获取两个数组之间的变化的算法

Question

我需要创建一个算法，它可以（高效地）获取旧数组和新数组之间的差异，并返回给我这两个数组中添加或删除的项。它需要在JavaScript中实现（以便在浏览器中运行），但算法比语言更重要。

以下是我设计的算法：http://jsbin.com/osewu3/13。有人能发现任何问题或提出改进建议吗？

谢谢！

代码清单：

function diff(o, n) {
  // deal with empty lists
  if (o == undefined) o = [];
  if (n == undefined) n = [];

  // sort both arrays (or this won't work)
  o.sort(); n.sort();

  // don't compare if either list is empty
  if (o.length == 0 || n.length == 0) return {added: n, removed: o};

  // declare temporary variables
  var op = 0; var np = 0;
  var a = []; var r = [];

  // compare arrays and add to add or remove lists
  while (op < o.length && np < n.length) {
      if (o[op] < n[np]) {
          // push to diff?
          r.push(o[op]);
          op++;
      }
      else if (o[op] > n[np]) {
          // push to diff?
          a.push(n[np]);
          np++;
      }
      else {
          op++;np++;
      }
  }

  // add remaining items
  if( np < n.length )
    a = a.concat(n.slice(np, n.length));
  if( op < o.length )
    r = r.concat(o.slice(op, o.length));

  return {added: a, removed: r}; 
}

（我也在另一个SO问题中发布了这篇文章作为潜在的解决方案，链接如下：JavaScript数组差异）

- Ian Grainger

---

是的，看起来像是标准集合交集算法的教科书实现（它使用了归并排序中“合并”算法的修改版本）。很棒，你自己想出来的。 - David

看起来没问题。你不需要针对空数组进行特别检查：如果有任何空数组，循环将立即退出，然后你将得到相同的结果。 - rbp

@rbp 看起来值得检查，因为肯定有一种情况是空的，在这种情况下我不想做任何事情。但实际上，现在我看看它 - 只是差了大约4个比较操作，所以我认为你是对的。那我可能会这样做。 - Ian Grainger

Answer 1

我创建了一个速度测试来比较两种可能的实现方式。

源代码:

function diff1 (o, n) { 
  // deal with empty lists 
  if (o == undefined) o = []; 
  if (n == undefined) n = []; 

  // sort both arrays (or this won't work) 
  o.sort(); n.sort(); 

  // don't compare if either list is empty 
  if (o.length == 0 || n.length == 0) return {added: n, removed: o}; 

  // declare temporary variables 
  var op = 0; var np = 0; 
  var a = []; var r = []; 

  // compare arrays and add to add or remove lists 
  while (op < o.length && np < n.length) { 
      if (o[op] < n[np]) { 
          // push to diff? 
          r.push(o[op]); 
          op++; 
      } 
      else if (o[op] > n[np]) { 
          // push to diff? 
          a.push(n[np]); 
          np++; 
      } 
      else { 
          op++;np++; 
      } 
  } 

  // add remaining items 
  if( np < n.length ) 
    a = a.concat(n.slice(np, n.length)); 
  if( op < o.length ) 
    r = r.concat(o.slice(op, o.length)); 

  return {added: a, removed: r};  
}

function diff2 (o, n) {
        // convert array items to object members
    var objO = {}, objN = {};
    for (var i = 0; i < o.length; i++) {
        objO[o[i]] = 1;
    }
    for (var i = 0; i < n.length; i++) {
        objN[n[i]] = 1;
    }

    var a = []; var r = []; 

    for (var i in objO) {
        if (i in objN) {
            delete objN[i];
        }
        else {
            r.push (i);
        }
    }
    for (var i in objN) {
        a.push (i);
    }
    return {added: a, removed: r};
}

var o = [], n = [];
for (var i = 0; i < 300000; i++) {
    if (i % 2 == 0) {
        o.push (i);
    }
    if (i % 3 == 0) {
        n.push (i);
    }
}

var start = new Date ();
diff1 (o, n);
var end1 = new Date ();
diff2 (o, n);
var end2 = new Date ();

alert ((end1 - start) + ", " + (end2 - end1));

diff2的缺点是返回的数组（added，removed）未排序。

速度测试：

IE7：diff1：2578ms，diff2：1906ms

IE8：diff1：1953ms，diff2：1152ms

Firefox：diff1：254ms，diff2：527ms

Opera：diff1：143ms，diff2：253ms

Safari：diff1：466ms，diff2：657ms

Chrome：diff1：734ms，diff2：581ms

结论：在Firefox、Opera和Safari中，diff1更快；在IE和Chrome中，diff2更快。

- gumape

---

这些时间是真的吗？那么这两个算法都太慢了，没有任何用处。 - KooiInc

好的，抱歉之前的评论：我没有看到您使用的数组大小。 - KooiInc

太好了，谢谢！我现在就留下它，因为我已经理解了 :) - Ian Grainger

Answer 2

没有undefined常量。你应该检查变量的类型：

if (typeof o === 'undefined') o = [];

编辑：

正如 Tim Down 所示，该属性实际上在标准中已经定义，但由于标准未将其定义为常量，因此它是不可靠的，不应该使用。

- Guffa

---

抱歉，请解释一下。对我来说，未定义似乎工作正常。这是undefined在w3schools的参考页面：http://www.w3schools.com/jsref/jsref_undefined.asp（“所有主要浏览器都支持undefined属性。”）。 - Ian Grainger

没有所谓的“未定义属性”。它只是一个未被赋值的变量。通过给它赋值可以很容易地证明这一点，你可以测试它不再是未定义的。如果它真的是属性，你将无法更改它的值。因此，“未定义属性”在任何浏览器中都不被支持。 - Guffa

这里有一些证据证明你是正确的，我会让w3schools.com来解释它！http://jsbin.com/ajolu3/2 - Ian Grainger

说“没有未定义的属性”是错误的：undefined实际上是全局对象的一个属性，其值为undefined（ECMAScript规范，15.1.1.3）。您是正确的，它的值可以被分配给其他东西。 - Tim Down

@Tim Down：好的，如果标准规定了一个不必保持不变的常量，那么这个标准在这一点上是有缺陷的，因此不应该使用该属性。 - Guffa

在ECMAScript 5严格模式下，undefined无法被覆盖，因此现在更加有用。 - Tim Down

Answer 3

你自己想出这个算法看起来非常不错！恭喜！
但是请记住，虽然你的算法可以显示两个数组内容的更改（例如删除项目等），但它无法显示内容顺序的更改（或删除的项目后来再次添加）。

例如，你可以从数组a中删除项目1，然后稍后将其重新添加，从技术上讲，这会更改数组a与数组b，但是你的算法却无法察觉到这一点。

array a: {1, 2, 3, 4, 5, 6}

array b: {1, 2, 3, 4, 5, 6}

array a: {2, 3, 4, 5, 6}    //after a.shift();
array a: {2, 3, 4, 5, 6, 1} //after a.push(1);

=> a != b //your algorithm would return "a == b" though

你的算法可能对你特定的需求已足够，但如果需要一个真正严格的数组差异算法，我建议尝试移植字符串差异算法。 基本上是改变算法，以不是比较字符串中的字符/运行，而是比较数组中的项。

JavaScript 字符串差异算法 (JS 代码)

- Regexident

---

我现在拥有的列表在服务器上都已经排序好了（实际上我在我的代码实现中注释掉了排序行;)）。 你说字符串差异 - 实际上 - 有人在博客文章中建议只需创建一个字符串，使用正则表达式（或一组），然后再次拆分。有趣的方法。但我不知道效率如何。 - Ian Grainger

好的，字符串差异需要比较上下文敏感的更改。 （排序会消除这些更改）由于字符串（至少在许多语言中）仅是char数组，因此我的第一个想法是处理数组对象（或其哈希），就像您在字符串差异中处理char一样。
因此，在您的比较检查中，您应该说“对象/哈希a是否与对象/哈希b匹配？”，而不是“char a是否与char b匹配？” - Regexident

哦，我不推荐“regex”的技巧。（尽管我喜欢regex，这也是我的用户名） 它们只适用于CFL，因此对于几乎任何上下文敏感的东西来说都是没用的（例如“容易出错”）。 我宁愿使用对象哈希并进行比较，就像我在上面的评论中写的那样。 当比较数组时，我只提到“string diff”，因为字符串diff是上下文敏感的，因此在比较数组时最有可能需要它。（至少对于通用的比较算法，您的特定情况可能很好地满足您的算法要求）。 - Regexident

Answer 4

以下页面有一个函数，可以从另一个数组中移除一个数组，并可用于提供2个值。 使用RemoveArrayItems()从JavaScript数组中删除项目

var newItemsAdded=RemoveArrayItems(oldArray,newArray);
var ItemsRemoved =RemoveArrayItems(newArray,oldArray);

- Alex

---

看起来是个不错的方法。我试图对其进行分析，但没有取得很大进展。肯定与我的方法相当，如果我要重新开始，我一定会使用它！ - Ian Grainger

链接似乎已失效。 - red.clover

Answer 5

我认为diff方法的实现是正确的，由于排序方法，你的算法的时间复杂度是O(n * log(n))。如果你使用数组，在比较之前需要对它们进行排序，而排序算法的时间复杂度至少为O(n * log(n))。

如果o和n数组不能包含多个相同的值，那么使用对象（关联数组）可能是更好的选择。

例如：

function diff(o, n) { 
    var a = {}; var r = {}; 

    for (var i in o) {
        if (!(i in n)) {
            r[i] = 1;
        }
    }
    for (var i in n) {
        if (!(i in o)) {
            a[i] = 1;
        }
    }
    return {added: a, removed: r};
}

    // how to use
var o = {"a":1, "b":1, "ab":1};
var n = {"a":1, "aa":1};

var diffon = diff (o, n);

    // display the results
var added = "", removed = "";
for (var i in diffon.added) {
    added += i + ", ";
}
for (var i in diffon.removed) {
    removed += i + ", ";
}

alert ("added: " + added);
alert ("removed: " + removed);

在这种情况下的时间复杂度为O(n)。

如果您需要有关JavaScript中数组、关联数组的更多详细信息，建议访问以下链接： Array object

- gumape

---

那么，如果要将你的解决方案加入我的代码中，我需要将我的输入和输出对象转换为对象字面量语法吗？除非有一种非常便宜的方法可以做到这一点，否则我宁愿坚持使用数组。是否有便宜的方法在它们之间进行转换？ - Ian Grainger

Answer 6

// I prefer to not sort the arrays

Array.prototype.diff= function(ar){
    var a= [], i= 0, L= this.length,
    ar= ar.concat(), t1, t2;
    while(i<L){
        t1= this[i++];
        t2= ar.indexOf(t1);
        if(t2!= -1){
            ar.splice(t2, 1);
        }
        else a.push(t1);
    }
    return a;
}

Array.prototype.compare= function(a2){
    return{
        r: this.diff(a2), a: a2.diff(this)
    }
}

/* 
test

var a1= [-1, 2, 3, 3, 4, 5], a2= [0, 2, 4, 3, 5, 6, 8];
var o= a1.compare(a2);

alert('added: '+o.a+'\nremoved: '+o.r);


returned:

added: 0, 6, 8
removed: -1, 3

*/


// oldbrowser code:

if(![].indexOf){
    Array.prototype.indexOf= function(what, i){
        i= i || 0;
        var L= this.length;
        while(i< L){
            if(this[i]=== what) return i;
            ++i;
        }
        return -1;
    }
}

// Return common values instead of differences
Array.prototype.incommon= function(ar){
    var a= [], i= 0, L= this.length, a2= ar.concat(), t1, t2;
    while(i<L && a2.length){
        t1= this[i++];
        t2= a2.indexOf(t1);
        if(t2 != -1){
            a.push(a2.splice(t2, 1));
        }
    }
    return a;
}

- kennebec

Answer 7

我使用这个函数：

function diffArray(from, to){
    /*
    result will hold the transformations (in order) that need to 
    be done to make the from array equal to the to array
    */
    var result = [];
    var fromValue, fromIndex, fromCount, fromOffset;
    var toValue, toIndex, toCount, toMap;

    /*
    Buld an index for the two arrays to speed up the process. Do
    note that due to this optimization all values in the array will
    be transformed to strings. So the number 1 will be equal to the
    string '1'. Also all objects will converted to strings (via
    toString) and therefore probably considered equal.
    */
    toMap = to.reduce(function(result, value, index){
        if(value in result) result[value].push(index);
        else result[value] = [index];
        return result;
    }, {});
    toIndex = 0;
    toCount = to.length;

    fromOffset = 0;
    fromIndex = 0;
    fromCount = from.length;

    /*
    loop until we reach the end of one of the two arrays
    */
    while(fromIndex < fromCount && toIndex < toCount){
        fromValue = from[fromIndex];
        toValue = to[toIndex];

        /*
        when the two values are equal, no transformation is required.
        */
        if(fromValue === toValue){
            fromIndex++;
            toIndex++;
        }
        else{
            /*
            if fromValue is not in the remainder of the to array
            */
            // if(~to.indexOf(fromValue, toIndex)){ 
            if(
                fromValue in toMap
                && toMap[fromValue].some(function(value){
                    return toIndex <= value;
                })
            ){
                result.push({
                    type: 'insert'
                    , index: fromIndex + fromOffset
                    , value: toValue
                });
                toIndex++
                fromOffset++;
            }
            else{
                result.push({
                    type: 'delete'
                    , index: toIndex
                    , value: fromValue
                });
                fromIndex++
                fromOffset--;
            }

        }

    }

    return result
    /*
    add the remainder of the from array to the result as deletions
    */
    .concat(
        from
        .slice(fromIndex)
        .map(function(value, index){
            var result = {
                type: 'delete'
                , index: index + fromIndex + fromOffset
                , value: value
            };
            fromOffset--;
            return result;
        })
    )
    /*
    add the remainder of the to array to the result as insertions
    */
    .concat(
        to
        .slice(toIndex)
        .map(function(value, index){
            var result = {
                type: 'insert'
                , index: index + toIndex
                , value: value
            };
            fromOffset++;
            return result;
        })
    )
    ;

}//diffArray

请查看存储库以获取更新和单元测试： https://github.com/elmerbulthuis/diff-array

- Elmer

---

这读起来整体相似，对吧？我猜创建该索引比排序更快，并且移除了重复项？所以你会为了更快的速度使用略微多一点的内存？ - Ian Grainger

Answer 8

PHP解决方案，用于关联数组，将插入/更新/删除拆分为单独的数组：

/**
 * compute differences between associative arrays.
 * the inserts, updates, deletes are returned
 * in separate arrays. Note: To combine arrays
 * safely preserving numeric keys, use $a + $b
 * instead of array_merge($a, $b).
 *
 * Author: Monte Ohrt <[e-mail]>
 * Version: 1.0
 * Date: July 17th, 2014
 *
 * @param array $a1
 * @param array $a2
 * @return array ($inserts, $updates, $deletes)
 */
get_array_differences($a1, $a2) {
    // get diffs forward and backward
    $forward = array_diff_assoc($a1, $a2);
    $backward = array_diff_assoc($a2, $a1);
    // compute arrays
    $inserts = array_diff_key($forward, $backward);
    $updates = array_intersect_key($forward, $backward);
    $deletes = array_diff_key($backward, $forward);
    return array($inserts, $updates, $deletes);
}

https://gist.github.com/mohrt/f7ea4e2bf2ec8ba7542c

- mohrt

---

与JavaScript相关的问题无关。 - Tim Down