Структура данных для построения и поиска набора целочисленных диапазонов

Question

У меня есть набор uint32 целых чисел, в наборе могут быть миллионы предметов. 50-70% из них являются последовательными, но во входном потоке они отображаются в непредсказуемом порядке.

Мне нужно:

1. Сжатие этого набора в диапазоны для достижения эффективного представления пространства. Уже реализовано это с использованием тривиального алгоритма, поскольку диапазоны, вычисляемые только один раз по скорости, здесь не важны. После этого преобразования число результирующих диапазонов, как правило, находится в пределах 5 000–10 000, многие из них, разумеется, являются единичными.

2. Проверка принадлежности некоторого целого числа, информация о конкретном диапазоне в наборе не требуется. Это должно быть очень быстро - O (1). Думал о минимальных идеальных хэш-функциях , но они не очень хорошо работают с диапазонами. Битсеты очень неэффективны в пространстве. Другие структуры, такие как двоичные деревья, имеют сложность O (log n), хуже всего то, что реализация делает много условных переходов, и процессор не может их предсказать, давая низкую производительность.

Существует ли какая-либо структура данных или алгоритм, специализирующийся на целочисленных диапазонах, для решения этой задачи?

Answer 1

По второму вопросу:

Вы можете посмотреть на Bloom Filters . Фильтры Блума специально предназначены для ответа на вопрос о членстве в O (1), хотя ответ либо no, либо maybe (что не так ясно, как да / нет: p).

В случае maybe, конечно, вам нужна дополнительная обработка, чтобы фактически ответить на вопрос (если в вашем случае не достаточно вероятностного ответа), но даже в этом случае Фильтр Блума может действовать как привратник и отвергать большинство из запросов прямо.

Кроме того, вы можете сохранить фактические диапазоны и вырожденные диапазоны (отдельные элементы) в разных структурах.

• отдельные элементы лучше всего хранить в хеш-таблице
• фактические диапазоны могут быть сохранены в отсортированном массиве

Это уменьшает количество элементов, хранящихся в отсортированном массиве, и, следовательно, сложность двоичного поиска, выполняемого там. Поскольку вы заявляете, что многие диапазоны являются вырожденными, я предполагаю, что у вас есть только около 500-1000 диапазонов (т. Е. На порядок меньше), и log (1000) ~ 10

Поэтому я бы предложил следующие шаги:

• Фильтр Блума: если нет, остановите
• Сортированный массив реальных диапазонов: если да, остановить
• Хеш-таблица из отдельных элементов

Тест Sorted Array выполняется первым, потому что из числа, которое вы даете (миллионы чисел объединяются в несколько тысяч диапазонов), если число содержится, скорее всего, оно будет в диапазоне, а не в одиночку :)

Последнее замечание: остерегайтесь O (1), хотя это может показаться привлекательным, вы не находитесь здесь в асимптотическом случае. Едва 5000-10000 диапазонов - это мало, так как log (10000) - это что-то вроде 13. Так что не пессимизируйте вашу реализацию, получив решение O (1) с таким высоким постоянным коэффициентом, что оно на самом деле работает медленнее, чем O (log N ) решение:)

Answer 2

Если вы заранее знаете, что такое диапазоны, то вы можете проверить, присутствует ли данное число в одном из диапазонов в O (lg n), используя стратегию, описанную ниже. Это не O (1), но на практике все еще довольно быстро.

Идея этого подхода заключается в том, что если вы объединили все диапазоны вместе, у вас будет набор непересекающихся диапазонов в числовой строке. Отсюда вы можете определить порядок этих интервалов, сказав, что интервал [a, b] & le; [c, d] если бы b & le; с. Это полный порядок, потому что все диапазоны не пересекаются. Таким образом, вы можете собрать все интервалы в статический массив и затем отсортировать их по этому порядку. Это означает, что самый левый интервал находится в первом слоте массива, а самый правый интервал - в самом правом слоте. Эта конструкция занимает O (n lg n) времени.

Чтобы проверить, содержит ли некоторый интервал заданное целое число, вы можете выполнить бинарный поиск по этому массиву. Начиная со среднего интервала, проверьте, содержится ли целое число в этом интервале. Если так, то все готово. В противном случае, если значение меньше наименьшего значения в диапазоне, продолжите поиск слева, а если значение превышает наибольшее значение в диапазоне, продолжите поиск справа. По сути, это стандартный бинарный поиск, и он должен выполняться за O (LG N) времени.

Надеюсь, это поможет!

Answer 3

Вы можете использовать y-быстрые деревья или деревья Ван-Эмде Боаса для выполнения запросов времени O (lg w), где w - количество бит в слове, и вы можете использовать деревья слияния для достижения времени O (lg_w n)запросы.Оптимальным компромиссом с точки зрения n является O (sqrt (lg (n))).

Самым простым из них является, вероятно, y-быстрые деревья.Они, вероятно, быстрее, чем бинарный поиск, хотя для них требуется примерно O (lg w) = O (lg 32) = O (5) запросов к хеш-таблице, а для бинарного поиска требуется примерно O (lg n) = O (lg 10000) =O (13) сравнений, поэтому бинарный поиск может быть быстрее.

Answer 4

AFAIK нет такого алгоритма, который выполняет поиск по целочисленному списку в O (1).

Только O (1) может выполнять поиск с огромным объемом памяти.

Так что не очень многообещающе пытаться найти O (1) алгоритм поиска по списку диапазона целых чисел.

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

Answer 5

Из описания вашей проблемы может показаться, что следующий может быть хорошим компромиссом. Я описал это, используя объектно-ориентированный язык, но его легко конвертировать в C, используя тип или структуру объединения с членом типа и указателем.

Используйте первые 16 бит для индексации массива объектов (размером 65536). В этом массиве есть 5 возможных объектов

• объект NONE означает, что в наборе нет элементов, начинающихся с этих 16 бит
• объект ALL означает, что все элементы, начинающиеся с 16 битов, находятся в наборе
• объект RANGE означает, что все элементы с последними 16 битами между верхней и нижней границами находятся в наборе
• объект SINGLE означает, что в массиве находится только один элемент, начинающийся с 16 бит
• объект BITSET обрабатывает все оставшиеся случаи с битрейтом 65536 бит

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

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

Answer 6

Храните ваши диапазоны в отсортированном массиве и используйте двоичный поиск для поиска.

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

Answer 7

Вместо хранения / извлечения на основе «сравнения» (которое всегда будет O (log (n))), вам нужно работать с хранилищем / извлечением на основе «radix».

Другими словами.Извлеките клев от uint32 и сделайте дерево ..