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

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

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

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

算法的目的

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

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

經(jīng)典Edit Distance問(wèn)題

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

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

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

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

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

KnockoutJS使用的edit distance算法

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

不難發(fā)現(xiàn)，從任意的一個(gè)（i，j）配對(duì)出發(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)，可以省去遞歸帶來(lái)的額外堆棧開銷。

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

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

在得到edit distance matrix之后獲取操作序列就非常簡(jiǎn)單了，只要從尾部按照之前賦值的規(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

元素移動(dòng)優(yōu)化

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

檢查可移動(dòng)元素的具體代碼如下：

// 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)容可以對(duì)大家有一定的幫助，讓大家可以學(xué)到更多知識(shí)，如果覺得文章不錯(cuò)，可以把它分享出去讓更多的人看到吧！

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

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

廣告

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