在大数据集上计算汉明距离

Question

我有一个大约 10^5 行的输入文件。
每行是一个 24 位的序列，即：

1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0 1 0 1 1 1 0 1 0

我需要计算每对行的汉明距离。这是我使用 SciPy 汉明函数的第一个实现：

from scipy.spatial.distance import hamming

with open('input.txt', 'r') as file:
    reader = csv.reader(file, delimiter=' ')
    nodes = {}
    b = 24  # Number of bits
    for nodeNum, node in enumerate(reader):
        node[nodeNum] = [int(i) for i in node]

for u, uBits in nodes.items():
    for v, vBits in nodes.items():
        distance = hamming(uBits, vBits) * b
            # Do stuff

我想出的第二个实现：

node[nodeNum] = sum([int(bit)*2**power for power, bit in enumerate(node)])

这里我只存储十进制值，但我必须手动计算每个 XOR 操作产生的设置位：

def hamming(a, b):
    N = a ^ b

    distance = 0
    ptr = 1

    while N:
        distance += ((N + 1) //
                           2 * ptr)
        N -= (N + 1) // 2
        ptr += 1

    return distance

我如何改进我的代码（理想情况下在内存使用和运行时间方面）？

Answer 1

为什么不直接将整个 .csv 放入一个数组中，然后让 scipy 完成计算成对距离的所有工作？

import numpy as np
import pandas as pd
import scipy.spatial.distance

nodes = []
with open('input.txt', 'r') as file:
    reader = csv.reader(file, delimiter=' ')
    for node in reader:
        nodes.append([int(i) for i in node])

nodes = np.array(nodes)  # not strictly necessary
dists = scipy.spatial.distance.pdist(nodes, 'hamming')

Answer 2

这可能是您能做到的最快速度（注意，对于您的数据大小，它需要分配 74.5 GiB 的内存）：

import numpy as np

nodes = []
with open('input.txt', 'r') as file:
    reader = csv.reader(file, delimiter=' ')
    for node in reader:
        nodes.append([int(i) for i in node])

dists = 2 * np.inner(nodes-0.5, 0.5-nodes) + nodes.shape[1] / 2

只是为了好玩，这是 Julia 中快 40 倍的版本：

using LoopVectorization, Tullio

function hamming!(nodes,dists)
    @tullio dists[i,j] = sum(nodes[i,k] ⊻ nodes[j,k])
end

n = 10^5
nodes = rand(Int8[0,1],n,24)
dists = Matrix{Int8}(undef,n,n)
@time hamming!(nodes,dists) # Run twice
  # 1.886367 seconds (114 allocations: 6.594 KiB)

在此期间，我邀请您进入 Julia 的世界。它提供与 C++ 相似的速度和类似于 Python.

的令人愉快的语法

在大数据集上计算汉明距离

Computing hamming distances on large data set

python

csv

hamming-distance