比较二进制数据的最快方法？

Question

我有0010011或[False, False, True, False, False, True, True]形式的数据。这种格式的示例大约有1000万个，每个示例的值不是7个而是1000个。在

在我的用例中，我得到了一个相同表单的新条目。然后，我想得到100个最相等的条目的索引。这里，most equal被定义为分别具有最相交的1s或{}s。E、 g.两个条目00011和{}有一个相交的1。在

目前，我正在做这样的比较：

similarties = []
for idx, binary_1 in enumerate(complete_list):
    similarties += [(idx, np.binary_repr(binary_1 & binary_2).count('1'))]
similarties.sort(key=lambda t: t[1], reverse=True)

对于10000个随机测试条目，这需要0.2秒。有没有更快的方法？在

Answer 1

更新：发现了三倍的加速。在

这是一种在压缩位上使用numpy来节省内存的方法。要在这种格式与0s和1类型的uint8s之间进行转换，numpy提供了packbits和{}函数。在

下面的代码预计算所有2^16模式的和，这些模式可以由16位的块组成。在

（旧版本在数据和模板中查找字节对）

我们使用视图强制转换到uint64对64位的块执行按位交集，然后再转换回uint16进行查找。在

为了找到最接近的n，我们使用argpartition（O（N）），而不是{}（O（N logn））。在

import numpy as np

n, m = 1_000_000, 1_000

data = np.random.randint(0, 256, (n, (m + 63) // 64 * 8), dtype=np.uint8)
test = np.random.randint(0, 256, ((m + 63) // 64 * 8,), dtype=np.uint8)

def create_lookup_1d():
    x, p = np.ogrid[:1<<16, :16]
    p = 1 << p
    return np.count_nonzero(x & p, axis=1)

lookup_1d = create_lookup_1d()

def find_closest(data, test, n):
    similarities = lookup_1d[(data.view(np.uint64) & test.view(np.uint64))
                             .view(np.uint16)].sum(axis=1)
    top_n = np.argpartition(similarities, len(data)-n)[-n:]
    return top_n, similarities[top_n]

# below is obsolete older version

def create_lookup_2d():
    x, y, p = np.ogrid[:256, :256, :8]
    p = 1 << p
    return np.count_nonzero(x & y & p, axis=2)

lookup_2d = create_lookup_2d()

def find_closest_old(data, test, n):
    similarities = lookup_2d[data, test].sum(axis=1)
    top_n = np.argpartition(similarities, len(data)-n)[-n:]
    return top_n, similarities[top_n]

演示（100万个条目，每个1000位，找到100个最佳）：

^{pr2}$

Answer 2

使用广播可能会有帮助。例如

import numpy as np

complete_list = np.random.randint(0, 2, (10000, 10)).astype(bool)
binary_2 = np.random.randint(0, 2, 10).astype(bool)

similarities = np.sum(complete_list & binary_2, axis=1)
idx = np.argsort(similarities)

print("Seed", binary_2)
print("Result", complete_list[idx[-1]])
print("Similarity", similarities[idx[-1]])

我无法运行您的示例（可能是不同的python/library版本？）所以还没有运行任何比较这两种方法的基准测试。当然，我们的机器会有所不同，但上面的机器比我的要慢半毫秒。在

请注意，我使用了&，而不是{}，给出了您对预期逻辑的描述。在