Быстрое удаление элемента из массива

Рич Харрис — автор Svelte, Shimport и других библиотек — сегодня твитнул про свою интересную находку в коде three.js.

Если вам нужно удалить один элемент из массива, можно воспользоваться array.splice(index, 1). Но если у вас огромный массив, то splice() будет работать очень медленно, так как будет происходить сдвиг всех элементов (линейная сложность).

Для тех массивов, где порядок элементов не важен, разработчики three.js используют такой код для удаления элемента:

array[index] = array[array.length - 1];
array.pop();

То есть здесь удаляемый элемент заменяется последним элементом массива и последний элемент удаляется (константная сложность).

В комментариях к твиту пишут, что при разработке на ассемблере для RISC-процессора PlayStation 1 подобный трюк был очень распространён.

https://twitter.com/rich_harris/status/1125850391155965952?s=21

← Home