Структура данных для O (log N) находит и обновляет, учитывая небольшой кеш L1

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

В основном я имею два массива int A[N] и short B[N]. Записи в A уникальны и упорядочены внешними ограничениями. Наиболее распространенная операция - проверить, появляется ли в A[] определенное значение A. Реже, но все же общий - это изменение элемента A[]. Новое значение не связано с предыдущим значением.

Так как наиболее распространенной операцией является find, то там, где находится B[]. Это отсортированный массив индексов в A[], такой, что A[B[i]] < A[B[j]] тогда и только тогда, когда i<j. Это означает, что я могу найти значения в A, используя двоичный поиск.

Конечно, когда я обновляю A[k], мне нужно найти k в B и переместить его в новую позицию, чтобы сохранить порядок поиска. Поскольку я знаю старые и новые значения A[k], просто a memmove() подмножества B[] между старой и новой позицией k. Это операция O (N), которую мне нужно исправить; так как старые и новые значения A[k] являются сугубо случайными, я в среднем перемещаюсь о ~~N/2~~ N/3 элементах.

Я просмотрел std::make_heap, используя [](int i, int j) { return A[i] < A[j]; } как предикат. В этом случае я могу легко сделать B[0] указать наименьший элемент A, а обновление B теперь является дешевой операцией по перебалансировке O (log N). Однако, как правило, мне не нужно наименьшее значение A, мне нужно найти, присутствует ли какое-либо данное значение. И это теперь поиск O (N log N) в B. (Половина моих элементов N находится в журнале глубины кучи N, четверть в (log N) -1 и т.д.), Что не улучшает поиск немого O (N) непосредственно в A.

Учитывая, что std::set имеет O (log N) insert и find, я бы сказал, что здесь можно получить такую же производительность для обновления и поиска. Но как мне это сделать? Мне нужен другой заказ для B? Другой тип?

B в настоящее время является short [N], потому что A и B вместе имеют размер моего кеша процессора, а моя основная память намного медленнее. Переход от 6 * N до 8 * N байтов не будет приятным, но все же приемлемым, если моя находка и обновление перейдут в O (log N).

Ответ 1

Если единственными операциями являются (1) проверить, принадлежит ли значение 'a' к A и (2) значениям обновления в A, почему бы вам не использовать таблицу хеш-таблицы вместо отсортированной массив B? Особенно, если A не растет или не уменьшается по размеру, а значения только изменяют это, было бы намного лучшим решением. Хэш-таблица не требует значительно больше памяти, чем массив. (В качестве альтернативы, B следует изменить не на кучу, а на двоичное дерево поиска, которое может быть самобалансирующимся, например, в дереве разделов или красно-черном дереве. Однако деревья требуют дополнительной памяти из-за левого и правого цветов, указатели.)

Практическое решение, которое увеличивает использование памяти с 6N до 8N байтов, предназначено для ровно 50% заполненной хеш-таблицы, т.е. использует хеш-таблицу, состоящую из массива из 2N шорт. Я бы рекомендовал использовать механизм Cuckoo Hashing (см. http://en.wikipedia.org/wiki/Cuckoo_hashing). Прочтите статью далее, и вы обнаружите, что вы можете получить коэффициенты нагрузки выше 50% (т.е. Потреблять память памяти от 8N в сторону, скажем, 7N), используя больше хеш-функций. " Использование только трех хеш-функций увеличивает нагрузку до 91%."

Из Википедии:

Исследование Zukowski et al. показало, что хэширование кукушки быстрее, чем цепочка хэширования для небольших хэш-таблиц с кэшем на современных процессоров. Кеннет Росс показал выпуклые версии хеширование кукушки (варианты, в которых используются ведра, содержащие более одного ключ), чтобы быть быстрее, чем обычные методы также для большого хэша таблиц, когда использование пространства велико. Производительность bucketized хеш-таблица кукушки была исследована далее Аскитисом, с его производительностью по сравнению с альтернативными схемами хэширования.

Ответ 2

std::set обычно предоставляет вложение и удаление O (log (n)) с помощью двоичного дерева поиска. Это, к сожалению, использует пространство 3 * N для большинства реализаций на основе указателей. Предполагая данные размера слова, 1 для данных, 2 для указателей на левый и правый дочерние на каждом node.

Если у вас есть константа N и может гарантировать, что ceil(log2(N)) меньше половины размера слова, вы можете использовать массив фиксированной длины узлов дерева размером 2 * N. Используйте 1 для данных, 1 для индексов двух дочерних узлов, сохраненных как верхняя и нижняя половина слова. Независимо от того, позволит ли вы использовать самобалансирующееся двоичное дерево поиска каким-либо образом, зависит от вашего размера N и слова. Для 16-битной системы вы получаете только N = 256, но для 32-х 65k.

Ответ 3

Поскольку у вас ограниченный N, вы не можете использовать std::set<short, cmp, pool_allocator> B с Boost pool_allocator?