Структуры данных LinkedList и TreeMap для JavaScript

Развитие языка 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) , TreeMap.set(i, value), TreeMap.keys()} — динамический массив любого размера, правда операция получить список ключей TreeMap.keys() выполняется за O(nlog(n)). Вообще в теоретическом массиве каждое удаление элемента должно сопровождаться сдвигом оставшегося хвоста элементов, но на практике просто оставляют пробелы. Если непрерывность индексации массива вам непринципиальна (некоторые элементы удалены), а важен лишь перебор и порядок — то AVL-TreeMap хорошо итерируется с помощью next(key) и previous(key) или можно обойти дерево рекурсивно в порядке возрастания или убывания ключей inOrder(). Кроме того AVL-дерево может выдать нам отсортированный по ключам массив. Одним словом выходит нечто похожее на PHP-array, только с асимптотикой O(log(n)), хотя O(1) от хэш-таблиц — это очень прикольно:

https://habr.com/ru/post/162685/

2) Set = TreeMap.set(element, counter) — множество уникальных элементов.

3) Map = TreeMap.set(key, value) — стандартная структура типа ключ-значение. Перебор всех элементов в цикле лучше делать через функции next(key) и previous(key) или использовать стандартные обходы деревьев preOrder(), inOrder(), postOrder():

https://habr.com/ru/post/144850/

Глубина рекурсии в AVL-дереве порядка log(n).

4) MinHeap и MaxHeap — минимальная и максимальная кучи, они же очереди с приоритетами. Сложность O(log(n)) — этого достаточно для нормальной работы.

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() {...} /** * Универсальный рекурсивный обход дерева: через все комбинации [узел, правое поддерево, левое поддерево] * @param {function} func - callback функция * @param {type} params - параметры функции * @param {string} order - порядок обхода дерева * @returns {params} - возвращает переданные параметры возможно модифицированные */ traverse(func, params, order) {...} clear() {...}     } /* реализация */  class AVLTree {...}

Исходные коды доступны по ссылке, лицензия свободная:

git clone https://gitflic.ru/project/neutrino/js-collections.git