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

Question

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

мне нужно:

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

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

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

Answer 1

Что касается второго вопроса:

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

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

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

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

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

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

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

выполняется тест отсортированного массива во-первых, потому, что фр om номер, который вы даете (миллионы номеров, объединенные в нескольких тысячах диапазонов), если число содержится, скорее всего, он будет в диапазоне, а не единым :)

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

Answer 2

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

Другими словами .. экстракт грызет из uint32, и сделать ..

синтаксического дерева

Answer 5

Держите ваши диапазоны в отсортированный массив и использовать бинарный поиск для поиска.

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

Answer 6

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

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

Answer 7

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

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

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

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

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