这篇文章主要介绍了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