JavaScript объекты как хеши? Сложность больше, чем O(1)?
Для какого-то алгоритма, который я недавно писал, я думал, что хеш будет превосходным. Я подумал, что, возможно, я мог бы просто использовать переменные-члены в объекте в качестве пар ключ-значение. Я не уверен, что это оптимально, так как я действительно не знаю, что происходит за кулисами. Я также предполагаю, что V8 делает это не так, как в других средах. Однако я действительно представляю, что поиск переменных-членов будет довольно быстрым (надеюсь)?
Тем не менее, мне интересно, все ли сложности времени написания, чтения, создания и удаления переменных-членов в объектах JavaScript - все это O(1). Если есть различия в окружающей среде (v8 против других), что они?
3 ответа
ОБНОВИТЬ
Удаление Chrome теперь действительно быстро; Однако, когда вы приближаетесь к миллиону ключей, обновление кажется медленным.
Хорошо, у меня есть некоторые данные. Я собираюсь сказать, да, есть различия между браузерами. Кажется, что разные среды заботятся о разных операциях CRUD. Кроме того, объекты - это хеши под капотом, так как производительность увеличивается, когда количество клавиш увеличивается. Если между тремя тестами нет разницы в производительности (ops/sec), то (я думаю) это означает, что это хеш, а сложность каждой операции равна O(1), независимо от того, быстрее ли она или медленнее по сравнению с другими операциями. Другими словами, если при увеличении количества ключей в каком-либо тесте учитывалось число операций в секунду, то это не O(1) (это не так).
тесты:
http://jsperf.com/objectsashashes/2 (100 ключей)
http://jsperf.com/objectsashashes/3 (100 тыс. ключей)
http://jsperf.com/objectsashashes/ (1 миллион ключей)
http://jsperf.com/objects-as-hashes-300-mil (ключи 10 м)
Замечания:
- Время создания пар линейно через пары ключей-значений 10 мил.
- Chrome: оптимизирован для чтения. Создание и обновление немного медленнее.
- Safari: оптимизирован для записи, но чтение выполняется довольно быстро. Медленнее обновлять вроде.
- IE9: не поддерживает ни одну из операций. Удалить дает чуть лучшую производительность. Примечание: я использовал более старую машину для тестирования.
- IE10: удаление дает чуть лучшую производительность. Создание / обновление медленнее, чем чтение.
- IE8: не удалось протестировать, но с последними обновлениями win7 кажется, что IE9 был установлен автоматически. Не уверен насчет машин XP.
- Firefox: оптимизирован для чтения. Все остальное примерно одинаково.
- Опера: Все операции выполняются с одинаковой скоростью.
- Кажется, единственные ограничения на максимальное количество хранимых ключей основаны на памяти (браузер, среда или машина).
Финальные заметки:
Хотя хеш ['что-то'] не медленнее, чем hash.something, если вам нужно объединить, чтобы найти имя вашего хэша, ваша производительность резко снижается ( http://jsperf.com/member-associative-array-syntax-vs-dot-syntax), поэтому я кэшировал эти значения вне тестов производительности, описанных выше. Избегайте объединения, если это возможно. Строки являются неизменяемыми в JS, и в результате каждая конкатенация создает 3 объекта / "примитива" (строка 1, строка 2 и объединенная строка).
Объекты JavaScript - это хеши. Я не могу представить ни одной разумной реализации, которая бы не обеспечивала CRUD-операции с постоянным временем над свойствами объекта.
Вы видите конкретные проблемы с производительностью с этим подходом?
Объекты в JavaScript являются примером хеш-таблицы, поскольку данные объекта представлены как ключи и значения.