Алгоритм FAST для быстрого нахождения диапазона числом принадлежит в ряде диапазонов?

Сбалансированное, отсортированное дерево с диапазонами на каждом узле кажется ответом. Я не могу доказать, что это оптимально, но на вашем месте я бы не стал искать дальше.

Создайте отсортированный список и отсортируйте его по нижнему полю / началу. Это проще всего реализовать и достаточно быстро, если у вас нет миллионов диапазонов (а может быть, даже тогда).

При поиске диапазона найдите диапазон, в котором start <= position . Здесь вы можете использовать двоичный поиск, поскольку список отсортирован. Число находится в диапазоне, если позиция <= end .

Поскольку конец любого диапазона гарантированно меньше начала следующего диапазона, вы не

После выполнения различных тестов я пришел к выводу, что здесь может работать только древовидная структура. Сортированный список, конечно, показывает хорошую производительность поиска - O (log n) - но он показывает ужасную производительность обновления (вставка и удаление медленнее более чем в 10 раз по сравнению с деревьями!).

Сбалансированное двоичное дерево также имеет O (log n) производительность поиска, однако его намного быстрее обновлять, также около O (log n), в то время как отсортированный список больше похож на O (n) для обновлений (O (log n), чтобы найти позицию для вставки или элемент для удаления, но тогда в списке необходимо переместить до n элементов, и это O (n)).

Я реализовал дерево AVL, красно-черное дерево, Treap, AA-Tree и различные варианты B-деревьев (B означает здесь Байеровское дерево, а не двоичное). Результат: деревья Байера почти никогда не побеждают. Их поиск хорош, но их производительность обновления плохая (поскольку в каждом узле B-Tree у вас снова есть отсортированный список!). Деревья Байера превосходны только в тех случаях, когда чтение / запись узла является очень медленной операцией (например, когда узлы напрямую считываются или записываются с / на жесткий диск) - поскольку B-дерево должно читать / записывать гораздо меньше узлов, чем любые другие дерево, поэтому в таком случае он выиграет. Однако, если у нас есть дерево в памяти, у него нет шансов против других деревьев, извините за всех поклонников B-Tree.

Treap было проще всего реализовать (менее половины строк кода вам нужно для других сбалансированные деревья, только вдвое больше кода, необходимого для несбалансированного дерева) и показывает хорошую среднюю производительность для поиска и обновлений ... но мы можем добиться большего.

AA-Tree показывает потрясающе хорошую производительность поиска - у меня нет идея почему. Иногда они побеждают все другие деревья (не далеко, но все же достаточно, чтобы не совпадать) ... и производительность удаления в порядке, однако, если я не слишком глуп, чтобы реализовать их правильно, производительность вставки действительно плохая (она работает гораздо больше поворотов дерева на каждой вставке, чем на любом другом дереве - даже B-деревья имеют более высокую производительность вставки).

Это оставляет нам две классики: AVL и RB-Tree. Они оба очень похожи, но после нескольких часов тестирования становится ясно одно: деревья AVL определенно имеют лучшую производительность поиска, чем деревья RB. Разница не огромная, но в 2/3 всех тестов они выиграют поисковый тест. Неудивительно, ведь деревья AVL более строго сбалансированы, чем деревья RB, поэтому в большинстве случаев они ближе к оптимальному двоичному дереву. Мы не говорим здесь об огромной разнице, это всегда сплошная гонка.

С другой стороны, RB Trees побеждают AVL Trees по вставкам почти во всех тестовых заездах, и это не такая уж близкая гонка. Как и прежде, этого ожидается. Будучи менее строго сбалансированными, деревья RB выполняют гораздо меньше вращения при вставках по сравнению с деревьями AVL.

Как насчет удаления узлов? Здесь, похоже, это сильно зависит от количества узлов. Для небольших номеров узлов (всего меньше полумиллиона) деревьям RB снова принадлежат деревья AVL; разница даже больше, чем для вставок. Довольно неожиданным является то, что как только число узлов превышает миллион узлов, деревья AVL, кажется, догоняют их, и разница с деревьями RB сокращается, пока они не станут более или менее одинаково быстрыми. Однако это могло быть следствием системы. Это могло быть связано с использованием памяти процессом или кэшированием ЦП и т.п. Что-то, что оказывает более негативное влияние на деревья RB, чем на деревья AVL, и поэтому деревья AVL могут догнать. Тот же эффект не наблюдается для поиска (AVL обычно быстрее, независимо от количества узлов) и вставок (RB обычно быстрее, независимо от количества узлов).

Заключение:
Я думаю, что самое быстрое, что я могу получить, это при использовании RB -Деревья, поскольку количество поисков будет лишь несколько выше, чем количество вставок и удалений, и независимо от того, насколько быстро AVL выполняет поиск, общая производительность пострадает от их худшей производительности вставки / удаления.

То есть, если только любой здесь может придумать гораздо лучшую структуру данных, которая будет владеть деревьями RB в большой степени; -)