高效加权杰卡德距离

Question

我试图找到 ~8000*8000 pandas df 矩阵中每对行的加权杰卡德距离。我已经尝试过以下方法：

import pandas as pd
import numpy as np

def weighted_j_sim(array1, array2):
    return np.minimum(array1, array2).sum()/np.maximum(array1, array2).sum()

matrix = pd.DataFrame([[1, 2 ,3],
                       [2, 1, 1],
                       [3, 1, 1]])


for index, (name, values) in enumerate(matrix.iterrows()):
    for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
        if other_index>index: #dont check self or something already compared
            weighted_js = weighted_j_sim(values, 
                                         other_values)

和

import pandas as pd
import numpy as np
            
def weighted_j_sim(array1, array2):
    #https://stackoverflow.com/a/71276180/11357695
    q = np.concatenate((array1.T, array2.T), axis=1)
    return np.sum(np.amin(q,axis=1))/np.sum(np.amax(q,axis=1))

matrix = pd.DataFrame([[1, 2 ,3],
                       [2, 1, 1],
                       [3, 1, 1]])
    
for index, (name, values) in enumerate(matrix.iterrows()):
    for other_index, (other_name, other_values) in enumerate(matrix.iterrows()):
        if other_index>index: #dont check self or something already compared
            weighted_jd = weighted_j_sim(np.array([values.values]), 
                                         np.array([other_values.values]))

这非常慢 - 谁能建议一些 numpy 魔法在这里应用？

Answer 1

一个大的性能问题是代码在 Pandas 系列对象上执行二次运行时算法，该算法通常比 Numpy 数组慢得多。另一个问题是多次将同一行转换为 Numpy 数组效率不高。而且，多次创建临时 Numpy 数组有点昂贵。此外，如果数组很大，则为最小值和最大值传输相同的数组可能效率很低，因为需要将其重新加载到 L1 缓存。

要做的第一件事是将 pandas 数据帧转换为连续的 Numpy 数组。然后，我们可以使用 Numba 和 Cython 等基于编译器的工具，以避免创建许多临时数组并更有效地使用缓存。此外，我们还可以通过在正确的索引处启动第二个循环来轻松删除条件。最重要的是，可以使用多线程（假设 weighted_js 的计算是线程安全的）。 这是一个相当快的 Numba 实现：

import numba as nb
import numpy as np
import pandas as pd

matrix = pd.DataFrame(np.random.rand(1000, 1000))

# Designed for 64-bit float -- please change the type if you want another kind of matrix
@nb.njit('float64(float64[:,::1],)', fastmath=True, parallel=True)
def compute_fast(matrix):
    checksum = 0

    for i in nb.prange(matrix.shape[0]):
        for j in range(i+1, matrix.shape[0]):
            sum1 = 0.0
            sum2 = 0.0
            arr1 = matrix[i]
            arr2 = matrix[j]

            for k in range(matrix.shape[1]):
                a = arr1[k]
                b = arr2[k]
                sum1 += min(a, b)
                sum2 += max(a, b)

            weighted_js = sum1 / sum2

            # Required for Numba not to optimize out the whole loop 
            # (otherwise weighted_js would be unused and the wholeloop useless).
            checksum += weighted_js

    return checksum

compute_fast(np.ascontiguousarray(matrix.to_numpy()))

这是我的 i5-9600KF 处理器在 1000x1000 数据帧上的最终性能：

First code of the question:       166.3 seconds
This optimized implementation:      0.1 second

因此，Numba 实现比问题中提供的（第一个）实现快

~1660 倍。它能够在仅 8 秒（而不是几个小时）内计算 8000x8000 数据帧。

请注意，仅当您的输入不包含任何特殊值（如 NaN、Inf 或次正规值）时才应使用

fastmath

。仅当 

sum2

不为 0 时才安全（因为被零除）。 请注意，这可以进一步优化。一种方法是在线程之间实现

负载平衡工作

。这应该会使计算速度

快两倍

。另一种优化在于使用 SIMD 指令。这对于 Numba 来说似乎是不可能的（至少既不容易也不高效）。您需要使用本地语言来执行此类优化。这将使大多数机器上的计算速度提高 4 倍。两种优化可以组合在一起，使计算速度提高 8 倍。生成的程序应该能够在

最佳时间

内计算 Jaccard 距离（假设需要计算所有距离）。