JavaScript实现ZLOGO: 性能改进

主攻前文吴烜：JavaScript实现ZLOGO: 界面改进与速度可调的几个性能问题

在线演示: 圈3

源码仍在: program-in-chinese/quan3

之前是在绘制过程中计算每帧需要绘制的线段, 在尝试改进的过程中很快发现问题太多且不易测试. 接着在某早晨"醒悟"到应该而且可以在绘制前计算好每一帧的步进路径表. 不仅可以避免绘制卡顿问题, 还便于测试(因为是纯JS实现, 不需夹杂DOM操作). 于是通过如下递归代码实现了截取指定位置的路径表:

// 返回{截取部分: 路径表, 剩余部分: 路径表}
// 如果 开始位置 >= 终止位置, 返回{[], 所有}
function 截取路径表(路径表, 开始位置, 终止位置) {
  if (开始位置 >= 终止位置) {
    return {截取部分: [], 剩余部分: 路径表};
  }
  if (路径表.length == 0) {
    return {截取部分: [], 剩余部分: []};
  } else if (路径表.length == 1) {
    return 截取路径(路径表[0], 开始位置, 终止位置);
  } else {
    var 段 = 路径表[0];
    var 长度 = 段.长度;
    if (开始位置 >= 长度) {
      路径表.shift();
      return 截取路径表(路径表, 开始位置 - 长度, 终止位置 - 长度);
    } else if (开始位置 < 长度 && 终止位置 < 长度) {
      var 前段 = 截取路径(路径表[0], 开始位置, 终止位置);
      路径表.shift();
      return {截取部分: 前段.截取部分, 剩余部分: 前段.剩余部分.concat(路径表)};
    } else {
      var 前段 = 截取路径(路径表[0], 开始位置, 长度);
      路径表.shift();
      var 后段 = 截取路径表(路径表, 0, 终止位置 - 长度);
      return {截取部分: 前段.截取部分.concat(后段.截取部分), 剩余部分: 后段.剩余部分};
    }
  }
}

原本为去掉路径表第一项, 使用了slice(), 测试时发现耗时接近O(n^3). 导致点击"运行"后的运算耗时在复杂时(比如>10000线段的图形)太长(停顿超过1秒)难以接受. 改为shift()后, 粗测不超过O(n^2), 暂未深入研究.

这里是获取每一帧的路径表(每帧前进的长度等于"速度"):

function 按步进拆分路径表(路径表, 速度) {
  var 所有段 = [];
  while (路径表.length > 0) {
    var 拆分路径 = 截取路径表(路径表, 0, 速度);
    所有段.push(拆分路径.截取部分);
    路径表 = 拆分路径.剩余部分;
  }
  return 所有段;
}

感觉已经达到可以让用户玩玩的程度. 接下来视反馈决定改进方向.

2019-01-23