Быстрая структура данных для нижних и верхних границ запросов на целые числа?

Question

мне нужно вести список чисел, считать до 100 000 ...

, если данные (например)

1, 4, 9, 12, 20, 35, 52, 77, 91

и язапросить число, скажем, 27, я хочу, чтобы число, непосредственно предшествующее 27, было доступно в списке, так что это будет: 20

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

в настоящее время я использую stl::set в сочетании с

set<int>iterator it = lower_bound(values.begin(), values.end(), n);

так

*it = 35 и с it--, я получаю20 ... но это не достаточно быстро, число запросов большое, до 500 000 ... которые включают изменение моих значений или поиск значения.

, пожалуйста, дайте мне несколько указателей.

Answer 1

На ум приходит несколько разных идей.

Для начала, существует специальная структура данных именно для этой проблемы, называемая деревом Ван Эмда Боаса , которая хранит целые числа в некотором фиксированном диапазоне [0, U) и поддерживает поиск преемника и предшественника в O (log лог U) время. Это экспоненциально быстрее, чем использование стандартного бинарного дерева поиска для сравнения. Если вы знаете верхнюю границу целых чисел, которые вы храните, эта структура может повысить вашу производительность. Существуют и другие связанные структуры, такие как y-fast trie , которые также могут использоваться здесь.

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

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

Answer 2

100 000 достаточно мало, чтобы я мог рассмотреть использование только битового вектора ... 100 000 бит - это всего 12,5 КБ, который должен быть довольно быстрым для поиска и даже помещаться в кэш L1.

Сохраните биты в обратном направлении (т. Е. 100000 в конце; 0 в начале), чтобы сканирование по памяти было линейным, и вы можете использовать ffs (если у вашей платформы есть).

Answer 3

Вы можете разделить все числа на (например) 100 векторов

1-> [0..99]
2-> [100..199]
.....

этот вектор должен быть отсортирован. Поиск по вектору с функцией lower_bound / upper_bound обычно быстрее, чем в ассоциативных контейнерах. Но для вставки или удаления вам нужно прибегнуть к одному маленькому вектору.

UPD Я согласен с templatetypedf: дерево Ван Эмде Боаса может быть лучшим решением.