Структура данных для поиска и обновления O(log N) с учетом небольшого размера кэша L1
В настоящее время я работаю над проектом встроенного устройства, где я сталкиваюсь с проблемами производительности. Профилирование обнаружило операцию O(N), которую я хотел бы исключить.
В основном у меня есть два массива int A[N]и short B[N]. Записи в Aуникальны и упорядочены внешними ограничениями. Наиболее распространенной операцией является проверка наличия определенного значения aв A[]. Реже, но все же распространено изменение элемента A[]. Новое значение не связано с предыдущим значением.
Поскольку наиболее распространенной операцией является поиск, здесь на помощь приходит B[].Это отсортированный массив индексов в A[], такой что A[B[i]] < A[B[j]]тогда и только тогда, когда iA, используя бинарный поиск.
Конечно, когда я обновляю A[k], я должен найти kв Bи переместить его в новую позицию, чтобы сохранить порядок поиска. Поскольку я знаю старое и новое значения A[k], это просто memmove()подмножества B[]между старым и новым позиция k. Это операция O(N), которую мне нужно исправить; поскольку старые и новые значения A[k]по существу случайны, я перемещаюсь в среднем примерно на N/2N/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 элементов находится на глубине кучи log N, четверть на (log N)-1 и т. д.), что не является улучшением по сравнению с тупым поиском O(N) непосредственно в A.
Учитывая, что std::setимеет O(log N) вставку и поиск, я бы сказал, что здесь можно получить ту же производительность для обновления и поиска.Но как мне это сделать? Нужен ли мне еще один заказ на B? Другой тип?
Bв настоящее время является коротким [N], потому что Aи Bвместе составляют примерно размер кеша моего процессора и моей основной памяти. намного медленнее. Переход от 6 * N к 8 * N байтам был бы нехорошим, но все же приемлемым, если бы мои поиск и обновление достигли O (log N) в обоих случаях.