Комментарии 12
Интересное решение. Любопытно было бы глянуть, насколько оно отстает от B-tree, которое не только на диске можно использовать, но и для работы с кэшем.
Разве это не одно и то же?
НЛО прилетело и опубликовало эту надпись здесь
Тут бинарное дерево. В общем случае B-ttree не бинарное. В-дерево оперирует страницами на которых может быть с десяток элементов, а не два. Кол-во элементов нужно определить исходя из длины кэшлайнс. Причем любопытно поэкспериментировать со строками L1,L2,L3. Еще можно поэкспериментировать с чередующимся порядком элементов и ссылок, и сравнить с раздельным хранением элементов и ссылок.
Ах, да. Не одно и то же. Меня сбил с толку префикс «B» :-(
Кстати, типичная ошибка, принимать B-tree как binary tree. Это логично, когда начинают изучение с двоичных деревьев.
Сами авторы никогда не раскрывали смысл буквы B, но у одного из них фамилия на B начинается (Rudolf Bayer, Ed McCreight) и работали они в то время в Boing. Еще были версии «balanced,» «broad,» or «bushy».
Еще можно обратить внимание, что полный функционал B-tree избыточен для условий задачи. Автор зафиксировал, что на входе неизменный набор данных, т.е. есть время на то чтобы его оптимально упорядочить один раз и затем многократно использовать.
Сами авторы никогда не раскрывали смысл буквы B, но у одного из них фамилия на B начинается (Rudolf Bayer, Ed McCreight) и работали они в то время в Boing. Еще были версии «balanced,» «broad,» or «bushy».
Еще можно обратить внимание, что полный функционал B-tree избыточен для условий задачи. Автор зафиксировал, что на входе неизменный набор данных, т.е. есть время на то чтобы его оптимально упорядочить один раз и затем многократно использовать.
Есть такой трюк. Если надо бинпоиском поискать в массиве длине n, то можно разбить его на sqrt(n) блоков по sqrt(n) элементов. Затем бинпоиском за log(sqrt(n)) подыскать нужный блок и в нём вторым бинпоиском за log(sqrt(2)) найти элемент. В сумме получается всё тот же log(n), но попаданий в кэш значительно больше, т.к. каждый раз ищем на довольно коротком массиве длины sqrt(n).
Для ускорения отсеивания тех чисел, которых в списке нет, можно использовать фильтр Блума
Но в вашем конкретном случае вы используете int, который 32х битный. Это будет 256 мегабайт, если хранить все в битовом массиве. Если таких массивов не много, то можно вполне обойтись таким решением. Понятно, все зависит от задачи.
Но в вашем конкретном случае вы используете int, который 32х битный. Это будет 256 мегабайт, если хранить все в битовом массиве. Если таких массивов не много, то можно вполне обойтись таким решением. Понятно, все зависит от задачи.
Есть ещё дружественное кэшу семейство Judy контейнеров: en.wikipedia.org/wiki/Judy_array
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Cache-Conscious Binary Search