确定JavaScript中循环数据结构相等的算法
Algorithm for determining equality of circular data structures in JavaScript
var ones = [1];
ones[1] = ones;
ones;
// => [1, [1, [1, [1, [1, ...]]]]]
var ones_ = [1];
ones_[1] = ones_;
ones_;
// => [1, [1, [1, [1, [1, ...]]]]]
如何确定ones
和ones_
相等?是否有一种算法可以处理如上所述的圆形结构?
解决这个问题的一个基本方法是注意,如果在递归比较期间,我们再次比较我们已经比较的同一对对象,那么我们可以简单地假设它们是相等的。这是有效的,因为如果它们毕竟不是相等,那么已经在进行的比较最终会发现它们之间的一些差异。
因此,我们可以简单地从一个基本的递归比较函数开始,并添加当前正在比较的对象堆栈:
function isEqual (a, b) {
var stack = [];
function _isEqual (a, b) {
// console.log("->", stack.length);
// handle some simple cases first
if (a === b) return true;
if (typeof(a) !== "object" || typeof(b) !== "object") return false;
// XXX: typeof(null) === "object", but Object.getPrototypeOf(null) throws!
if (a === null || b === null) return false;
var proto = Object.getPrototypeOf(a);
if (proto !== Object.getPrototypeOf(b)) return false;
// assume that non-identical objects of unrecognized type are not equal
// XXX: could add code here to properly compare e.g. Date objects
if (proto !== Object.prototype && proto !== Array.prototype) return false;
// check the stack before doing a recursive comparison
for (var i = 0; i < stack.length; i++) {
if (a === stack[i][0] && b === stack[i][1]) return true;
// if (b === stack[i][0] && a === stack[i][1]) return true;
}
// do the objects even have the same keys?
for (var prop in a) if (!(prop in b)) return false;
for (var prop in b) if (!(prop in a)) return false;
// nothing to do but recurse!
stack.push([a, b]);
for (var prop in a) {
if (!(_isEqual(a[prop], b[prop]))) {
stack.pop();
return false;
}
}
stack.pop();
return true;
}
return _isEqual(a, b);
}
// TEST CASES:
var ones = [1]; ones[1] = ones;
var foo = [1]; foo[1] = [1, foo];
var bar = [1]; bar[1] = [1, ones];
console.log("ones == foo:", isEqual(ones, foo));
console.log("ones == bar:", isEqual(ones, bar));
console.log("foo == bar:", isEqual(foo, bar));
var obj = {}; obj["x"] = obj; obj["y"] = {obj};
console.log("obj == obj[x]:", isEqual(obj, obj["x"]));
console.log("obj != obj[y]:", !isEqual(obj, obj["y"]));
var seven = []; seven[0] = [[[[[[seven]]]]]];
var eleven = []; eleven[0] = [[[[[[[[[[eleven]]]]]]]]]];
console.log("seven == eleven:", isEqual(seven, eleven));
console.log("[seven] == [eleven]:", isEqual([seven], [eleven]));
console.log("[seven] == seven:", isEqual([seven], seven));
console.log("[seven] == [[[eleven]]]:", isEqual([seven], [[[eleven]]]));
请注意,上面代码中的许多复杂性是由于它试图接受和(或多或少)优雅地处理任何不同类型的JavaScript值的混合,包括原语,空值,数组,普通对象和JS变量可以包含的所有其他杂项。如果您知道您的输入只能包含有限范围的数据类型,那么可能会大大简化这段代码。
p。由于堆栈比较,这段代码的运行时间可以高达O(和),其中n是需要比较的树中的节点数(可能比预期的要多;例如,比较上面代码片段中的对象seven
和eleven
需要77次递归调用),而d是堆栈的深度(在本例中,也可以达到77)。在ES2015中,一个潜在有用的优化可能是使用以前看到的对象的Map来减少堆栈查找,从0 (d)到有效的O(1)。如果我们期望所比较的数据结构通常有许多重复的分支,其中包含对相同对象的引用,那么将其扩展到一个包含我们已经发现相等的先前看到的对象的通用缓存中可能会很有用。
你可以通过迭代一个对象并用"指针"(=某些数组中的索引)替换已经看到的对象来'decycle'一个对象。一旦得到了循环的结构体,只需将它们序列化并作为字符串进行比较:
let encode = function (x) {
function _enc(x, lst) {
if (typeof x !== 'object')
return x;
let i = lst.indexOf(x);
if (i >= 0)
return {'->': i};
lst.push(x);
let y = {};
for (let k of Object.keys(x))
y[k] = _enc(x[k], lst)
return y;
}
return JSON.stringify(_enc(x, []));
};
//////
let ones = [1];
ones[1] = ones;
let ones_ = [1];
ones_[1] = ones_;
console.log(encode(ones) === encode(ones_))
// more interesting example
a = {
b: {
c: 123
}
};
a.b.d = a;
a.x = [9, a.b];
a2 = {
b: {
c: 123
}
};
a2.b.d = a2;
a2.x = [9, a2.b];
console.log(encode(a) === encode(a2))
相关文章:
- JS库支持各种数据结构?(如爪哇的番石榴)
- JavaScript数据结构
- Node JS,传统的数据结构?(如Set等),任何类似Java.util的node
- 更正扁平数据模型和noSQL数据结构
- 用于筛选无模式集合的最快数据结构
- 将数据结构转换为二进制数据
- JavaScript 设置具有对数搜索时间的数据结构
- 更好的数据结构来处理这个数组
- Firebase 数据结构理念
- 基于其他数据结构更新 AngularJS 中的数据结构
- JavaScript - JSON 数据结构的构建 - 如何使用变量值更改键名
- 如何处理在javascript中访问数据结构的两个回调
- 文字与原型对象表示法的数据结构
- 表示可用产品的所有组合的数据结构
- Immutable.js:表示2D游戏场的数据结构
- javascript和python返回的相同数据结构在d3.js中表现不同
- 无法识别的数据结构-转换为对象
- 确定JavaScript中循环数据结构相等的算法
- 我怎样才能改进这个JavaScript DOM操作数据结构/算法
- Word Ladder,Javascript:我使用的是什么算法和数据结构