Быстрый алгоритм быстрого поиска диапазона, в котором содержится номер в наборе диапазонов?

Сценарий

У меня несколько диапазонов чисел. Эти диапазоны не перекрываются - поскольку они не перекрываются, логическим следствием является то, что ни одно число не может быть частью более чем одного диапазона в любое время. Каждый диапазон постоянно (в одном диапазоне нет отверстий, поэтому диапазон от 8 до 16 будет действительно содержать все числа от 8 до 16), но могут быть отверстия между двумя диапазонами (например, диапазон начинается с 64 и переходит на 128, следующий диапазон начинается с 256 и переходит на 384), поэтому некоторые числа могут вообще не принадлежать ни одному диапазону (номера от 129 до 255 не будут принадлежать ни одному диапазону в этом примере).

Проблема

Я получаю номер и должен знать, к какому диапазону принадлежит номер... если он вообще относится к любому диапазону. В противном случае мне нужно знать, что он не принадлежит ни одному диапазону. Конечно, скорость важна; Я не могу просто проверить все диапазоны, которые будут O (n), поскольку могут быть тысячи диапазонов.

Простые решения

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

Диапазоны также могут быть соединены цепями в какой-то древовидной структуре. Это в основном как отсортированный список с бинарным поиском. Преимущество состоит в том, что будет быстрее модифицировать дерево, чем отсортированный массив (добавочный/удаляемый диапазон), но в отличие от того, что мы тратим лишнее время на сохранение сбалансированного дерева, дерево может быть очень неуравновешенным с течением времени, и это приведет к гораздо медленнее, чем двоичный поиск в отсортированном массиве.

Можно утверждать, какое решение лучше или хуже, поскольку на практике количество операций поиска и модификации будет почти сбалансированным (будет выполняться равное количество запросов и операций добавления/удаления в секунду).

Вопрос

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

Некоторая дополнительная информация, которая может помочь здесь, следующая: все диапазоны всегда начинаются и заканчиваются с несколькими из двух. Они всегда все начинают и заканчиваются при одинаковой мощности двух (например, все они начинаются/заканчиваются с кратным 4 или кратным 8 или кратным 16 и так далее). Сила двух не может меняться во время работы. Перед добавлением первого диапазона необходимо установить силу двух, и все диапазоны, когда-либо добавленные, должны начинаться/заканчиваться с кратным значению до тех пор, пока приложение не завершится. Я думаю, что это можно использовать для оптимизации, как если бы все они начинались с кратного, например. 8, я могу игнорировать первые 3 бита для всех операций сравнения, остальные биты будут сообщать мне диапазон, если он есть.

Я читал о разделе и диапазонах деревьев. Являются ли эти оптимальные решения проблемы? Возможны ли лучшие решения? Проблема похожа на то, что должна выполнить реализация malloc (например, каждый свободный блок памяти относится к диапазону доступной памяти, а реализация malloc должна выяснить, к какому из них), так как это обычно решает проблему?

Ответ 1

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

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

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

Все другие структуры данных становятся интересными, когда вы получаете пересечения или у вас есть много диапазонов, и когда вы строите структуру и часто запрашиваете.

Ответ 3

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

Ответ 4

Если общий диапазон чисел низкий, и у вас достаточно памяти, вы можете создать огромную таблицу со всеми числами.

Например, если у вас есть миллион чисел, вы можете создать таблицу, которая ссылается на объект диапазона.

Ответ 5

В качестве альтернативы O (log n) сбалансированным двоичным деревьям поиска (BST) можно было бы построить побитовое (сжатое) trie. То есть дерево префикса на битах номеров, которые вы храните.

Это дает вам O (w) -поиск, вставку и удаление производительности; где w = количество бит (например, 32 или 64 минус любая мощность, равная 2 вашим диапазонам).

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