如何加速字符串型二维NumPy数组的行间成对距离矩阵计算？

兄弟，我太懂你这种被O(N²)复杂度卡到怀疑人生的痛苦了！10k行的话光是嵌套循环就要跑1亿次，再加上每轮还要算10个字符串的Levenshtein相似度，跑1小时真的一点不奇怪。咱们一步步拆解优化，把速度提上去：

先说说你当前代码的问题 #

你用np.vectorize其实没真正实现向量化加速——它本质上还是个披着numpy外衣的Python循环，再加上两层纯Python的for遍历，Python解释器的开销直接拉满，这才是慢的核心原因。

优化方案来了，从易到难： #

1. 先换个更快的相似度计算库

别用python-Levenshtein了，换成rapidfuzz！它的底层是C++实现的，计算Levenshtein相似度的速度比前者快好几倍甚至几十倍，而且API和python-Levenshtein几乎兼容，改起来超简单。

2. 利用距离矩阵的对称性砍半计算量

你算的Q[i][j]和Q[j][i]其实是相等的（因为Levenshtein ratio(a,b)=ratio(b,a)），所以完全不用重复计算。只算上三角或者下三角的元素，然后复制到对称位置，直接减少50%的计算量，速度瞬间翻倍！

3. 用多进程榨干CPU多核

成对行的计算完全是独立的，不会互相影响，刚好可以用多进程并行处理。把每行的计算任务拆分给不同的CPU核心，比如8核CPU就能把时间降到原来的1/8左右。

4. 减少numpy索引的额外开销

把NumPy数组里的每行提前转成Python元组/列表，避免在循环里反复调用X[i]、X[j]——numpy的索引虽然快，但在亿级循环里积累起来的开销也不容忽视。

整合后的最优代码示例 #

from rapidfuzz import fuzz
import numpy as np
from multiprocessing import Pool

def calculate_single_row(args):
    row_idx, target_row, all_rows = args
    row_result = []
    for j, compare_row in enumerate(all_rows):
        # 计算当前行和第j行对应列的相似度之和
        sum_ratio = sum(fuzz.ratio(s1, s2)/100 for s1, s2 in zip(target_row, compare_row))
        row_result.append(10 - sum_ratio)
    return row_result

if __name__ == "__main__":
    # 假设这是你的输入数组
    X = np.array([['asd', 'qwe'], ['asd', 'rty']])
    # 提前把每行转成元组，减少numpy索引开销
    all_rows = [tuple(row) for row in X]
    n_rows = len(all_rows)

    # 准备多进程任务参数
    tasks = [(i, row, all_rows) for i, row in enumerate(all_rows)]
    
    # 启动多进程池（默认用所有CPU核心）
    with Pool() as pool:
        results = pool.map(calculate_single_row, tasks)
    
    # 把结果转成NumPy矩阵
    Q = np.array(results)

额外的进阶优化（如果还想更快） #

如果你的字符串有重复，可以先统计重复行的数量，只计算唯一行之间的距离，最后再根据重复次数填充矩阵——比如10k行里有2k个唯一行，计算量直接从1亿降到400万，这速度提升简直恐怖！

备注：内容来源于stack exchange，提问作者anon.for