Question 276914 in Javascript Question posted in
A very good W3school tutorial can be found here.

Javascript – Using `reduce` or a ` forEach` as the most efficient way of merging an element into an array if it doesn't exist already

Suppose the following:

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];
}

I would call the above like so:

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'
    },
]);

The expected result:

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

Initially, however, I was using 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];
}

My question is which of these two is faster? I ask because I’d imagine that even though state is passed by reference to reduce, it’s still cloned to be come the acc, and if there are, say 10,000 messages, then it must be slower that a simple forEach, right? Am I on the right track here or is there an altogether even better way of approaching this?

Tags:

3

Answers


  1. 0

    A more optimal solution: grab the IDs in the state into a set, and then filter them out:

    function getNewState(state, messages) {
  const idsInState = new Set(state.map((message) => message.id));
  const messagesNotInState = messages.filter((message) => !idsInState.has(message.id));
  return [...messagesNotInState, ...state];
}
    Login or Signup to reply.
  2. 0

    When you want to know what is the faster, as AKX said, just test it

    I wrote the three tests in JsPerf here:

    • forEach
    • reduce
    • AKX solution

    The results are
    enter image description here

    EDIT: As AKX said, with a bigger amount of data (state 50 items, and 70 in stateToMerge), the fastest is the Set solution, and forEach is the slower

    Login or Signup to reply.
  3. 0

    In order to actually measure them, you can loop with an index up to a very large number of your choice, perform both algorithms in the exact same amount and add up the times used for them. Then, compare the sums:

    let state = [
    {
        id: 1,
        text: 'text 1'
    },
    {
        id: 2,
        text: 'text 2'
    },
    {
        id: 3,
        text: 'text 3'
    },
];
let stateJSON = JSON.stringify(state);
const getNewState1 = (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 getNewState2 = (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];
}

let timeElapsed1 = 0;
let timeElapsed2 = 0;

for (let index = 0; index < 1000000; index++) {
    state = JSON.parse(stateJSON);
    let start = new Date();
    getNewState1(state, [
        {
            id: 1,
            text: 'text 1'
        },
        {
            id: 4,
            text: 'text 4'
        },
    ])
    let end = new Date();
    timeElapsed1 += end - start;
    start = new Date();
    getNewState2(state, [
        {
            id: 1,
            text: 'text 1'
        },
        {
            id: 4,
            text: 'text 4'
        },
    ])
    end = new Date();
    timeElapsed2 += end - start;
}

console.log("getNewState1: " + timeElapsed1 + " getNewState2: " + timeElapsed2);

    For me, the sum was:

    getNewState1: 672 getNewState2: 705

    You have an inner find, so the complexity is n * m, where n is the outer size and m is the size of data for which you run .find.

    However, whatever the result, the first approach is superior, because the second modifies your array and prevents you from reusing it.

    You can optimize your algorithm of course, but for the purpose of this question, you were wondering about the comparison of the two algorithms.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search