在 python 中异或大量二进制数组的最快方法是什么？

Question

我的任务是计算两组一维二进制数组之间的汉明距离——一组 3000 个数组和一组 10000 个数组，每个数组的长度为 100 个项目（位）。这就是 100 位长的 3000x10000 HD 计算 objects.And 所有这些必须在最多十几分钟内完成

这是我想出的最好的东西

#X - 3000 by 100 bool np.array 
#Y - 10000 by 100 bool np.array
hd = []
i=1
for x in X:
    print("object nr " + str(i) + "/" + str(len(X)))
    arr = np.array([x] * len(Y)) 
    C = Y^arr # just xor this array by all the arrays in the other group simultainously
    hd.append([sum(c) for c in C]) #add up all the bits to get the hamming distance
    i+=1

return np.array(hd)

它仍然需要 1-1.5 小时才能完成。我怎样才能让它更快？

Answer 1

您应该能够通过使用 numpy 来显着提高求和速度，而不是使用列表理解和内置的 sum 函数（不利用 numpy向量化操作）。

只需替换：

hd.append([sum(c) for c in C])

与：

# Explicitly use uint16 to reduce memory cost; if array sizes might increase
# you can use uint32 to leave some wiggle room
hd.append(C.sum(1, dtype=np.uint16))

对于二维数组，它将 return 一个新的一维数组，其中每个值都是相应行的总和（由于指定它应该在 axis 1 上运行).例如：

>>> arr = np.array([[True,False,True], [False,False,True], [True, True,True]], dtype=np.bool)
>>> arr.sum(1, np.uint16)
array([ 2, 1, 3], dtype=uint16)

因为它在没有类型转换的情况下在单个操作中执行了 C 层的所有工作（而不是你原来的方法需要一个 Python 级循环来对每一行进行操作，然后是一个隐式循环，而在 C 层，仍然必须隐式地将每个 numpy 值从 np.bool 一个一个地转换为 Python 级别 ints 只是为了对它们求和），这应该运行对于您所描述的数组比例，速度要快得多。

旁注：虽然不是性能问题的根源，但没有理由手动维护索引值； enumerate can do that 更快捷、更轻松。只需替换：

i=1
for x in X:
    ... rest of loop ...
    i+=1

与：

for i, x in enumerate(X, 1):
    ... rest of loop ...

您将获得相同的行为，但总体上速度稍快、更简洁、更清晰。

Answer 2

IIUC，你可以使用np.logical_xor和列表理解：

result = np.array([[np.logical_xor(X[a], Y[b].T).sum() for b in range(len(Y))] 
                                                       for a in range(len(X))])

整个操作在我的机器上运行了 7 秒。

0:00:07.226645

Answer 3

以防万一您不限于使用 Python，这是使用 bitset:

的 C++ 解决方案

#include <iostream>
#include <bitset>
#include <vector>
#include <random>
#include <chrono>

using real = double;

std::mt19937_64 rng;
std::uniform_real_distribution<real> bitset_dist(0, 1);
real prob(0.75);

std::bitset<100> rand_bitset()
{
    std::bitset<100> bitset;
    for (size_t idx = 0; idx < bitset.size(); ++idx)
    {
         bitset[idx] = (bitset_dist(rng) < prob) ? true : false;
    }
    return std::move(bitset);
}

int main()
{
    rng.seed(std::chrono::high_resolution_clock::now().time_since_epoch().count());

    size_t v1_size(3000);
    size_t v2_size(10000);

    std::vector<size_t> hd;
    std::vector<std::bitset<100>> vec1;
    std::vector<std::bitset<100>> vec2;
    vec1.reserve(v1_size);
    vec2.reserve(v2_size);
    hd.reserve(v1_size * v2_size); /// Edited from hd.reserve(v1_size);

    for (size_t i = 0; i < v1_size; ++i)
    {
        vec1.emplace_back(rand_bitset());
    }
    for (size_t i = 0; i < v2_size; ++i)
    {
        vec2.emplace_back(rand_bitset());
    }

    std::cout << "vec1 size: " << vec1.size() << '\n'
              << "vec2 size: " << vec2.size() << '\n';

    auto start(std::chrono::high_resolution_clock::now());
    for (const auto& b1 : vec1)
    {
        for (const auto& b2 : vec2)
        {
            /// Count only the bits that are set and store them
            hd.emplace_back((b1 ^ b2).count());
        }
    }
    auto time(std::chrono::duration_cast<std::chrono::milliseconds>(std::chrono::high_resolution_clock::now() - start).count());

    std::cout << vec1.size() << " x " << vec2.size()
              << " xor operations on 100 bits took " << time << " ms\n";
    return 0;
}

在我的机器上，整个操作 (3000 x 10000) 大约需要 300 毫秒。

您可以将其放入一个函数中，将其编译成一个库并从 Python 中调用它。另一种选择是将距离存储到文件中，然后在 Python.

中读取它们

编辑：我的高清向量大小错误。保留适当的内存量可将操作减少到大约 190 毫秒，因为可以避免重定位。

在 python 中异或大量二进制数组的最快方法是什么？

What is the fastest way to XOR A LOT of binary arrays in python?

python

arrays

hamming-distance