计算非均匀向量上的距离:python列表与numpy数组

我相信您可以将数组密集化,并将未使用的最后一个元素设置为0。

import numpy as np
from scipy.spatial.distance import cdist, pdist, squareform


def batch_pdist(x, metric, batchsize=1000):
    dists = np.zeros((len(x), len(x)))
    for i in range(0, len(x), batchsize):
        for j in range(0, len(x), batchsize):
            dist_batch = cdist(x[i:i+batchsize], x[j:j+batchsize], metric=metric)
            dists[i:i+batchsize, j:j+batchsize] = dist_batch

    return dists


MIN_LEN = 5
MAX_LEN = 11
N = 10000
M = 10

data = []
data = np.zeros((N,MAX_LEN))
for i in range(N):
    num_nonzero = np.random.randint(MIN_LEN, MAX_LEN)
    data[i, :num_nonzero] = np.random.randint(0, M, num_nonzero)

dists = squareform(pdist(data, metric='cityblock'))
dists2 = batch_pdist(data, metric='cityblock', batchsize=500)
print((dists == dists2).all())

定时输出:

%timeit squareform(pdist(data, metric='cityblock'))
43.8 µs ± 134 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

有关自定义距离函数,请参见下面的内容 documentation .

我最终找到了解决这个问题的最直接的方法,不需要对代码做太多更改,只依赖计算而不依赖内存(因为这对于非常大的数据集可能是不可行的)。

基于juanpa。arrivillaga建议,我试过了 numba ,这是一个加速面向数组和数学密集型Python代码的库,主要针对 numpy . 您可以在此处阅读有关优化Python代码的良好指南: https://jakevdp.github.io/blog/2015/02/24/optimizing-python-with-numpy-and-numba/ .

MAX_LEN = 11
N = 100

# Pure Python lists implementation.
import random

def manhattan_distance(vec1, vec2):
    n1, n2 = len(vec1), len(vec2)
    n = min(n1, n2)
    dist = 0
    for i in range(n):
        dist += abs(vec1[i] - vec2[i])
    if n1 > n2:
        for i in range(n, n1):
            dist += abs(vec1[i])
    else:
        for i in range(n, n2):
            dist += abs(vec2[i])
    return dist

def compute_distances():
    n = len(data)
    for i in range(n):
        for j in range(n):
            manhattan_distance(data[i], data[j])

data = []
for i in range(N):
    data.append([])
    for k in range(random.randint(5, MAX_LEN)):
        data[i].append(random.randint(0, 10))

%timeit compute_distances()

# numpy+numba implementation.
import numpy as np
from numba import jit

@jit
def manhattan_distance_np(vec1, vec2):
    return np.absolute(vec1 - vec2).sum()

@jit
def compute_distances_np():
    n = len(data)
    for i in range(n):
        for j in range(n):
            manhattan_distance_np(data_np[i], data_np[j])

data_np = np.array([np.append(np.asarray(d), np.zeros(MAX_LEN - len(d))) for d in data])

%timeit compute_distances_np()

定时输出:

%timeit compute_distances()
78.4 ms ± 3.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit compute_distances_np()
4.1 ms ± 14.7 µs per loop (mean ± std. dev. of 7 runs, 1 loop each)

努比 具有 优化速度大约快19倍(不涉及其他代码优化)。