JavaScript быстрее сдвиг, unshift и сращивания реализация

Question

Я прочитал эту статью:

https://gamealchemist.wordpress.com/2013/05/01/lets-get-those-javascript-arrays-to-work-fast/

В конце пункта 6 автор говорит:

Rq о сдвиге/unshift: берегитесь, это всегда операции O (n) (что означает: каждая операция будет занимать время пропорционально числу длины массива). Если вам это действительно не нужно, вы не должны использовать их . Скорее создайте свой собственный вращающийся массив, если вам нужна такая функция.

А в 7-м пункте:

Rq для сдвига/unshift пользователей: применить тот же принцип, с двумя индексами, чтобы избежать копирования/перераспределении. Один указатель слева, один справа на , начиная с середины массива. Затем вы снова будете в O (1) раз. Лучше. Не забудьте повторно центрировать индексы, когда они ==.

Мне было интересно, что означает автор, когда он говорит build your own rotating array и two indexes,...One index on the left, one on the right, both starting at the middle of the array. Как должны быть эти соображения переведены в код (автор не делает пример для этих случаев использования)?

Могут ли принципы применяться к shift и unshift также применимы к Array.prototype.splice?

РЕДАКТИРОВАТЬ: У меня есть упорядоченный массив x координат происходят из индексов 0 (более низких значений для x) до n (более высоких значений x). Мне нужно будет использовать myArray.splice(index, 0, item); несколько раз и вставить некоторые новые координаты x между уже существующими, если эта координата < более высокой и > более низкой (я могу легко найти это через двоичный поиск), и я не знаю, t хочу, чтобы он менял порядок индексов каждый раз, когда я вызываю splice. У меня есть тысячи элементов в массиве myArray. Можно ли его улучшить, используя принципы, упомянутые автором связанной статьи?

Спасибо за внимание.

Answer 1

На все вопросы, связанные с производительностью, следует ответить, кодируя очень конкретное решение, а затем измеряя производительность этого решения по сравнению с вашей альтернативой с репрезентативными данными в браузерах, о которых вы заботитесь. Очень мало вопросов о производительности, на которые можно ответить точно с абстрактным вопросом, который не включает точный код для измерения.

Есть некоторые элементы здравого смысла, например, если вы собираетесь поместить 1000 элементов в массив, то да, вероятно, быстрее перенаправить массив на конечную длину, а затем просто заполнить значения массива, а не называть .push() 1000 раз. Но, если вы хотите знать, какая разница и действительно ли она актуальна в вашей конкретной ситуации, вам нужно будет скопировать два сравнения и измерить их в нескольких браузерах в таком инструменте, как http://jsperf.com.

Рекомендация в этой статье для создания вашей собственной функции .splice() кажется подозрительной для меня без измерения. Похоже, что хорошая нативная версия кода .splice() может быть быстрее, чем одна полностью написанная в Javascript. Опять же, если вы действительно хотите знать, вам нужно будет измерить конкретный тестовый пример.

Если у вас есть масса манипуляций с массивами, и вы хотите закончить сортированный массив, возможно, быстрее удалить элементы, добавить новые элементы в конец массива и позвонить .sort() с помощью специального сравнения когда вы делаете, а не вставляете каждый новый элемент в отсортированном порядке. Но, опять же, какой путь быстрее будет зависеть полностью от того, что вы делаете, как часто вы это делаете и какие браузеры вам больше всего нравятся. Измерьте, измерьте, измерьте, если вы действительно хотите знать.

Что касается улучшения вашей конкретной ситуации в вашем редакторе с помощью настраиваемого .splice(), вам придется закодировать его в обоих направлениях с помощью репрезентативного набора данных, а затем проверить в инструменте, таком как perf, в нескольких браузерах, чтобы ответить на вопрос. Поскольку вы не предоставляете код или данные для тестирования, никто из нас не может действительно ответить на этот вопрос для вас. Существует не общий ответ, который работает для всех возможных применений .splice() на всех возможных наборах данных во всех возможных браузерах. Дьявол находится в деталях, и детали находятся во всей специфике вашей ситуации.

Я предполагаю, что если вы действительно настроите настройку производительности, вы часто найдете большую рыбу, чтобы поджарить, чтобы сделать ваш общий алгоритм более умным (поэтому на нем меньше работы, чем в первую очередь), чем путем перезаписи методов массива , Цель состоит в том, чтобы проверить/измерить достаточно, чтобы понять, где ваши узкие места в производительности действительно так, чтобы вы могли сосредоточиться на одной области, которая делает наибольшую разницу, и не тратить много времени на угадывание того, что может ускорить работу. Я всегда буду кодировать интеллектуальное использование существующих методов массивов и рассматривать только заказное кодированное решение, когда я доказал себе, что у меня есть узкое место в одной конкретной операции, которая действительно имеет значение для моего приложения. Перспектива просто сделает код более сложным и менее ремонтопригодным и, как правило, будет потрачен на меньшее время.