Skip to content

Instantly share code, notes, and snippets.

@Rich-Harris
Last active May 6, 2024 10:29
Show Gist options
  • Save Rich-Harris/50ff201552a8ca8bc1492dd570ecac07 to your computer and use it in GitHub Desktop.
Save Rich-Harris/50ff201552a8ca8bc1492dd570ecac07 to your computer and use it in GitHub Desktop.
Testing array.splice vs array.pop vs set.delete

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();
@flcoder
Copy link

flcoder commented Dec 27, 2020

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.

@erhangundogan
Copy link

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment