为了解决一个研究问题，我们必须在 Python 中组织位掩码搜索。 作为输入，我们有一个原始数据(我们将其表示为一个位序列)。大小约为 1,5Gb。 作为输出，我们必须获得特定位掩码的出现次数。 我举个例子说明一下情况
input: sequence of bits, a bitmask to search(mask length: 12bits)
第一个想法(效率不高)是像这样使用 XOR:
1step: from input we take 12 first bits(position 0 to 11) and make XOR with mask
2step: from input we take bits from 1 to 12 position and XOR with mask ...
让我们进行 2 个第一步:
input sequence 100100011110101010110110011010100101010110101010
mask to search: 100100011110
step 1: take first 12 bits from input: 100100011110 and XOR it with mask.
step 2: teke bits from 1 to 12position: 001000111101 and XOR it with mask.
...
问题是:如何组织从输入中获取位？ 我们能够取前 12 位，但我们如何取 1 到 12 位置的位来进行下一次迭代？
之前我们使用 python BitString 包，但是我们花在搜索所有掩码上的时间太高了。 还有一个。掩码的大小可以从 12 位到 256 位。 有什么建议吗？任务必须在 python 中实现
最佳答案
您的算法是在数据中搜索“字符串”的朴素方法，但幸运的是有更好的算法。 一个例子是 KMP algorithm ，但还有其他可能更适合您的用例。
使用更好的算法，您可以从 O(n*m) 的复杂度降低到 O(n+m)。
关于Python 位掩码(可变长度)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4916170/