如何快速评估大量布尔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]
...

每个表达式可以引用每个向量中的零个或一个元素.变量很少出现在多个表达式中.对于每个查询,output是一组true表达式.

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

Answer 1

早点回来.一旦找到假布尔值,就会知道and表达式将返回false,所以不要检查其余的.

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

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

根据输入的可预测程度,您可能能够在每个表达式变量的每个可能性为假的情况下对表达式进行排序,并且最不可能重新排序表达式.

Answer 2

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

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

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

现在，遍历表达式列表，找出属于 AI 和 S[1]-S[400] 范围的表达式。然后再次拉取 JT（或缓存中适合的任何内容）并拉出这些操作，一旦到达操作列表的末尾，就重复 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] 值以确定它是否已经失败并应该跳过。