Comments 12
Интересное решение. Любопытно было бы глянуть, насколько оно отстает от B-tree, которое не только на диске можно использовать, но и для работы с кэшем.
Тут бинарное дерево. В общем случае B-ttree не бинарное. В-дерево оперирует страницами на которых может быть с десяток элементов, а не два. Кол-во элементов нужно определить исходя из длины кэшлайнс. Причем любопытно поэкспериментировать со строками L1,L2,L3. Еще можно поэкспериментировать с чередующимся порядком элементов и ссылок, и сравнить с раздельным хранением элементов и ссылок.
Кстати, типичная ошибка, принимать B-tree как binary 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 мегабайт, если хранить все в битовом массиве. Если таких массивов не много, то можно вполне обойтись таким решением. Понятно, все зависит от задачи.
Согласен, фильтр Блума хорош для своих задач.
Но в данной статье я не рассматривал различные подходы к решению рассматриваемой задачи, мне хотелось просто немного рассказать про Cache-Conscious Data Structures, а бинарный поиск взят в качестве июллюстрации ввиду его простоты.
Only those users with full accounts are able to leave comments. Log in, please.