2019-01-23 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 所有段;
}

感覺已經達到可以讓用戶玩玩的程度. 接下來視反饋決定改進方向.