测试深度相等*与共享*JavaScript对象

Test deep equality *with sharing* of JavaScript objects

本文关键字：共享 JavaScript 对象 测试 深度      更新时间：2023-09-26
在

JavaScript中测试两个对象的深度相等性的主题上已经有很多笔墨。然而，似乎没有人关心区分以下两个对象：

var o1 = [{},{}];
var subitem = {};
var o2 = [subitem, subitem];
var o3 = [{}, {}];

大多数深度相等算法会说o1、o2和o3是相等的。我想要一个算法，说o1和o2不相等，但o1和o3相等。换句话说，我想要一种算法来告诉我指针图是否具有相同的结构。我关心这一点，因为如果我对第一个元素进行修改，则会反映在o2的第二个元素中，但不反映在o1中。

这意味着循环结构的深度相等应该起作用：

var o1 = [];
o1.push(o1);
var o2 = [];
o2.push(o2);
// deepGraphEqual(o1, o2) == true
var o3 = [[]];
o3[0].push(o3);
// deepGraphEqual(o1, o3) == false

如果你要避免改变项目，你可能需要 ECMAScript6 映射，所以我会接受使用这些映射的解决方案。

没有以

二次时间运行的 ES6 特征的版本：

function deepGraphEqual(a, b) {
    var left = [], right = [], has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        var i, k;
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        for (i = 0; i < left.length; i++) {
            if (a === left[i])
                return b === right[i];
            if (b === right[i])
                return a === left[i];
        }
        for (k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.push(a);
        right.push(b);
        for (k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}

带有线性时间运行的 ES6 Map的版本：

function deepGraphEqual(a, b) {
    let left = new Map(), right = new Map(), has = Object.prototype.hasOwnProperty;
    function visit(a, b) {
        if (typeof a !== 'object' || typeof b !== 'object' || a === null || b === null)
            return a === b;
        if (Object.getPrototypeOf(a) !== Object.getPrototypeOf(b))
            return false;
        if (left.has(a))
            return left.get(a) === b
        if (right.has(b))
            return right.get(b) === a
        for (let k in a)
            if (has.call(a, k) && !has.call(b, k))
                return false;
        for (let k in b)
            if (has.call(b, k) && !has.call(a, k))
                return false;
        left.set(a, b);
        right.set(b, a);
        for (let k in a)
            if (has.call(a, k) && !visit(a[k], b[k]))
                return false;
        return true;
    }
    return visit(a, b);
}
如何

改进Anders Kaseorg的答案：

如果在非常大的数据结构上使用该算法，则可能会出现堆栈溢出错误。例如，对于具有 5,000 个节点的完整图形，就会发生这种情况。所以我写了一个非递归版本，它使用广度优先搜索而不是深度优先搜索，因为这似乎更容易实现(不使用递归时(。迭代版本适用于具有 5,000 个节点的完整图形(不过，在我的机器上需要高达 6 秒(。在这里：

function deepEqual(item1, item2){
    var EQUAL_ATOM = 1, UNEQUAL = 2, OBJECT = 3;
    function compareSimple(first, second){
        var ty1 = typeof first, ty2 = typeof second;
        if (ty1!==ty2) return UNEQUAL;
        if (ty1!=='object'){
            if (first===second) return EQUAL_ATOM;
            if ((ty1==='number')&&isNaN(first)&&isNaN(second)) return EQUAL_ATOM;
            return UNEQUAL;
        }
        if (first===null) return (second===null) ? EQUAL_ATOM : UNEQUAL;
        if (second===null) return UNEQUAL;
        if (Object.getPrototypeOf(first) !== Object.getPrototypeOf(second)) return UNEQUAL;
        return OBJECT;
    }
    var c = compareSimple(item1, item2);
    if (c !== OBJECT) { return (c===EQUAL_ATOM); }
    var stack1 = [], stack2 = [], inverse1 = new Map(), inverse2 = new Map();
    stack1.push(item1); stack2.push(item2);
    inverse1.set(item1, 0); inverse2.set(item2, 0);
    var currentIdx = 0;
    var firstItem, secondItem, i, own, has1, has2, key, kid1, kid2, itemCount;
    while (currentIdx < stack1.length){
        firstItem = stack1[currentIdx]; secondItem = stack2[currentIdx];
        own = {};
        for (key in firstItem){
            has1 = firstItem.hasOwnProperty(key);
            has2 = secondItem.hasOwnProperty(key);
            if (has1 !== has2) return false;
            if (has1) { own[key] = null; }
        }
        for (key in secondItem){
            if (!(key in own)){
                has1 = firstItem.hasOwnProperty(key);
                has2 = secondItem.hasOwnProperty(key);
                if (has1 !== has2) return false;
                if (has1) { own[key] = null; }
            }
        }
        for (key in own){
            kid1 = firstItem[key];
            kid2 = secondItem[key];
            c = compareSimple(kid1, kid2);
            if (c === UNEQUAL) return false;
            if (c === OBJECT){
                has1 = inverse1.has(kid1);
                has2 = inverse2.has(kid2);
                if (has1 !== has2) return false;
                if (has1){
                    if (inverse1.get(kid1) !== inverse2.get(kid2)) { return false; }
                } else {
                    itemCount = stack1.length;
                    stack1.push(kid1); stack2.push(kid2);
                    inverse1.set(kid1, itemCount); inverse2.set(kid2, itemCount);
                }
            }
        }
        ++currentIdx;
    }
    return true;
}

我在 jsperf.com 网站上添加了一些速度测试。有趣的是，根据数据结构的不同，有时Anders的递归版本更快，有时我的迭代版本更快，平均值更有利于Anders。

以下是jsperf测试的链接：

侄子例子

从 reddit 示例循环免费真实世界的 JSON

叔

叔示例

具有 2K 节点的完整图形

具有 5K 节点的完整图形

此外，内置对象的处理方式可能不是您想要的。许多或大多数内置对象"隐藏"其密钥。如果你Object.keys(...)，你只会得到一个空数组。

now = new Date();
keys = Object.keys(now);  // result: []

因此，例如，任何 2 个Date都是相互deepGraphEqual的，也是任何 2 个RegExp s。这很可能不是你想要的。我没有所有这些的"全部"，并且遍历所有现有的"内置"对象将花费很长时间。但至于Dates和RegExp，这里有一些更合理的东西，用.toString()来比较它们。

相关文章：