Развитие языка JavaScript постепенно переносит всю тяжесть вычислений с одного сервера на сеть пользовательских компьютеров. Это супер-хорошо. Программирование на стороне сервера вынуждает очень тщательно оптимизировать код по быстродействию и занимаемой памяти, в это же время разработка клиентской части несколько отстает.
Часто для удобного и быстрого кодирования применяют специализированные структуры данных. Именно так и поступают при разработке на Java:
https://habr.com/ru/post/237043/
А вот для подобной работы с JavaScript оптимизированных инструментов по умолчанию не предоставляется. Реализация Array(), Set() и Map() перекладывается на плечи разработчиков браузерных движков, а их разработки на сегодняшний день очень далеки от оптимальности:
https://habr.com/ru/company/ruvds/blog/518032/
Зададимся вопросом — а что если требуются прямо сейчас действительно оптимальные по производительности и памяти структуры данных. Какой минимальный набор достаточно таких структур надо реализовать и поддерживать? Один из вариантов ответа — это сделать двунаправленный связный список и сбалансированное дерево поиска.
Что это нам даст?
Реализуя связный список LinkedList мы получаем сразу список, двунаправленную очередь и стек. И если это сделать без JavaScript Array(), а лишь используя простые ссылки на объекты, то получаем стандартную и достаточно оптимальную структуру данных.
Если же сделать бинарное сбалансированное дерево поиска TreeMap, например AVL-дерево:
https://habr.com/ru/post/150732/
тогда используя его можно получить следующие структуры данных:
1) Array = TreeMap.get(i) — стандартный массив, кроме того AVL-дерево может выдать нам уже отсортированный массив.
2) Set = TreeMap.set(element, counter) — множество уникальных элементов.
3) Map = TreeMap.set(key, value) — стандартная структура типа ключ-значение
4) MinHeap и MaxHeap — минимальная и максимальная кучи, они же очереди с приоритетами.
5) Matrix = TreeMap.get(«i_j») и Tensor = TreeMap.get(«i_j_k»): простые операции преобразования индексов в строку и обратно ([i, j, k] = «i_j_k») дают нам оптимальные по размерам памяти многомерный матрицы, можете забыть о разреженности матриц.
6) List — теоретически структуру можно получить если использовать в качестве ключей дробные числа, тогда вставка элемента между i и j будет такая: TreeMap.set((i+j)/2, element)
7) SearchTree — ну и собственно дерево поиска, тоже нам пригодится.
Все операции в TreeMap достаточно оптимальны, порядка O(log(n)).
Вот минимально необходимый интерфейс структуры TreeMap:
/* интерфейс */
class TreeMap {
tree;
constructor() {
//интерфейс можно дополнять своими функциями - он отделен от реализации:
this.tree = new AVLTree();
}
get(key) {...}
set(key, value) {...}
delete(key) {...}
getMinKey() {...}
popMinKey() {...}
getMaxKey() {...}
popMaxKey() {...}
next(key) {...} //элемент следующий за элементом-с-ключом=key
previous(key) {...} //элемент перед элементом-с-ключом=key
has(key) {...}
keys() {...}
toArray() {...}
clear() {...}
}
/* реализация */
class AVLTree {...}Исходные коды доступны по ссылке, лицензия свободная: