KnockoutJS數組比較算法的示例分析

這篇文章給大家分享的是有關KnockoutJS數組比較算法的示例分析的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

這篇文章主要介紹了KnockoutJS數組比較算法實例詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下

前端開發中，數組是一種非常有用的數據結構。這篇博客會解釋并分析KnockoutJS實現中使用的數據比較算法。

算法的目的

KnockoutJS使用MVVM的思想，view model中的數組元素會對應data model中的數組數據，當用戶進行輸入或者請求后臺時，數組數據會發生變更， 從而帶動UI的更新。例如購物車類的頁面，用戶可以通過點擊一些按鈕來添加/刪除購物車中儲存的物品。一個顯示購物車中商品詳情的列表會根據數組中物品元素的變化實時更新。

另一個例子可以是一個展示餐館等候隊列的展示頁面，隨著客人加入/退出隊列，服務器端會不斷推送數據到前端頁面，實時更新當前最新的隊列情況。因此我們需要一個算法，根據更新前的數組數據和更新后的數組數據，計算出一個DOM操作序列，從而使得綁定的DOM元素能根據data model里的數據變化自動更新DOM里的元素。

經典Edit Distance問題

開始正式分析之前，我們先回顧一個經典的算法問題。給定兩個字符串，允許“添加”，“刪除”或是“替換”字符，如何計算出將一個字符串轉換成另一個字符串的操作次數。我們不難發現我們之前討論的問題和這個經典的問題非常相似，但是又有以下一些不同點：

• DOM元素并不能很好地支持“替換”的操作。通過瀏覽器的JavaScript api并不能很高效地將一個DOM元素變換成另一個DOM元素，所以必須通過“添加”和“刪除”的組合操作來實現“替換”的等效操作。

• DOM元素可以支持“移動”操作。盡管原版Edit Distance的并沒有提到，但是在瀏覽器中利用已經存在的DOM元素是一個很合理的做法。

• 原版問題只要求計算出最小的操作次數，我們的問題里需要計算出一個DOM操作序列。

眾所周知，經典Edit Distance的算法使用動態規劃實現，需要使用O(m*n)的時間和O(m*n)的空間復雜度（假設兩個字符串的長度分別為m和n)。

KnockoutJS使用的edit distance算法

KnockoutJS的數組比較算法的第一步是一個變種的edit distance算法，基于具體問題的特殊性進行了一些調整。算法仍然使用動態規劃，需要計算出一個2維的edit distance矩陣（叫做M），每個元素對應兩個數組的子序列的最小edit distance + 1。比如說，假設兩個數組分別叫arr1和arr2，矩陣的第i行第j列的值就是arr1[:i]和arr2[:j]的最小edit distance + 1。

不難發現，從任意的一個（i，j）配對出發，我們可以有如下的遞歸關系：

• arr1[i-1] === arr2[j-1], 我們可以省去一次操作，M[i][j] = M[i-1][j-1]

• arr1[i-1] !== arryou2[j-1], 這時我們有兩種選項，取最小值

• 刪除arr1[i-1]，繼續比較， 此時M[i][j] = M[i-1][j] + 1

• 在arr1[i-1]后添加一個等于arr2[j-1]的元素，繼續比較，此時M[i][j] = M[i][j-1] + 1

根據這個遞推關系可以知道如何初始化好第一行和第一列。算法本身使用循環自下而上實現，可以省去遞歸帶來的額外堆棧開銷。

計算edit distance具體代碼如下：

// ... preprocess such that arr1 is always the shorter array
var myMin = Math.min,
  myMax = Math.max,
  editDistanceMatrix = [],
  smlIndex, smlIndexMax = smlArray.length,
  bigIndex, bigIndexMax = bigArray.length,
  compareRange = (bigIndexMax - smlIndexMax) || 1,
  maxDistance = smlIndexMax + bigIndexMax + 1,
  thisRow, lastRow,
  bigIndexMaxForRow, bigIndexMinForRow;

for (smlIndex = 0; smlIndex <= smlIndexMax; smlIndex++) {
  lastRow = thisRow;
  editDistanceMatrix.push(thisRow = []);
  bigIndexMaxForRow = myMin(bigIndexMax, smlIndex + compareRange);
  bigIndexMinForRow = myMax(0, smlIndex - 1);
  for (bigIndex = bigIndexMinForRow; bigIndex <= bigIndexMaxForRow; bigIndex++) {
    if (!bigIndex)
      thisRow[bigIndex] = smlIndex + 1;
    else if (!smlIndex) // Top row - transform empty array into new array via additions
      thisRow[bigIndex] = bigIndex + 1;
    else if (smlArray[smlIndex - 1] === bigArray[bigIndex - 1])
      thisRow[bigIndex] = lastRow[bigIndex - 1];         // copy value (no edit)
    else {
      var northDistance = lastRow[bigIndex] || maxDistance;    // not in big (deletion)
      var westDistance = thisRow[bigIndex - 1] || maxDistance;  // not in small (addition)
      thisRow[bigIndex] = myMin(northDistance, westDistance) + 1;
    }
  }
}
// editDistanceMatrix now stores the result

算法利用了一個具體問題的特性，那就是頭尾交叉的子序列配對不可能出現最優情況。比如說，對于數組abc和efg來說，配對abc和e不可能出現在最優解里。因此算法的第二層循環只需要遍歷長數組長度和短數組長度的差值而不是長數組的長度。算法的時間復雜度被縮減到了O(m*(n-m))。因為JavaScript的數組基于object實現，未使用的index不會占用內存，因此空間復雜度也被縮減到了O(m*(n-m))。

仔細想想會發現在這個應用場景里，這是一個非常高效的算法。盡管理論最壞復雜度仍然是平方級，但是對于前端應用的場景來說，大部分時間面對的是高頻小幅的數據變化。也就是說，在大部分情況下，n和m非常接近，因此這個算法在大部分情況下可以達到線性的時間和空間復雜度，相比平方級的復雜度是一個巨大的提升。

在得到edit distance matrix之后獲取操作序列就非常簡單了，只要從尾部按照之前賦值的規則倒退至第一行或者第一列即可。
計算操作序列具體代碼如下：

// ... continue from the edit distance computation
var editScript = [], meMinusOne, notInSml = [], notInBig = [];
for (smlIndex = smlIndexMax, bigIndex = bigIndexMax; smlIndex || bigIndex;) {
  meMinusOne = editDistanceMatrix[smlIndex][bigIndex] - 1;
  if (bigIndex && meMinusOne === editDistanceMatrix[smlIndex][bigIndex-1]) {
    notInSml.push(editScript[editScript.length] = {   // added
      'status': statusNotInSml,
      'value': bigArray[--bigIndex],
      'index': bigIndex });
  } else if (smlIndex && meMinusOne === editDistanceMatrix[smlIndex - 1][bigIndex]) {
    notInBig.push(editScript[editScript.length] = {   // deleted
      'status': statusNotInBig,
      'value': smlArray[--smlIndex],
      'index': smlIndex });
  } else {
    --bigIndex;
    --smlIndex;
    if (!options['sparse']) {
      editScript.push({
        'status': "retained",
        'value': bigArray[bigIndex] });
    }
  }
}
// editScript has the (reversed) sequence of actions

元素移動優化

如之前提到的，利用已有的重復元素可以減少不必要的DOM操作，具體實現方法非常簡單，就是遍歷所有的“添加”，“刪除”操作，檢查是否有相同的元素同時被添加和刪除了。這個過程最壞情況下需要O(m*n)的時間復雜度，破環了之前的優化，因此算法提供一個可選的參數，在連續10*m個配對都沒有發現可移動元素的情況下直接退出算法，從而保證整個算法的時間復雜度接近線性。

檢查可移動元素的具體代碼如下：

// left is all the operations of "Add"
// right is all the operations of "Delete
if (left.length && right.length) {
  var failedCompares, l, r, leftItem, rightItem;
  for (failedCompares = l = 0; (!limitFailedCompares || failedCompares < limitFailedCompares) && (leftItem = left[l]); ++l) {
    for (r = 0; rightItem = right[r]; ++r) {
      if (leftItem['value'] === rightItem['value']) {
        leftItem['moved'] = rightItem['index'];
        rightItem['moved'] = leftItem['index'];
        right.splice(r, 1);     // This item is marked as moved; so remove it from right list
        failedCompares = r = 0;   // Reset failed compares count because we're checking for consecutive failures
        break;
      }
    }
    failedCompares += r;
  }
}
// Operations that can be optimized to "Move" will be marked with the "moved" property

感謝各位的閱讀！關于“KnockoutJS數組比較算法的示例分析”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！