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

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

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

Конечно, когда я обновлюсьA[k], Я должен найтиk вB и переместить его на новую позицию, чтобы сохранить порядок поиска. Так как я знаю старые и новые значенияA[k], это просто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 элементов находится на глубине кучи, log N, четверть в (log N) -1 и т. Д.), Что не лучше, чем тупой O (N) поиск непосредственно вA.

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

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