Testing array.splice vs array.pop vs set.delete

README.md

You have an array. Its sort order doesn't matter. You want to remove an item from this array.

The obvious thing to do would be to use splice:

function remove(array, item) {
  const index = array.indexOf(item);
  array.splice(index, 1);
}

But there's a much faster way:

function remove(array, item) {
  const index = array.indexOf(item);
  array[index] = array[array.length - 1];
  array.pop();
}

In my tests this is signficantly faster with large arrays, and never slower.

The fastest approach of all, though, is to use a set rather than an array:

set.delete(item);

You can test for yourself by running this code in your console. Note that the bulk of the time is spent in indexOf, and this test makes finding an index as slow as possible:

function test(size = 10000) {
  const array = [];
  for (let i = 0; i < size; i += 1) {
    if (i % 2 === 0) {
      array.push(i);
    } else {
      array.unshift(i);
    }
  }

  const set = new Set(array);

  function with_splice() {
    const clone = array.slice();
    console.time('with splice');
    for (let i = 0; i < size; i += 1) {
    const index = clone.indexOf(i);
      clone.splice(index, 1);
    }
    console.timeEnd('with splice');
  }

  function with_pop() {
    const clone = array.slice();
    console.time('with pop');
    for (let i = 0; i < size; i += 1) {
      const index = clone.indexOf(i);
      clone[index] = clone[clone.length - 1];
      clone.pop();
    }
    console.timeEnd('with pop');
  }

  function with_set() {
    console.time('with set');
    for (let i = 0; i < size; i += 1) {
      set.delete(i);
    }
    console.timeEnd('with set');
  }

  with_splice();
  with_pop();
  with_set();
}

test();

Considering a real world scenario with multiple insertions/removals and attempts to remove elements not in the list, a Set is 💯times better.

While I suppose the test leads one to the right conclusion, I have 3 issues with it:

1. It is removing every element in the list from beginning to end which is likely something one would never do in a real world scenario. To do so, one would simply arr.length = 0 or set.clear().

2. Alternating push/unshift while setting up the list is not accomplishing anything; it doesn't matter what or where the elements are.

3. It doesn't check if the element is in the list or not. Consider removing an element that isn't in the list; an implementation using an array will need to first confirm arr.indexOf(element) > -1 or else the array could be ruined. Confirming this will make the function as much as 100 times slower.

I think const set = new Set(array); and const array = Array.from(set) should move into the with_set function if you would like to keep inputs/outputs same type which is array. But still result won't change Set is blazing fast.