Вопрос по algorithm, complexity-theory, c++ – Структуру данных для O (log N) найти и обновить, учитывая небольшой кэш L1

19

В настоящее время я работаю над проектом встраиваемого устройства, в котором у меня проблемы с производительностью. Профилирование обнаружило операцию 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), об

Возможно, я не понял, но я думаю, что вы можете сохранить ваш массив отсортированным и сделать бинарный поиск. это будет стоить nlogn, когда вам нужно сортировать и регистрировать n, когда вам нужно искать. memo
Приблизительно, насколько большой N? Кроме того, почему поиск Contains O (N log N) вместо просто O (N)? Поиск в куче - это просто O (N) (и вам даже не нужно делать это в порядке кучи) harold
@ memo: Вот почему я заявил, что порядокA навязывается извне. Я использовалB чтобы создать второй заказ, который я контролирую. Тем не менее, даже если бы я мог пересортироватьA вместо тогоB, это все равно будет операция O (N) (сдвигать элементы междуA[old] а такжеA[new] вверх или вниз на одно место). Я стремлюсь к O (журнал N). MSalters
Чтобы быть точным: перемещение 2 случайных элементов потребует в среднем перемещения N / 3 элементов, а не N / 2 (элементы до первого элемента и после 2-го не должны перемещаться). Тем не менее, это очень интересный вопрос! amit

Ваш Ответ

3   ответа
7

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

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

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

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

Выполняется коллегой, улучшилось на 7%. Благодарность MSalters
Но чтобы добиться хорошей производительности с помощью хеш-таблицы, ее размер (хеш-таблица) должен составлять ~ * 2-4 от числа элементов (баланс нагрузки) ... В противном случае коллизии будут слишком частыми, и это распадется наO(n) поиск и обновление. amit
Да, хеш-таблица занимает больше памяти, чем простой массив, независимо от того, как реализована хеш-таблица ... Вопрос: есть ли у вас статистика о том, как часто, когда вы запрашиваете наличие 'a', оно присутствует и как часто это НЕ присутствует --- какой из случаев является более распространенным или они оба распространены? Antti Huima
@ antti.huima: СN=1000 Я смотрю на 60-90% присутствия. Немного зависит от используемых наборов данных и точного пользовательского запроса, но соотношение 2: 1 является разумным приближением. MSalters
Оказывается, что фактическая реализация имеет тонкий крайний случай; если обе хеш-функции возвращают одно и то же значение, у вас есть цикл длины 1, который вы должны обнаружить. Нам повезло найти эту ошибку в обзоре; на нашем тестовом наборе этого не произошло. Кроме того, для таблиц с высокой нагрузкой в качестве альтернативы мы нашли «Hopscotch Hashing MSalters
0

std::set<short, cmp, pool_allocator> B с Boost'spool_allocator?

По крайней мере с libstdc ++ 4.6.3 я обнаружил, что std :: set выделяет как минимум 20 * N байт. Vaughn Cato
Согласен с Воном,std::set собирается выделить как минимум два указателя. Я мог бы свернуть свой, используя идею Адама, но построить красно-черное дерево, используяshort в качестве замены указателей звучит сложно. MSalters
1

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

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

Я действительно могу жить с N <65536, для наборов данных такого размера потребуется набор данных, превышающий 256 МБ. Мой дешевый встроенный процессор с кешем 8 КБ так и не выживет. MSalters

Похожие вопросы