如何快速评估大量布尔 AND？

Question

我需要运行数百万以下类型的查询。

每个输入都包含一个小集合 (<100) 各种大小的布尔向量（<20000 个元素），每个都有几个 1 和许多 0：

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

我还有很多 (>20000) 布尔 AND 表达式。这些表达式对于所有查询都是不变的。

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

每个表达式可以引用每个向量中的零个或一个元素。变量很少出现在多个表达式中。对于每个查询，输出是一组真实的表达式。

什么是快速计算查询的好算法，最好比按顺序计算每个表达式更快？该算法需要为每个输入运行一次，并且有数百万个输入要运行上，因此速度很重要。由于表达式是常量，我可以提前优化它们。我在和 C 一起工作。

Answer 1

我建议您预处理表达式以生成：

包含具有该变量的表达式的每个变量的列表（即 A10 的列表将是 [S1,A10 的任何其他表达式]）
该表达式中变量数量的每个表达式的计数（即 S1 的计数为 4）

然后对于每个输入：

将每个表达式的计数初始化为该表达式中的变量总数
遍历输入中的所有稀疏集位，并针对每个输入递减包含该位的所有表达式的计数
Return 计数达到 0 的所有表达式。

Answer 2

将您的输入转换为压缩形式（非零元素的索引列表）。为了使整个方法比按顺序评估每个表达式更快，您需要一次处理多个元素，使用位旋转的编译器内部函数（假设每个输入布尔值只占用一个字节，或者更好的一位）。
预处理 'AND' 表达式到数组，将打包输入数组的索引映射到它所属的表达式。（但如果某个变量出现在多个表达式中，则需要进行一些特殊处理）。
将表达式的计数器初始化为 0。
读取打包输入数组并为相应的表达式递增计数器。
计数器等于其项数的表达式是 'true'，其他是 'false'。

Answer 3

Return早。一旦你发现一个错误的布尔值，你就知道 and 表达式将 return false，所以不要检查其余的。

在 C 语言中，默认情况下您会在硬编码的布尔表达式中获得此行为：

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

根据输入的可预测性，您可能会根据错误的可能性对每个表达式的变量进行排名，并将表达式从最可能到最不可能重新排序，从而获得很多性能。

Answer 4

您似乎正在使用大量数据。这是一个猜测，但我想说您将通过将表达式预处理为缓存最佳传递来获得最佳行为。考虑给定的两个表达式：

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];

考虑手头机器缓存的大小。我们想要缓存中的所有输入向量。这可能不会发生，所以我们知道我们将多次将输入向量和结果向量拉入和拉出内存。我们想将可用的机器缓存分为三个部分：输入向量块、结果向量块和一些工作 space（我们当前的操作列表将从中提取）。

现在，遍历表达式列表，找出属于 A-I 和 S[1]-S[400] 范围的表达式。然后再次拉取 J-T（或任何适合缓存的内容），然后拉取这些操作，一旦到达操作列表的末尾，就对 s[401]-s[800] 重复。这是操作的最终执行顺序。请注意，这可以并行化，而不会跨 S 频段争用。

不利的一面是您没有提前退出的行为。好处是在转换计算块时只会出现缓存故障。对于如此大的数据集，我怀疑这（以及所有分支的消除）将压倒早期优势。

如果您仍想尝试使用早期优化，您可以它只是更难实现。考虑一下：一旦你有了缓存括号 A-I & S[1]-s[400]，并且你已经在该括号中创建了一个操作列表：

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

然后您可以重新排序操作以按 S[x]（本示例已经如此）对它们进行分组。现在，如果您发现 A[10] 为假，您可以 "early out" 到 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] 值以确定它是否已经失败并且应该被跳过。

如何快速评估大量布尔 AND？

How can I evaluate a large number of boolean ANDs quickly?

c

algorithm

boolean