Как улучшить производительность сравнения многомерных битовых массивов в C или C ++ - PullRequest
Новая
       14

Как улучшить производительность сравнения многомерных битовых массивов в C или C ++

0 голосов
/ 26 января 2012

У меня есть следующий трехмерный битовый массив (для фильтра Блума): 

unsigned char  P_bit_table_[P_ROWS][ROWS][COLUMNS];

enter image description here

размерность P_ROWS представляет независимые двумерные битовые массивы (т. Е. P_ROWS [0], P_ROWS 1 , P_ROWS [2] являются независимыми битовыми массивами) и может достигать 100 МБ и содержать данные, которые содержат данные заселены независимо. Данные, которые я ищу, могут быть в любом из этих P_ROWS, и сейчас я ищу их независимо, то есть P_ROWS [0], затем P_ROWS 1 и так далее, пока я не получу положительный результат или пока конец этого (P_ROWS [n-1]). Это означает, что если n равно 100, я должен выполнить этот поиск (сравнение битов) 100 раз (и этот поиск выполняется очень часто). Кто-то предложил мне улучшить производительность поиска, если бы я мог выполнять группировку битов (используйте порядок основных столбцов в массиве основных рядов - Я НЕ ЗНАЮ КАК).

Мне действительно нужно улучшить производительность поиска, потому что программа делает многое из этого.

Я буду рад предоставить более подробную информацию о моей реализации битовой таблицы, если потребуется.

Извините за плохой язык.

Спасибо за вашу помощь.

EDIT: Группировка битов может быть выполнена в следующем формате: Предположим, что массив: 

unsigned char P_bit_table_[P_ROWS][ROWS][COLUMNS]={{(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))},
                                                  {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))},   
                                                  {(a1,a2,a3),(b1,b2,b3),(c1,c2,c3))}};

Как видите, все строки - в третьем измерении - имеют похожие данные. То, что я хочу после группировки, похоже; все a1 находятся в одной группе (как один объект, так что я могу сравнить их с другим битом для проверки, включены они или выключены), и все b1 находятся в другой группе и т. д.

1 Ответ

2 голосов
/ 26 января 2012

Повторное использование алгоритмов других людей

Существует масса оптимизаций вычисления битов , включая многие неочевидные, такие как Вес Хэмминга испециализированные алгоритмы для нахождения следующего истинного или ложного бита, которые не зависят от того, как вы структурируете свои данные.

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

Воспользуйтесь преимуществами кэширования процессора и многопоточности

Я лично свел свои многомерные битовые массивы в одно измерение, оптимизированное для ожидаемого обхода.

Таким образом, существует большая вероятность попадания в кэш ЦП.

В вашем случае я бы также глубоко подумал об изменчивости данных и о том,хочу поставить блоки на блоки битов.Имея 100 МБ данных, у вас есть потенциал для параллельной работы ваших алгоритмов с использованием множества потоков, если вы можете структурировать свои данные и алгоритмы, чтобы избежать конфликтов.

У вас может даже быть модель lockless если вы разделяете владение блоками данных по потокам, чтобы два потока не могли читать или записывать один и тот же блок.Все зависит от ваших требований.

Сейчас самое время подумать над этими вопросами.Но поскольку никто не знает ваши данные и использование лучше, чем вы, вы должны рассмотреть варианты проектирования в контексте ваших данных и моделей использования.

...