Comments 9
Расчёты делаете на скалярном процессоре или на x86? Я тут решил полностью на скалярные переехать.
А почему вы выбрали именно AVL?
Да. Я открыл для себя декартово дерево(на хабре есть замечательный цикл статей) — и доволен как слон.
Оно простое и ультрабыстрое.
Оно простое и ультрабыстрое.
Есть еще вот такое дерево vk.com/note5333_11073544, говорят очень быстрое.
+ в данном случае наверняка желательна скорость + маленькая память занимаемая, с этих точек зрения наверное стоит смотреть на RB или splay.
+ в данном случае наверняка желательна скорость + маленькая память занимаемая, с этих точек зрения наверное стоит смотреть на RB или splay.
RB на больших примерах тормознее. splay затрудняюсь оценить. вы прикиньте затраты на построение и на поиск по нему не N*1000 записей, а N*1000000 — порядок другой
одна из причин почему стандартные СУБД под таблицами в миллионы записей ложатся (к примеру mysql) — потому что там для индексов часто используют B дерево с ограниченной высотой, и в листьях слишком много записей получается
одна из причин почему стандартные СУБД под таблицами в миллионы записей ложатся (к примеру mysql) — потому что там для индексов часто используют B дерево с ограниченной высотой, и в листьях слишком много записей получается
хотя — если ваша реализация решает все вопросы, то какая разница будет это B,RB,Heap или любое другое дерево
может это я такой криворукий что моя реализация самого оптимального дерева будет хуже одной самого не оптимального, но которую у меня получилось реализовать случайно — хорошо
короче зависит от конкретных задач — у меня хорошо работает AVL
может это я такой криворукий что моя реализация самого оптимального дерева будет хуже одной самого не оптимального, но которую у меня получилось реализовать случайно — хорошо
короче зависит от конкретных задач — у меня хорошо работает AVL
RB начинает рвать все и вся если совместить ребалансировку с поиском позиции на вставку. Но это получается ограничение по мултизридовости, и интересно когда операций вставок приблизительно столько же, сколько и операций чтений — многовато ограничений. Поэтому AVL универсальней, ага. И насчет сортировок я бы не был столь категоричен — тут играет роль кеш процессора, и O(N*log N) раскрывается с хорошей такой констаной *ц. Для больших N и Ц будет намного больше, ибо дороги промахи не только в кеш процессора, но еще сильней будут стоить промахи в TLD кеш страниц, коих предвидится кошмарная туча.
«The results show that each should be preferred in a different situation. Unbalanced BSTs are best when randomly ordered input can be relied upon; if random ordering is the norm but occasional runs of sorted order are expected, then red-black trees should be chosen. On the other hand, if insertions often occur in a sorted order, AVL trees excel when later accesses tend to be random, and splay trees perform best when later accesses are sequential or clustered.» Performance Analysis of BSTs in System Software
Sign up to leave a comment.
AVL деревья и широта их применения