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

Stack Overflow用户

提问于 2010-08-13 12:17:18

回答 8查看 8.5K关注 0票数 17

我需要创建一个算法，它将(有效地)获取一个旧数组和一个新数组，并返回这两个数组之间的更改(添加了哪些项，删除了哪些项)。它碰巧需要在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 array difference)

arrays

performance

algorithm

javascript

跨境电商上云解决方案

轻量应用服务器助力卖家与独立站拓展跨境电商业务

回答 8

Stack Overflow用户

回答已采纳

发布于 2010-08-13 12:27:34

下面的页面有一个从一个数组中删除另一个数组的函数，可以用来给你两个值。Remove items from a JavaScript Array with RemoveArrayItems()

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

票数 0

Stack Overflow用户

发布于 2010-08-13 12:25:28

没有undefined常量。您应该改为检查变量的类型：

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

编辑：

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

票数 3

Stack Overflow用户

发布于 2010-08-13 16:04:34

我在两个可能的实现之间创建了一个速度测试。

源代码：

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));