获取两个数组之间的变化的算法
我需要创建一个算法，它将(有效地)获取一个旧数组和一个新数组，并返回这两个数组之间的更改(添加了哪些项，删除了哪些项)。它碰巧需要在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)
回答 8
Stack Overflow用户
发布于 2010-08-13 20:27:34
下面的页面有一个从一个数组中删除另一个数组的函数，可以用来给你两个值。Remove items from a JavaScript Array with RemoveArrayItems()
var newItemsAdded=RemoveArrayItems(oldArray,newArray);
var ItemsRemoved =RemoveArrayItems(newArray,oldArray);Stack Overflow用户
发布于 2010-08-13 20:25:28
没有undefined常量。您应该改为检查变量的类型：
if (typeof o === 'undefined') o = [];编辑：
正如Tim Down所展示的，该属性实际上是在标准中定义的，但由于标准没有将其定义为常量，因此它是不可靠的，不应该使用。
Stack Overflow用户
发布于 2010-08-14 00: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));diff2的缺点是返回的数组(添加的、移除的)不排序。
速度测试：
IE7: diff1: 2578ms，diff2: 1906ms
IE8: diff1: 1953ms，diff2: 1152ms
火狐：diff1: 254ms，diff2: 527ms
歌剧：diff1: 143ms，diff2: 253ms
Safari：diff1: 466ms，diff2: 657ms
Chrome: diff1: 734ms，diff2: 581ms
结论: diff1在火狐、Opera和Safari上运行速度较快，diff2在IE和Chrome上运行速度较快。
https://stackoverflow.com/questions/3476672
复制相似问题
腾讯云开发者
