B-дерево быстрее, чем AVL или RedBlack-Tree? [закрыто]
Вам просто нужно добавить padding:0 к вашему элементу ul:
ul.menu {
padding: 0;
}
5 ответов
Сообщение Sean (в настоящее время принимаемое) содержит несколько неправильных требований. Жаль Sean, я не означаю быть грубым; я надеюсь, что могу убедить Вас, что мой оператор базируется на самом деле.
Они полностью отличаются в своих вариантах использования, таким образом, не возможно сделать сравнение.
Они и используются для поддержания ряда полностью заказанных объектов с быстрым поиском, вставкой и удалением. У них есть тот же интерфейс и то же намерение.
деревья RB являются структурами обычно в оперативной памяти, используемыми для обеспечения быстрого доступа (идеально O (logN)) к данным. [...]
всегда O (регистрируют n)
B-деревья являются обычно находящимися на диске структурами и так по сути медленнее, чем данные в оперативной памяти.
Ерунда. При хранении деревьев поиска на диске Вы обычно используете B-деревья. То, что много верно. Когда Вы храните данные на диске, это медленнее к доступу, чем данные в памяти. Но красно-черное дерево, сохраненное на диске, также медленнее, чем красно-черное дерево, сохраненное в памяти.
Вы сравниваете яблоки и апельсины здесь. То, что действительно интересно, является сравнением B-деревьев в оперативной памяти и красно-черных деревьев в оперативной памяти.
[Как в стороне: B-деревья, в противоположность красно-черным деревьям, теоретически эффективны в I/O-model. Я экспериментально протестировал (и проверил), I/O-model для сортировки; я ожидал бы, что это будет работать на B-деревья также.]
B-деревья являются редко двоичными деревьями, число детей, которых может иметь узел, обычно является большим количеством.
, Чтобы быть ясным, диапазон размера узлов B-дерева является параметром дерева (в C++, можно хотеть использовать целочисленное значение в качестве шаблонного параметра).
управление структурой B-дерева может быть вполне сложным, когда данные изменяются.
я помню их, чтобы быть намного более простым понять (и реализация), чем красно-черные деревья.
попытка B-дерева минимизировать количество доступов к диску так, чтобы поиск данных был довольно детерминирован.
Так много верно.
весьма распространено видеть что-то как 4 доступа B-дерева, необходимые для поиска немного данных в очень база данных.
Получил данные?
В большинстве случаев я сказал бы, что деревья RB в оперативной памяти быстрее.
Получил данные?
, поскольку поиск является двоичным, очень легко найти что-то. B-дерево может иметь несколько детей на узел, таким образом, на каждом узле необходимо просканировать узел для поиска соответствующего ребенка. Это - O (N) операция.
размер каждого узла является фиксированным параметром, поэтому даже если Вы делаете линейное сканирование, это - O (1). Если мы большой о свыше размера каждого узла, обратите внимание, что Вы обычно сохраняете массив отсортированным, таким образом, это - O (зарегистрируйте n).
На RB-дереве это был бы O (logN), так как Вы делаете одно сравнение и затем переходите.
Вы сравниваете яблоки и апельсины. O (регистрируют n) - то, потому что высота дерева в большей части O (зарегистрируйте n), как это для B-дерева.
кроме того, если Вы не играете противные приемы выделения с красно-черными деревьями, кажется разумным предугадать, что B-деревья имеют лучшее поведение кэширования (это получает доступ к массиву, не указателям, усыпанным о повсеместно, и имеет меньше выделения, наверху увеличивающего местность памяти еще больше), который мог бы помочь ему на гонке скорости.
я могу указать на экспериментальные данные, что B-деревья (с параметрами размера 32 и 64, конкретно) очень конкурентоспособны по отношению к красно-черным деревьям для небольших размеров, и превосходит его по характеристикам, передает даже для умеренно больших значений n. См. http://idlebox.net/2007/stx-btree/stx-btree-0.8.3/doxygen-html/speedtest.html
, B-деревья быстрее. Почему? Я предугадываю, что это происходит из-за местности памяти, лучше кэширующееся поведение и меньше преследования указателя (которые являются, если не то же самое, накладываясь до некоторой степени).
-
1я добрался 29.895185185185, когда я пробую это – Utku Dalmaz 22 November 2009 в 01:32
Они - sed при различных обстоятельствах - B-деревья используются, когда древовидные узлы должны держаться вместе в устройстве хранения данных - обычно, потому что устройство хранения данных является дисковой страницей, и таким образом изменять баланс могло быть очень дорогим. Деревья RB используются, когда у Вас нет этого ограничения. Таким образом, B-деревья, вероятно, будут быстрее, если Вы захотите реализовать (говорят), что индекс реляционной базы данных, в то время как деревья RB, вероятно, будут fasterv для (говорит) в поиске памяти.
-
1Это могло бы повредиться в некоторых случаях, p.e. пробующий это сегодня (
2012-11-30) результаты к2012-12-31. Могло бы быть более безопасно реализовать его как это:$firstDayNextMonth = date('Y-m-01', strtotime('next month'));– Bjoern 30 November 2012 в 07:56
Ничто не предотвращает реализацию B-дерева, которая работает только в памяти. На самом деле, если ключевые сравнения являются дешевыми, B-дерево в оперативной памяти может быть быстрее , потому что его упаковка нескольких ключей в одном узле вызовет меньше неудачные обращения в кэш во время поисков. См. этот ссылка для сравнений производительности. Кавычка: "Результаты испытаний скорости интересны и показывают B + дерево, чтобы быть значительно быстрее для деревьев, содержащих больше чем 16 000 объектов". (B+Tree является просто вариацией на B-дерево).
-
1
Все они имеют одинаковое асимптотическое поведение, поэтому производительность больше зависит от реализации, чем от типа дерева ты используешь. Некоторая комбинация древовидных структур на самом деле может быть самым быстрым подходом, когда каждый узел B-дерева точно помещается в строку кэша, а для поиска в каждом узле используется своего рода двоичное дерево. Самостоятельное управление памятью для узлов также может позволить вам добиться еще большей локальности кеша, но по очень высокой цене.
Лично я просто использую все, что есть в стандартной библиотеке для языка, который я использую, так как это много работы для очень небольшого прироста производительности (если есть).
Теоретически ... RB-деревья на самом деле очень похожи на B-деревья, поскольку они имитируют поведение 2-3-4 деревьев. AA-деревья представляют собой аналогичную структуру, которая вместо этого имитирует 2-3 дерева.
На самом деле в Википедии есть отличная статья, в которой показано, что каждое RB-дерево может быть легко выражено как B-дерево. В качестве примера возьмем следующее дерево:
теперь просто преобразуйте его в B-дерево (чтобы сделать это более очевидным, узлы по-прежнему окрашены в R / B, чего обычно нет в B-дереве):
.svg){kind=link}
(не могу добавить сюда изображение по какой-то странной причине)
То же самое верно для любого другого RB-дерева. Это взято из этой статьи:
http://en.wikipedia.org/wiki/Red-black_tree
Цитата из этой статьи:
Красно-черное дерево тогда структурно эквивалентен B-дереву заказ 4, с минимальным коэффициентом заполнения 33% значений на кластер с максимальная вместимость - 3 значения.
Я не нашел данных о том, что одно из них значительно лучше, чем другое. Я полагаю, что один из них уже вымер, если это было так. Они отличаются друг от друга относительно того, сколько данных они должны хранить в памяти и насколько сложно добавлять / удалять узлы из дерева.
Обновление:
Мои личные тесты показывают, что B-деревья лучше подходят для поиска данных, поскольку у них лучшая локальность данных, и поэтому кэш ЦП может сравнивать несколько быстрее. Чем выше порядок B-Tree (порядок - это количество дочерних элементов, которые может иметь заметка), тем быстрее будет выполняться поиск. С другой стороны, у них хуже производительность для добавления и удаления новых записей, чем выше их порядок. Это вызвано тем фактом, что добавление значения в узел имеет линейную сложность. Поскольку каждый узел представляет собой отсортированный массив, вы должны переместить множество элементов внутри этого массива при добавлении элемента в середину: все элементы слева от нового элемента должны быть перемещены на одну позицию влево или все элементы справа от нового элемента должны быть перемещены на одну позицию направо. Если значение перемещается на один узел вверх во время вставки (что часто случается в B-дереве), оно оставляет отверстие, которое также необходимо заполнить либо перемещением всех элементов слева на одну позицию вправо, либо перемещением всех элементов в правая позиция налево. Эти операции (в C обычно выполняются memmove) на самом деле O (n). Таким образом, чем выше порядок B-Tree, тем быстрее поиск, но медленнее модификация. С другой стороны, если вы выберете слишком низкий порядок (например, 3), На практике B-дерево показывает небольшие преимущества или недостатки по сравнению с другими древовидными структурами (в этом случае вы также можете использовать что-то еще). Таким образом, я всегда создавал B-деревья с высокими порядками (по крайней мере, 4, 8 и выше).
Файловые системы, которые часто основываются на B-деревьях, используют гораздо более высокие порядки (порядка 200 и даже намного больше). ) - это потому, что они обычно выбирают достаточно высокий порядок, чтобы примечание (когда оно содержит максимальное количество разрешенных элементов) равнялось либо размеру сектора на жестком диске, либо кластера файловой системы. Это обеспечивает оптимальную производительность (поскольку жесткий диск может записывать только полный сектор за раз, даже если изменяется только один байт, весь сектор все равно перезаписывается) и оптимальное использование пространства (поскольку каждая запись данных на диске равна по крайней мере размеру один кластер или кратное размеру кластера, независимо от того, насколько велики данные). Вызванный тем фактом, что оборудование видит данные как секторы, а файловая система группирует секторы в кластеры, B-деревья могут обеспечить гораздо лучшую производительность и использование пространства для файловых систем, чем любая другая древовидная структура; именно поэтому они так популярны для файловых систем.
Когда ваше приложение постоянно обновляет дерево, добавляя или удаляя из него значения, RB-Tree или AVL-Tree может в среднем показывать лучшую производительность по сравнению с B-Tree с высоким порядком. Несколько хуже для поиска, и им также может потребоваться больше памяти, но поэтому модификации обычно бывают быстрыми. На самом деле RB-Trees даже быстрее для модификаций, чем AVL-Trees, поэтому AVL-Trees немного быстрее для поиска, поскольку они обычно менее глубокие.
Как обычно, это во многом зависит от того, что делает ваше приложение. Мои рекомендации:
- Множество поисков, небольшие модификации: B-Tree (с высоким порядком)
- Множество поисков, множество модификаций: AVL-Tree
- Маленькие поиски, множество модификаций: RB-Tree
Альтернатива ко всем этим деревьям относятся AA-деревья . Как говорится в документе PDF , AA-деревья (которые на самом деле являются подгруппой RB-деревьев) почти равны по производительности с обычными RB-деревьями, но их гораздо проще реализовать, чем RB-деревья. Деревья, AVL-деревья или B-деревья. Вот полная реализация , посмотрите , насколько она крошечная (основная функция не является частью реализации, а половина строк реализации на самом деле являются комментариями).
В документе PDF показано, что Treap также является интересной альтернативой классической реализации дерева. Treap - это тоже бинарное дерево, но не Я пытаюсь добиться балансировки. Чтобы избежать наихудших сценариев, которые могут возникнуть в несбалансированных двоичных деревьях (в результате чего поиск становится O (n) вместо O (log n)), Treap добавляет некоторую случайность к дереву. Случайность не может гарантировать, что дерево хорошо сбалансировано, но также делает крайне маловероятным, что дерево сильно разбалансировано.