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

[Carduelis]

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

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

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

Спасибо!

[ermouth]

Смотря для чего использовать. Это сразу видно из сравнения (консоль Хрома, Макось, 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]

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

[Alexandroppolus]

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

[Alexandroppolus]

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

[anudas]

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

[aleks_raiden]

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

[anudas]

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

[Alexandroppolus]

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

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

[idneutrino24]

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