我有两个整数，称它们为haystack和needle。我需要检查一下，如果needle的二进制表示出现在haystack[并且OPTIONALLY找到第一次出现的位置]
示例
haystack = 0b10101111010110010101010101110
needle = 0b1011001 # occurred in position 13
needle = 0b111011 # not occurred
我正在寻找尽可能低的时间复杂度，我无法写出比O(h)更好的时间复杂程度的代码，其中h是干草堆中的位数。你可以在下面看到我的代码。
我需要检查预定义的needle(它永远不会改变，并且是奇数)在数十亿个随机haystack整数中的出现(因此我们无法预处理haystack以优化速度)
由于查找位置是可选的，如果您可以编写一个时间复杂度更好的代码，只返回一个指示发生的布尔值，那么它也是完美的。因为在数十亿次的检查中，我知道它没有发生，当它发生时，我可以使用以下代码来找到位置。
一个好的具有假阳性结果的概率算法也很好。
def find_needle_in_haystack(haystack, needle):
n = needle.bit_length() # calculate the number of bits in needle
mask = (1 << n) - 1 # create a mask with n bits
i = 0
while haystack != 0:
x = haystack & mask # bitwise AND with mask to get first n bits
if x == needle:
return i
i += 1
haystack >>= 1 # shift haystack to the right by 1 bit
return -1 # needle not found in haystack
首先，Python是一种糟糕的语言选择。无论如何，你会做很多琐碎的事情。Python是一种高级语言，为了方便程序员，它具有缓慢的抽象层。这会给任何看起来很简单的小把戏增加很多开销。
也就是说，我建议使用预先计算的查找表。想法如下。我们需要一个数组，按匹配位数，按下一个字节，当前匹配位数。这可以存储在长度为CCD_ 10的阵列中。位置256*a + b处的值是一个数字，它告诉您，如果您之前匹配了a位，而b是下一个字节，那么您现在匹配了多少位。
现在你的逻辑看起来是这样的(忽略选角)：
matched = 0
for b in bytes:
matched = lookup[256*matched + int(b)]
if matched == length_of_needle:
return True
return False
下面是一些演示这个想法的示例代码。请注意，我0填充了位的末尾，最后得到了偶数个字节。
# Assuming that needle is an array of bits.
def needle_to_lookup (needle):
ord2bits = []
for j in range(256):
bits = []
k = j
for _ in range(8):
bits.append(k % 2)
k = k // 2
ord2bits.append(tuple(reversed(bits)))
lookup = []
for i in range(len(needle) + 1):
for bits in ord2bits:
# Do we successfully keep matching?
matched = i
for j in range(8):
if i + j == len(needle):
matched = i+j
break
elif needle[i+j] == bits[j]:
matched = i+j
else:
matched = 0
break
if 0 == matched: # Failed to extend for a byte.
for j in range(8):
for k in range(8 - j):
if k == len(needle):
matched = k
break
elif needle[k] == bits[j+k]:
matched = k+1
else:
matched = 0
break
if 0 < matched:
break
lookup.append(matched)
return lookup
def find_needle(needle, byte_list):
lookup = needle_to_lookup(needle)
matched = 0
for byte in byte_list:
matched = lookup[256*matched + byte]
if matched == len(needle):
return True
return False
print(find_needle([1, 0, 1, 1, 0, 0, 1], bytes([175, 89, 85, 184])))
print(find_needle([1, 1, 1, 0, 1, 1], bytes([175, 89, 85, 184])))
所以我有一个开箱即用的解决方案-您可以尝试将二进制表示转换为字符串，然后使用str.find方法。例如：
In [7]: haystack = 10101111010110010101010101110
In [8]: needle = 1011001
In [9]: str_haystack = str(haystack)
In [10]: str_needle = str(needle)
In [11]: str_haystack.find(str_needle)
Out[11]: 9