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

前端開發(fā)中，數(shù)組是一種非常有用的數(shù)據(jù)結(jié)構(gòu)。這篇博客會解釋并分析KnockoutJS實(shí)現(xiàn)中使用的數(shù)據(jù)比較算法。

算法的目的

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

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

經(jīng)典Edit Distance問題

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

• DOM元素并不能很好地支持“替換”的操作。通過瀏覽器的JavaScript api并不能很高效地將一個(gè)DOM元素變換成另一個(gè)DOM元素，所以必須通過“添加”和“刪除”的組合操作來實(shí)現(xiàn)“替換”的等效操作。
• DOM元素可以支持“移動”操作。盡管原版Edit Distance的并沒有提到，但是在瀏覽器中利用已經(jīng)存在的DOM元素是一個(gè)很合理的做法。
• 原版問題只要求計(jì)算出最小的操作次數(shù)，我們的問題里需要計(jì)算出一個(gè)DOM操作序列。

眾所周知，經(jīng)典Edit Distance的算法使用動態(tài)規(guī)劃實(shí)現(xiàn)，需要使用O(m*n)的時(shí)間和O(m*n)的空間復(fù)雜度（假設(shè)兩個(gè)字符串的長度分別為m和n)。

KnockoutJS使用的edit distance算法

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

不難發(fā)現(xiàn)，從任意的一個(gè)（i，j）配對出發(fā)，我們可以有如下的遞歸關(guān)系：

• arr1[i-1] === arr2[j-1], 我們可以省去一次操作，M[i][j] = M[i-1][j-1]
• arr1[i-1] !== arryou2[j-1], 這時(shí)我們有兩種選項(xiàng)，取最小值
  • 刪除arr1[i-1]，繼續(xù)比較， 此時(shí)M[i][j] = M[i-1][j] + 1
  • 在arr1[i-1]后添加一個(gè)等于arr2[j-1]的元素，繼續(xù)比較，此時(shí)M[i][j] = M[i][j-1] + 1

根據(jù)這個(gè)遞推關(guān)系可以知道如何初始化好第一行和第一列。算法本身使用循環(huán)自下而上實(shí)現(xiàn)，可以省去遞歸帶來的額外堆棧開銷。

計(jì)算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

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

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

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

// ... 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

元素移動優(yōu)化

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

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

// 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

完整的相關(guān)代碼可以在這里找到

knockout/src/binding/editDetection/compareArrays.js

以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

最新評論