Большое число массивов JavaScript

105

Массивы в JavaScript очень легко изменять, добавляя и удаляя элементы. Это несколько маскирует тот факт, что большинство языковых массивов имеют фиксированный размер и требуют сложных операций для изменения размера. Кажется, что JavaScript упрощает написание плохо работающего кода массива. Это приводит к вопросу:

Какую производительность (с точки зрения большой временной сложности) я могу ожидать от реализаций JavaScript в отношении производительности массива?

Я предполагаю, что все разумные реализации JavaScript имеют не более следующих больших О.

  • Доступ - O (1)
  • Добавление - O (n)
  • Подготовка - O (n)
  • Вставка - O (n)
  • Удаление - O (n)
  • Обмен - O (1)

JavaScript позволяет предварительно заполнить массив до определенного размера, используя new Array(length)синтаксис. (Дополнительный вопрос: создает массив таким образом O (1) или O (n)). Это больше похоже на обычный массив, и при использовании в качестве массива с предварительно заданным размером может допускать добавление O (1). Если добавлена ​​логика кольцевого буфера, вы можете добиться начала O (1). Если используется динамически расширяющийся массив, O (log n) будет средним случаем для обоих из них.

Могу ли я ожидать более высокой производительности для некоторых вещей, чем мои предположения? Я не ожидаю, что что-либо будет описано в каких-либо спецификациях, но на практике может случиться так, что все основные реализации используют оптимизированные массивы за кулисами. Используются ли динамически расширяющиеся массивы или какие-то другие алгоритмы повышения производительности?

PS

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

Кендалл Фрей
источник
6
Конструктор Array с размером практически бесполезен в современных реализациях JavaScript. В этой форме с одним параметром он почти ничего не делает. (Он устанавливает, .lengthно это все.) На самом деле массивы мало чем отличаются от простых экземпляров Object.
Pointy
3
Установка lengthсвойства и предварительное выделение пространства - две совершенно разные вещи.
Pointy
1
@Pointy: Я ожидаю слишком многого, когда ожидаю, что настройка array[5]на new Array(10)O (1)?
Кендалл Фрей
1
Хотя ECMAScript не определяет, как реализуется объект Array (он определяет только некоторые семантические правила), вполне возможно, что различные реализации будут оптимизированы для ожидаемых случаев (например, иметь поддержку «реального массива» для массивов размером меньше некоторого n ). Я не настолько разбираюсь в реализации, но был бы очень удивлен, если бы этого где-то не было ...
5
@KendallFrey «Лучший ответ», скорее всего, напишет несколько тестов jsperf для разных шаблонов n / доступа и посмотрим, что из этого

Ответы:

111

ПРИМЕЧАНИЕ. Хотя в 2012 году этот ответ был правильным, сегодня движки используют очень разные внутренние представления как для объектов, так и для массивов. Этот ответ может быть правдой, а может и нет.

В отличие от большинства языков, которые реализуют массивы с массивами, в Javascript массивы являются объектами, а значения хранятся в хэш-таблице, как обычные значения объектов. В качестве таких:

  • Доступ - O (1)
  • Добавление - Амортизированный O (1) (иногда требуется изменение размера хеш-таблицы; обычно требуется только вставка)
  • Предварительный вызов - O (n) через unshift, поскольку он требует переназначения всех индексов
  • Вставка - Амортизируется O (1), если значение не существует. O (n), если вы хотите сместить существующие значения (например, используя splice).
  • Удаление - Амортизировано O (1) для удаления значения, O (n), если вы хотите переназначить индексы через splice.
  • Обмен - O (1)

В общем, установка или отключение любого ключа в dict амортизируется O (1), и то же самое касается массивов, независимо от того, какой индекс. Любая операция, требующая перенумерации существующих значений, - O (n) просто потому, что вам нужно обновить все затронутые значения.

Ник Джонсон
источник
4
Не должно предшествовать O (n)? Так как все индексы нужно сдвинуть. То же самое для вставки и удаления (с произвольным индексом и сдвигом / сворачиванием элементов).
nhahtdh
2
Кроме того, lengthустанавливается мутация массива, или getон получит длину и, возможно, запомнит ее?
Alex
27
Стоит упомянуть, что этот ответ больше не является правильным. Современные движки не хранят массивы (или объекты с индексированными целочисленными ключами) как хэш-таблицы (но, как и ... массивы, как в C), если они не являются разреженными. Для начала здесь является «классическим» эталоном , иллюстрирующим это
Benjamin Gruenbaum
4
Это определено стандартом или это обычная реализация в движках JS? Что насчет V8?
Альберт
4
@BenjaminGruenbaum, было бы неплохо, если бы вы могли немного рассказать о том, как они хранятся. Или дайте какие-то источники.
Ced
1

гарантия

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

реальность

Например, V8 использует (на сегодняшний день) как хэш-таблицы, так и списки массивов для представления массивов. Он также имеет различные представления для объектов, поэтому нельзя сравнивать массивы и объекты. Поэтому доступ к массиву всегда лучше, чем O (n), и может даже быть таким же быстрым, как доступ к массиву C ++. Добавление - O (1), если вы не достигли размера структуры данных и ее нужно масштабировать (что составляет O (n)). Подготовка еще хуже. Удаление может быть еще хуже, если вы сделаете что-то вроде delete array[index](не делайте этого!), Поскольку это может заставить движок изменить свое представление.

совет

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

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

Йонас Вильмс
источник
Подождите секунду, у нас могут быть массивы со смешанными типами данных? Javascript такой классный!
Анураг
@Anurag, но в 99% случаев вам не понадобится эта функция
Desiigner