仔细想想会发现在这个应用场景里，这是一个非常高效的算法。尽管理论最坏复杂度仍然是平方级，但是对于前端应用的场景来说，大部分时间面对的是高频小幅的数据变化。也就是说，在大部分情况下，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