idneutrino24 Sep 26 2021 at 16:27

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

3 min

5.7K

Comments 13

Carduelis Sep 26 2021 at 16:42

А не могли бы вы сравнить производительность данного решения с текущими реализациями в nodejs, webkit, gecko,blink?

Возьмем, например, пример из жизни: таблица с 10к строками, данные в которой нужно отфильтровать на клиенте.

Конечно, на таких малых значениях использование альтернативных структур данных избыточно. Но в каких случаях это оправданно?

Спасибо!

UFO landed and left these words here

ermouth Sep 26 2021 at 20:06

Смотря для чего использовать. Это сразу видно из сравнения (консоль Хрома, Макось, 4.2ГГц х86):
for (var l1 = [], i = 0; i<100000; i++) i%2?l1.unshift(i):l1.push(i); – примерно 160мс
for (var l0 = new LinkedList(), i= 0; i<100000; i++) i%2?l0.addFirst(i):l0.addLast(i); – примерно 35мс

Причём если увеличить к-во итераций в 10 раз, для списка это займёт в 10 раз больше времени, а вот для массива – уже в 100.

JustDont Sep 27 2021 at 10:22

Так вы что с чем сравниваете? Это и так заведомо известно, что реализация LL (самая примитивнейшая даже) будет быстрее на вставку с краев, чем массив.

Alexandroppolus Sep 27 2021 at 10:53

Насчёт вставки в конец массива нельзя сказать наверняка. Если там ещё есть резерв, то массив может и побыстрее быть. Хотя с js-ными "массивами" ничего не понятно.

UFO landed and left these words here

Alexandroppolus Sep 27 2021 at 12:33

Ага, спасибо. Ну собственно, всё как при использовании массива для стека. Сейчас запустил пример @ermouth с массивом, 196 мс. Если поменять unshift на push, то 4 мс (для миллиона - 16мс, или 120мс, если вставлять вновь созданные объекты). Пример с LinkedList не трогал (оно не копипастится без номеров строк), но думаю будет не меньше 40мс на 100 тыщах. Так что конец массива прям намного лучше списка.

UFO landed and left these words here

anudas Sep 27 2021 at 13:27

github для опенсорса уже не айс. есть другие места, но и не облако яндекса, конечно же

aleks_raiden Sep 27 2021 at 19:01

хорошая шутка :)

anudas Sep 27 2021 at 23:07

Почему шутка? У каждой нормальной оперсорсной группировки есть свой гибхаб ~~с блэкджеком...~~ на своем серваке и, например, на опенсорсной gitea

Alexandroppolus Sep 26 2021 at 18:49

LinkedList дает неплохую очередь, потому что на массиве она очевидно хреновая. Впрочем, тут вполне подойдет "гибридный" вариант в виде списка массивов - это более экономно. Ну и лучше кольцевой буфер, если максимальное количество известно. Стек лучше делать на массиве.

Насчет дерева - использовать его как массив дурацкая идея. Да и для приоритетной очереди есть варианты лучше. В остальном годная вещь.

idneutrino24 Sep 27 2021 at 01:39

Замечания учитываются и это отражается на тексте статьи. Она корректируется для улучшенного понимания предложенного решения.