使用 lodash 或下划线或 vanilla js 查找嵌套对象数组之间的深层差异

Question

我要比较的深层嵌套对象

const prevObj = {
    "ui_data": [
        {
            "children": [
                {
                    "editable": true,
                    "id": "22615650-510a-11ec-8393-cfd004935be3",
                    "mandatory": false,
                    "modifiable": true,
                    "options": [],
                    "t_id": "text",
                    "title": "Text 1",
                    "type": "FormFieldType.textField"
                },
                {
                    "editable": true,
                    "id": "2a6f9000-510a-11ec-8393-cfd004935be3",
                    "mandatory": false,
                    "modifiable": true,
                    "options": [],
                    "t_id": "cb",
                    "title": "Check Box 2",
                    "type": "FormFieldType.checkBox"
                }
            ],
            "id": "fe8223e0-5109-11ec-8393-cfd004935be3",
            "title": "Page-1",
            "type": "FormContainerType.page"
        }
    ]
}

const newObj = {
    "ui_data": [
        {
            "children": [
                {
                    "editable": true,
                    "id": "22615650-510a-11ec-8393-cfd004935be3",
                    "mandatory": false,
                    "modifiable": true,
                    "options": [],
                    "t_id": "text",
                    "title": "Text 1",
                    "type": "FormFieldType.textField"
                },
                {
                    "editable": true,
                    "id": "2a6f9000-510a-11ec-8393-cfd004935be3",
                    "mandatory": false,
                    "modifiable": true,
                    "options": [],
                    "t_id": "cb",
                    "title": "Check Box 2",
                    "type": "FormFieldType.checkBox"
                }
            ],
            "id": "fe8223e0-5109-11ec-8393-cfd004935be3",
            "title": "Page-1",
            "type": "FormContainerType.page"
        }
    ]
}

const wrapAddedKey = newValue => ({ oldValue: undefined, newValue });
function changes(oldCollection, newCollection) {
    const diff = _.reduce(oldCollection, function (result, oldValue, key) {
        const newValue = newCollection[key];
        if (_.isObject(oldValue) && _.isObject(newValue)) {
            const diff = _.compact(changes(oldValue, newValue));
            if (!_.isEmpty(diff)) {
                result[key] = diff;
            };
        } else if (oldValue !== newValue) {
            result[key] = { oldValue: oldValue, newValue: newValue };
        }
        return result;
    }, _.isArray(oldCollection) ? [] : {});
    const addedKeys = _.difference(_.keys(newCollection), _.keys(oldCollection));
    const additions = _.pick(newCollection, _.compact(addedKeys));
    return _.extend(diff, __.mapObject(additions, wrapAddedKey));
}

我正在创建一种算法来比较深度嵌套的对象，我正在使用 lodash 来比较对象的变化。我有两个深层嵌套的对象，其中还包含数组。我想比较它们内部是否有任何更新、创建或删除的内容。上面的代码适用于一层深度数组，但如果对象数组位于对象数组内部，则此代码不起作用。我已经分享了上面的对象示例。我期待的完整输出，如果创建了新的东西，那么它应该 return 跟随。

{
oldValues : null,
newValues : {
    // Values of newly created items
}
}

如果删除了某些内容，则应该 return

{
    oldValues  : {
         // Older Values of deleted item
    },
    newValues : null
}

如果更新了某些内容，则应该 return

{
     oldValues  : {
        // Older Values of item
    },
    newValues : {
        // Newer Values of item
    }
}

Answer 1

了解问题

问题中的示例对象使用了无效的符号，并且还分配了一个全局变量 anotherArr 作为副作用，这可能是无意的。（更新：问题中的示例对象在我 post 编辑了这个答案后发生了变化。下面的对象仍然类似于原始示例对象。）在这个答案中，我假设以下符号代替：

const prevObj = {
    arr: [{
        name: 'Ankur',
    }, {
        email: 'ankur4736@gmail.com',
    }, {
        key: 456,
    }, [{
        name: 'Shubham',
        anotherNestedArr: [{
            name: 'Gundeep Paji'
        }],
    }]],
};

const newObj = {
    arr: [{
        name: 'Shubham',
    }, {
        email: 'shubham@gmail.com',
    }, {
        key: 466,
    }, [{
        name: 'Gundeep Paji',
        anotherNestedArr: [{
            name: 'Ankur'
        }],
    }]],
};

如果我对问题的理解正确，您不仅要对对象进行深入比较，还要创建一个包含差异描述的新对象。您声明您当前的代码适用于对象但不适用于数组。从您的代码中，我收集到您希望 diff 看起来像这样：

const diff = {
    arr: [{
        name: {
            oldValue: 'Ankur',
            newValue: 'Shubham',
        },
    }, {
        email: {
            oldValue: 'ankur4736@gmail.com',
            newValue: 'shubham@gmail.com',
        },
    }, {
        key: {
            oldValue: 456,
            newValue: 466,
        },
    }, [{
        name: {
            oldValue: 'Shubham',
            newValue: 'Gundeep Paji',
        },
        anotherNestedArr: [{
            name: {
                oldValue: 'Gundeep Paji',
                newValue: 'Ankur',
            },
        }],
    }]],
};

稀疏数组与密集数组

在我们开始之前，我应该指出，有两种不同的方法可以创建一个新数组，该新数组仅包含旧数组中已在新数组中更改的值。为简单起见，我将使用两个数字数组作为示例：

const oldArr = [1, 2, 3, 4, 5, 6, 7];
const newArr = [1, 1, 3, 4, 7, 6, 7];
// differences:    ^        ^

为了便于说明，暂时假设我们只将旧值存储在 diff 中，而不是 {oldValue, newValue} 个对象。无论哪种方式，我们的 diff 数组一开始都是空的，但是如果我们选择 dense 表示差异的方式，我们只需附加 oldArr 中在 [=30 中发生变化的每个元素=]到最后：

const denseDiff = [2, 5];

这种表示的优点是 denseDiff.length 会告诉我们一个直截了当的事实，即两个元素发生了变化。缺点是我们无法知道被改变的元素的原始索引是什么。

sparse方式比较复杂：

const sparseDiff = [, 2, , , 5];

sparseDiff.length，也就是5，不再告诉我们变化的元素个数。相反，它仅传达已更改元素的最高索引。此外，如果我们在0和sparseDiff.length之间取一个没有变化的索引，例如sparseDiff[3]，它总是告诉我们undefined，其含义是不清楚。

这里有很多混淆的空间，这在编程中通常不是一件好事。然而，稀疏方式的主要优点是更改元素的索引在 oldArr 和 sparseDiff 之间始终相等。也就是说，我们为每个索引维护以下不变量 i:

oldArr[i] == newArr[i] ? sparseDiff[i] == undefined : sparseDiff[i] == oldArr[i]

幸运的是，我们还有一种方法可以直接找到哪些索引对应于变化的元素。 _.keys（或Object.keys）将告诉我们明确设置的元素的索引（因为它们已更改）：

_.keys(sparseDiff)  // ['1', '4']

_.keys(sparseDiff).length 甚至会告诉我们发生变化的元素数量。我们可以通过密集表示获得所有信息，只是以一种更迂回和混乱的方式。

总而言之，稀疏数组在这里可以说是正确的方法，因为它们使我们能够获得我们可能需要的所有信息。无论如何，我指出了稀疏数组的缺点，以强调仍然存在权衡。

您的代码

在跳到解决方案之前，让我们借此机会尽可能多地学习。您的代码中有几处让我印象深刻。

双外函数

这是我注意到的第一件事：

function difference(oldValues, newValues) {
    function changes(oldValues, newValues) {
        //...
    }

    return changes(oldValues, newValues);
}

difference 函数只是简单地将其参数以相同的顺序转发给 changes，然后回显其 return 值。这意味着 difference 并没有真正做任何事情。您可以删除最外面的 difference 函数，调用 changes 而不是 difference 并仍然得到相同的结果：

function changes(oldValues, newValues) {
    //...
}

_.transform

我注意到的第二件事是您正在使用 _.transform。如果我们看看这个函数是如何构思出来的，它原来是 _.reduce 的一个变体，它可以通过从被迭代对象 returning false 来提前停止迭代。由于迭代器必须能够 return false 但我们还必须能够在最后获得结果，这意味着迭代器必须就地修改累加器，而不是 return就像我们在 _.reduce 中所做的那样。这有两个主要问题。

首先，就地修改不适用于字符串等不可变值。因此，_transform 仅适用于对象和数组。考虑以下函数来反转字符串，它可以与 _.reduce 一起使用但不能与 _.transform 一起使用：

function reverse(string) {
    return _.reduce(string, (result, char) => char + result);
}

您可以通过将 result 包装在一个对象中然后再展开它来解决这个问题，但这意味着您正在解决 _.transform 而你应该首先使用 _.reduce。

其次，也是更重要的一点，部分变换对象毫无意义。对象的键是无序的。假设在迭代过程中，您找到了特定键的停止条件。纯属巧合，其他一些键已经被访问过，而另一些还没有。没有合理的理由说明为什么已经访问过的键应该成为转换结果的一部分而其他键不应该，因为这种划分完全是任意的。

_.transform 对不可变值无用，对无序集合无意义。有序集合、数组怎么样？乍一看，在某些合理的情况下，您可能希望部分转换数组。例如，要计算从一开始就对数组中的数字求和可获得的高于阈值的最小数字：

function thresholdPartialSum(numbers, threshold) {
    return _.transform(numbers, function(result, number) {
        result.wrapped += number;
        return result.wrapped <= threshold;
    }, { wrapped: 0 }).wrapped;
}

注意 wrapped 出现在四个地方。我们正在解决 _.transform 必须在此处修改累加器的限制。

诚然，在这种情况下，_.transform 比 _.reduce 具有性能优势。但是，我们都不需要。部分迭代数组已经被很好的旧 _.find 和类似函数处理得很好。此外，由于无论如何我们都必须就地修改累加器，我们不妨关闭它。 _.find 将像 _.transform 一样处理这些情况，但复杂性较低：

function thresholdPartialSum(numbers, threshold) {
    let partialSum = 0;
    find(numbers, function(number) {
        partialSum += number;
        return partialSum > threshold;
    });
    return partialSum;
}

总之，您应该永远不要使用_.transform。请改用 _.reduce 或 _.find。

重复递归

这是我注意到的第三件事：

if (!_.isEqual(value, oldValues[key])) {
    // recursion here
}

虽然这不会导致不正确的结果，但 _.isEqual 本身是递归的。它的 return 值基于是否发现任何差异。这意味着当发现差异时，您最终会再次递归地迭代这两个值，只是为了找回 _.isEqual 已经识别但没有告诉您位置的差异。

乍一看，这似乎没什么问题。您可能会递归两次而不是一次。不是最高效的，但最多慢两倍，对吧？不幸的是，重复并不止于此。一旦你递归调用你自己的 changes 函数，_.isEqual 将再次为你递归到的元素的每个子元素调用，并且它将再次递归 .

为了量化这一点，让我们首先将嵌套对象想象成一棵树。

const tree = {
    mainBranch1: {
        branch1_1: {
            twig1_1_1: {
                leaf1_1_1_1: 'value 1.1.1.1',
                leaf1_1_1_2: 'value 1.1.1.2',
            },
            twig1_1_2: {
                leaf1_1_2_1: 'value 1.1.2.1',
                leaf1_1_2_2: 'value 1.1.2.2',
            },
        },
        branch1_2: {
            twig1_2_1: {
                leaf1_2_1_1: 'value 1.2.1.1',
                leaf1_2_1_2: 'value 1.2.1.2',
            },
            twig1_2_2: {
                leaf1_2_2_1: 'value 1.2.2.1',
                leaf1_2_2_2: 'value 1.2.2.2',
            },
        },
    },
    mainBranch2: {
        branch2_1: {
            twig2_1_1: {
                leaf2_1_1_1: 'value 2.1.1.1',
                leaf2_1_1_2: 'value 2.1.1.2',
            },
            twig2_1_2: {
                leaf2_1_2_1: 'value 2.1.2.1',
                leaf2_1_2_2: 'value 2.1.2.2',
            },
        },
        branch2_2: {
            twig2_2_1: {
                leaf2_2_1_1: 'value 2.2.1.1',
                leaf2_2_1_2: 'value 2.2.1.2',
            },
            twig2_2_2: {
                leaf2_2_2_1: 'value 2.2.2.1',
                leaf2_2_2_2: 'value 2.2.2.2',
            },
        },
    },
};

我们有一棵有四级分支的树（不包括 tree 本身）。有十六片叶子。

递归将在 leaf 键处停止，所以让我们数一数 _.isEqual 访问叶键的次数。假设我们将 tree 与另一个具有相似结构的对象进行比较，并且大约一半的叶值已更改。

首先，我们在 tree 和另一个对象上调用 changes。我们为每个 mainBranch 调用一次 _.isEqual。 _.isEqual 递归调用自身直到到达叶键。它需要访问大约一半的叶子才能找到差异，此时它知道它必须 return false。至此，我们平均访问了每片叶子一半的时间。

每_.isEqualreturnsfalse，我们在对应的主分支上递归调用changes。每次调用 changes 然后为每个 branch 调用一次 _.isEqual。 _.isEqual 再次递归调用自身，直到到达叶键。现在我们平均访问了每片叶子一次。

_.isEqual again returns false 每次，所以我们再次递归到 changes 。整个模式重复，我们每片叶子访问一次半。

我们最终用 twig 再次重复整个模式，最终平均每个叶键调用两次 _.isEqual。这意味着在叶键上总共 16 * 2 = 32 次 _.isEqual 调用。每个叶子的调用总数等于树的深度乘以叶子的数量，再除以二。在复杂性分析中，我们称其为对数线性或拟线性 time.

这是最坏的情况。如果少于一半的叶子不同，changes 将减少递归的频率，而如果超过一半的叶子不同，_.isEqual 将更快地停止自己的递归。然而，如果没有重复递归，我们只需要访问每个叶子一次，而不管树的深度如何。毕竟我们在判断某个key是否发生变化的时候，还不如直接记录差异。对于大型、深层嵌套的结构，这可能会有很大的不同，特别是如果它发生在热循环中。

去除重复需要我们将算法从前序遍历更改为post序traversal。也就是说，我们不必先确定与较大分支是否存在任何差异，然后在其每个较小分支中找出这些差异，而是必须直接收集最小分支内的所有差异。如果我们在较小的分支中发现任何差异，我们就会知道我们还应该记录包含的较大分支。

解决方案

足够的理论。以下代码解决了我上面讨论的问题，适用于对象和数组。无论您使用的是 Underscore 还是 Lodash，它都有效。

function changes(oldCollection, newCollection) {
    return _.reduce(oldCollection, function(result, oldValue, key) {
        const newValue = newCollection[key];
        if (_.isObject(oldValue) && _.isObject(newValue)) {
            const diff = changes(oldValue, newValue);
            if (!_.isEmpty(diff)) result[key] = diff;
        } else if (oldValue !== newValue) {
            result[key] = { oldValue, newValue };
        }
        return result;
    }, _.isArray(oldCollection) ? [] : {});
}

最后的评论

与原始问题一样，由 changes 编辑的 diff 对象 return 包含每个更改的叶键的嵌套 {oldValue, newValue} 对象。如果旧对象或新对象包含名称为 oldValue 或 newValue 的键，这可能会导致歧义。这并不像看起来那么疯狂。考虑比较两个不同时间点的差异。

为避免这种情况，您可以选择在差异中仅存储旧值（或仅存储新值）。由于您知道更改值的确切位置，因此在其他对象中查找相应的键将变得微不足道。您只需更改一行即可使算法以这种方式运行，但这留作 reader.

的练习。

同样与原始问题一样，上述解决方案没有考虑到新集合可能具有旧集合中不存在的新键。如果你想检测新键并且你可以接受删除的键将被遗漏，只需迭代 newCollection 而不是 oldCollection。如果两边都需要补缺键，先通过判断常用键和非常用键。常用键如上处理，不常用键直接记录为差异。这再次作为练习留给 reader.

更新：检测删除和添加的元素

在上面的“最后的评论”中，我评论说我上面的解决方案与原始问题一样，没有检测到对象和数组中新添加的元素。 Ankur Sharma 评论说，这实际上是他在问题中寻求解决方案的问题之一。为了解决这个问题，下面是我的解决方案的新版本。

下面的代码采用下划线。对于 Lodash 4，使用 _.mapValues 而不是 _.mapObject.

// Helper for the call to _.mapObject/_.mapValues below.
const wrapAddedKey = newValue => ({ oldValue: undefined, newValue });

function changes(oldCollection, newCollection) {
    const diff = _.reduce(oldCollection, function(result, oldValue, key) {
        const newValue = newCollection[key];
        if (_.isObject(oldValue) && _.isObject(newValue)) {
            const diff = changes(oldValue, newValue);
            if (!_.isEmpty(diff)) result[key] = diff;
        } else if (oldValue !== newValue) {
            result[key] = { oldValue, newValue };
        }
        return result;
    }, _.isArray(oldCollection) ? [] : {});
    const addedKeys = _.difference(_.keys(newCollection), _.keys(oldCollection));
    const additions = _.pick(newCollection, addedKeys);
    return _.extend(diff, _.mapObject(additions, wrapAddedKey));
}

更新 2

从问题的另一次更新中可以看出，提问者想要将缺失值表示为 null 而不是 undefined。以下代码解决了这个问题。

// Helper for the call to _.mapObject/_.mapValues below.
const wrapAddedKey = newValue => ({ oldValue: null, newValue });

function changes(oldCollection, newCollection) {
    const diff = _.reduce(oldCollection, function(result, oldValue, key) {
        const newValue = key in newCollection ? newCollection[key] : null;
        if (_.isObject(oldValue) && _.isObject(newValue)) {
            const diff = changes(oldValue, newValue);
            if (!_.isEmpty(diff)) result[key] = diff;
        } else if (oldValue !== newValue) {
            result[key] = { oldValue, newValue };
        }
        return result;
    }, _.isArray(oldCollection) ? [] : {});
    const addedKeys = _.difference(_.keys(newCollection), _.keys(oldCollection));
    const additions = _.pick(newCollection, addedKeys);
    return _.extend(diff, _.mapObject(additions, wrapAddedKey));
}

使用 lodash 或下划线或 vanilla js 查找嵌套对象数组之间的深层差异

Find deep difference between nested array of object with lodash or underscore or vanilla js

javascript

arrays

lodash

underscore.js