То есть, было бы лучше, если бы я использовал какую-то структуру данных дерева или списка пропусков, если мне нужно многократно вызывать эту функцию для отдельных вставок массива?Javascript: Что такое алгоритмическое исполнение «сращивания»?
Вы можете подумать, хотите ли вы использовать прямую карту; все объекты JavaScript (включая Array экземпляры) являются картами, поэтому реализация должна (обратите внимание, что я не говорю «делает») имеют разумный алгоритм хэширования производительности.
Кроме того, производительность splice будет варьироваться от до между реализациями (например, поставщиками). Это одна из причин, почему «не оптимизировать преждевременно» - это еще более подходящий совет для приложений JavaScript, которые будут выполняться в нескольких версиях поставщиков (например, в веб-приложениях), чем это даже для нормального программирования. Сохраняйте свой код хорошо модульным и обращайтесь к проблемам производительности, если и когда они происходят.
Проблема с картой - я не думаю, что могу перебирать ее в отсортированном порядке ... – Hamster
@Hamster: Вы можете, но только найдя все ключи, отсортировав их, а затем перейдя через этот список. Если вам нужно сделать это много, то вам, вероятно, будет лучше с «Array» (который в JavaScript, в конце концов, представляет собой только карту с определенным порядком и магическим свойством 'length'). –
@ T.J.Crowder Что делать, если мне нужно часто вставлять элемент по определенному индексу между уже существующими элементами (т. Е. Сохранять их и переупорядочивать индексы), и есть тысячи элементов? Я знаю, что могу сделать это с помощью 'splice', но является ли' Array' с 'splice' правильной структурой данных для такой задачи? Если нет, то какая другая структура данных JS может быть подходящей для этого? – tonix
Это хорошее эмпирическое правило, основанное на тестах, выполненных в браузере Chrome, Safari и Firefox: объединение одного значения в середину массива примерно равно с точностью до, так как нажатие/перенос значения на один конец массив. (Примечание: Только протестирована на массив размером 10000.)
http://jsperf.com/splicing-a-single-value
Это довольно быстро. Таким образом, маловероятно, что вам нужно зайти так далеко, чтобы реализовать другую структуру данных, чтобы выжать больше производительности.
Обновления: Как электронный бизнес указует в комментариях ниже, тест выполняет дорогую операцию копирования вместе с каждым splice, push и shift, что означает, что занижает разницу в производительности. Вот пересмотренный тест, который позволяет избежать копирования массива, поэтому она должна быть гораздо более точным: http://jsperf.com/splicing-a-single-value/19
Фактически, он полностью зависит от длины массива. Если вы перейдете на массив из 100 000 элементов, то сплайсинг значения в середине будет на 95% медленнее, чем добавление значения в конце, как измерено вашим тестом jsperf. Это потому, что вставка в середине - это O (n) в размере массива, а вставка в конце может быть O (1). – Geoff
-1 Этот тест jsperf загрязнен копированием массива, он в основном измеряет время, необходимое для создания целого нового массива элементов 10000. – aaaaaaaaaaaa
@eBusiness Пожалуйста, подробно остановитесь на своем заявлении. Где в тестах массив копируется? –
Переместить одно значение
// \t tmp = arr[1][i];
// \t arr[1].splice(i, 1); \t // splice is slow in FF
// \t arr[1].splice(end0_1, 0, tmp);
\t tmp = arr[1][i];
\t ii = i;
\t while (ii<end0_1)
\t \t {
\t \t arr[1][ii] = arr[1][++ii];
cycles++;
\t \t }
\t arr[1][end0_1] = tmp;
Попробуй! Это лучший способ ответить на этот вопрос ... – Harmen
Каков хороший способ проверить это? – Hamster
Если массивы JavaScript действительно массивы, это O (n). – Gumbo