使用reduce或forEach合并数组去重：哪种实现性能更优？

场景与现有实现 #

原始forEach实现 #

const getNewState = (state, messages) => {
    const messagesToMerge = [];

    messages.forEach((message) => {
        const alreadyInState = state.find((messageInState) => messageInState.id === message.id);

        if (!alreadyInState) {
            messagesToMerge.push(message);
        }
    });

    return [...messagesToMerge, ...state];
}

调用示例 #

const state = [
    { id: 1, text: 'text 1' },
    { id: 2, text: 'text 2' },
    { id: 3, text: 'text 3' },
];

const newState = getNewState(state, [
    { id: 1, text: 'text 1' },
    { id: 4, text: 'text 4' },
]);

预期结果 #

[
    { id: 1, text: 'text 1' },
    { id: 2, text: 'text 2' },
    { id: 3, text: 'text 3' },
    { id: 4, text: 'text 4' }
]

你的reduce实现 #

const getNewState = (state, messages) => {
    const messagesToMerge = messages.reduce((acc, message) => {
        const alreadyInState = acc.find((messageInState) => messageInState.id === message.id);

        if (!alreadyInState) {
            acc.push(message);
        }

        return acc
    }, state);

    return [...messagesToMerge, ...state];
}

性能对比：forEach vs reduce #

你的猜想不正确：reduce的初始值state是按引用传递的，并没有被克隆，acc就是state本身的引用，不存在克隆带来的性能损耗。

从性能角度看，forEach和reduce的底层执行逻辑几乎一致，两者的性能差距可以忽略不计。真正拖慢速度的是代码里的find操作——每次find都要遍历整个state数组，时间复杂度是O(n)，当处理10000条消息时，整体时间复杂度会达到O(m*n)（m是messages长度，n是state长度），这才是性能瓶颈。

另外要注意：你的reduce实现存在bug——因为acc是state的引用，在reduce里执行acc.push(message)会直接修改原始的state数组，导致外部的state被意外修改，违背了纯函数的原则，而forEach实现不会修改原始state，这是两者的关键区别。

更优的实现方式 #

要解决性能瓶颈，核心是把find的O(n)查找变成O(1)的查找，我们可以用Set来存储state中已有的id：

const getNewState = (state, messages) => {
    // 先把state的id存入Set，O(n)时间
    const existingIds = new Set(state.map(item => item.id));
    // 过滤messages中不在state里的项，O(m)时间
    const newMessages = messages.filter(msg => !existingIds.has(msg.id));
    // 合并新消息和原state，匹配预期结果顺序
    return [...state, ...newMessages];
}

这个实现的时间复杂度是O(m + n)，相比原来的O(m*n)，在数据量大时性能提升非常明显，同时也不会修改原始state，符合纯函数的要求。

内容的提问来源于stack exchange，提问作者Mike K