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

成都網(wǎng)站設(shè)計、成都網(wǎng)站制作的關(guān)注點(diǎn)不是能為您做些什么網(wǎng)站，而是怎么做網(wǎng)站，有沒有做好網(wǎng)站，給創(chuàng)新互聯(lián)一個展示的機(jī)會來證明自己，這并不會花費(fèi)您太多時間，或許會給您帶來新的靈感和驚喜。面向用戶友好，注重用戶體驗，一切以用戶為中心。

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

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

算法的目的

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

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

經(jīng)典Edit Distance問題

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

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

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

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

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

KnockoutJS使用的edit distance算法

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

不難發(fā)現(xiàn)，從任意的一個（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], 這時我們有兩種選項，取最小值

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

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

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

計算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

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

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

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

// ... 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操作，具體實現(xiàn)方法非常簡單，就是遍歷所有的“添加”，“刪除”操作，檢查是否有相同的元素同時被添加和刪除了。這個過程最壞情況下需要O(m*n)的時間復(fù)雜度，破環(huán)了之前的優(yōu)化，因此算法提供一個可選的參數(shù)，在連續(xù)10*m個配對都沒有發(fā)現(xiàn)可移動元素的情況下直接退出算法，從而保證整個算法的時間復(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)于“KnockoutJS數(shù)組比較算法的示例分析”這篇文章就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，讓大家可以學(xué)到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！

網(wǎng)站題目：KnockoutJS數(shù)組比較算法的示例分析-創(chuàng)新互聯(lián)
當(dāng)前URL：http://aaarwkj.com/article10/isogo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、網(wǎng)站建設(shè)、網(wǎng)站策劃、響應(yīng)式網(wǎng)站、企業(yè)建站、網(wǎng)頁設(shè)計公司

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)