python - 查找位数组的最长前缀

Question

我正在尝试寻找一种快速算法来搜索多个位数组的最长前缀。在我的应用程序中，这些位数组可以无限长且长度可变。例如，如果我有那些​​位数组:

0b1011001
0b1001101
0b1001010
0b1010100

最长的前缀是 10。我目前正在对位数组进行 ORing 和 NAND 运算以找到它们的公共(public) 0 和 1，并将结果一起进行 XORing。

OR
0b1011111

NAND
0b0111111

XOR
0b1100000

有没有更快的解决方案？

Answer 1

关于你的方法

它可以很好地(线性)扩展位数组的数量。

它不能很好地缩放位数组的大小，理想情况下它应该根据公共(public)前缀的长度而不是位数组的大小进行缩放。

处于低水平

位数组中的单个字节/字的位操作应该比一次一个地遍历位快得多。 (虽然不确定 Python 能给你多少低级控制)。

第一个建议

如果这是像 C 这样的低级语言，我会以与您类似的方式解决这个问题，但会引用其他答案中的一些想法。

在我的例子中，我假设计算机是一台 64 位机器。

我从 (OR NAND XOR) 开始，只是每个位数组的前 64 位，(这些是 64 位机器上的基本操作，复杂度仅为 O( # of arrays ) )。

然后快速找到结果中第一个设置位的位置，(大多数计算机内置或至少在优化的汇编代码中有一些快速方法，for C，如果有设置位，返回该值.

否则，重复每个位数组的下一个 64-127 位。

(您将需要以某种方式处理不同长度的位数组，可能是通过找到串的最小长度位数组，然后将其用作最大值。)

这种方法的好处是它与位数组的数量成线性关系，并且与公共(public)前缀的长度成线性关系。

第二个建议

如果有大量的位数组，您可以通过使用并行性来提高速度。

首先，您可以在运行 NAND 的同时运行 OR。

您可以更巧妙地应用以下内容:

如果我有 4 个位数组 A,B,C,D

代替(((A或B)或C)或D)

我可以做(A 或 B)或(C 或 D)。

在这两种情况下，完成的 OR 次数相同。

但是第二种方法可以有效地并行化(实际上，在单核机器上采用第二种方法可能会更快，因为 CPU 实际上通常会有多个 ALU。)

写出逻辑有点棘手，因为您不能使用单个 for 循环和单个临时变量来保存 OR 的结果。

您可以想象将子结果存储在一个长度为位数组数量一半的数组中。将 A OR B 的子结果存储在 array[0] 中，将 C OR D 存储在 array[1] 中，然后执行 array[0] OR array[1]。 (您可以将结果存储在长度减半的新数组中，或者覆盖数组中的值以节省空间和内存分配)。

将工作划分为足够大的 block ，以使整个计算机保持忙碌，而不会引入太多开销。

有了足够多的处理器，您就可以接近位数组数量的对数复杂度，而不是线性的。但实际上，在 6 核机器上获得 5 倍的加速可能已经很不错了。