Как я могу быстро вычислить большое количество логических AND?

Question

Мне нужно запустить миллионы запросов следующего вида.

Каждый вход состоит из небольшого набора (< 100) булевых векторов различных размеров (< 20000 элементов), причем каждый из которых имеет несколько 1s и многие 0s:

A = [ 0 0 0 1 0 0 0 0 0 0 0 ... ] 
B = [ 0 0 0 0 1 0 ... ] 
... 

У меня также есть много (> 20000) булевых И-выражений. Эти выражения являются постоянными для всех запросов.

S[1] = A[10] AND B[52] AND F[15] AND U[2] 
S[2] = I[8] AND Z[4] 
... 

Каждое выражение может ссылаться на ноль или один элемент от каждого вектора. Переменные редко появляются в нескольких выражениях. Для каждого запроса вывод представляет собой набор истинных выражений.

Что такое хороший алгоритм для вычисления запросов быстро, желательно быстрее, чем оценка каждого выражения в порядке? Алгоритм должен запускаться один раз для каждого входа, и есть миллионы входов для запуска, поэтому скорость важна. Поскольку выражения постоянны, я могу их оптимизировать заранее. Я работаю с C.

Answer 1

Вы, кажется, используете лотов данных. Это предположение, но я бы сказал, что вы получите оптимальное поведение, предварительно обработав ваши выражения в оптимальных проходах кеша. Рассмотрим два выражения Дано:

S[1] = A[10] AND B[52] AND F[15] AND U[2] 
S[2] = I[8] AND Z[4] 

переписывают их как:

S[1] = 1; 
S[1] &= A[10]; 
S[1] &= B[52]; 
S[1] &= F[15]; 
S[1] &= U[2]; 

S[2] = 1; 
S[2] &= I[8]; 
S[2] &= Z[4]; 

Тогда-то все выражения вместе, чтобы создать один длинный список операций:

S[1] = 1; 
S[2] = 1; 

S[1] &= A[10]; 
S[1] &= B[52]; 
S[1] &= F[15]; 
S[2] &= I[8]; 
S[1] &= U[2]; 
S[2] &= Z[4]; 

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

Теперь пройдите список выражений, вытягивающих выражения, которые попадают в диапазон A-I и S [1] -S [400]. Затем снова проведите J-T (или все, что подходит в кеше) и потяните эти операции дальше, как только вы дойдете до конца повтора списка операций для s [401] -s [800]. Это окончательный порядок выполнения операций. Обратите внимание, что это может быть распараллелировано без конкуренции по S-диапазонам.

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

Если вы все еще хотите попытаться использовать раннюю оптимизацию, вы можете использовать , это сложнее реализовать. Подумайте: когда у вас есть свой кэш скобка AI & S [1] -s [400], и вы создали список операций по всем этой скобе:

S[1] &= A[10]; 
S[1] &= B[52]; 
S[1] &= F[15]; 
S[2] &= I[8]; 

Вы можете изменить порядок операций в группу им S [x] (этот пример уже был). Теперь, если вы обнаружите, что A [10] является ложным, вы можете «рано выйти» в блок S [2]. Насколько это реализовать? Ну, ваши операции теперь нужно знать, сколько пропустить вперед от текущей операции:

Operation[x ] => (S[1] &= A[10], on false, x+=3) 
Operation[x+1] => (S[1] &= B[52], on false, x+=2) 
Operation[x+2] => (S[1] &= F[15], on false, x+=1) 
Operation[x+3] => (S[2] &= I[8]... 

Опять же, я подозреваю, просто добавив разветвления будет медленнее, чем просто выполнение всех других работ. Это не полный процесс с самого начала, так как вы переходите к следующему блоку блока ввода, вам нужно будет пересмотреть каждое полученное значение S [x], чтобы определить, было ли оно уже неудачно и должно быть пропущено.

Answer 2

Я предлагаю вам предобработки выражения для производства:

1. список для каждой переменной, содержащей выражения с этой переменной (т.е. список для A10 будет [S1, любой другой выражения с А10])
2. отсчет для каждого выражения числа переменных в этом выражении (т.е. графы для S1 будет 4)

Тогда для каждого входа:

1. Инициализировать счетчик для каждого выражения к общему количеству переменных в этом выражении
2. цикла по всем разреженным установленным битам во входных данных и для каждого входа декремента счетчика для всех выражений, содержащих этот бит
3. Return всех выражения где счетчик достиг 0.

Answer 3

1. Преобразование входов в упакованном виде (список индексов для ненулевых элементов). Чтобы сделать весь подход более быстрым, чем оценивать каждое выражение в порядке, вам нужно обработать сразу несколько элементов, используя либо встроенные в компилятор биты twiddling (предполагая, что каждое входное логическое значение занимает только один байт, или даже лучше один бит).
2. Предварительно обрабатывать выражения 'AND' для массивов, отображающих индексы из упакованных входных массивов в выражение, к которому оно принадлежит. (Но если какая-то переменная появляется в более чем одном выражении, для нее потребуется специальная обработка).
3. Инициализировать счетчики для выражений до 0.
4. Чтение массивов входных данных и счетчиков приращений для соответствующих выражений.
5. Выражения, имеющие счетчик, равный их числу терминов, являются «истинными», другие - «ложными».

Answer 4

Возврат рано. Как только вы найдете ложное логическое значение, вы знаете, что выражение and вернет false, поэтому не проверяйте остальное.

В C, вы получите такое поведение по умолчанию в HARDCODED логических выражений:

(A[10] && B[52] && F[15] && U[2]) 

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