为何自研Cython实现的广义Levenshtein Distance远慢于Python Levenshtein库？

我用Cython实现了一个基于动态规划、支持调参d（替换成本）和e（插入/删除成本）的广义Levenshtein字符串距离函数，还有一个用于为大量字符串计算距离表的包装函数，但运行速度远慢于Python的Levenshtein库，想知道原因。

我的实现代码 #

cimport cython
from libc.stdlib cimport malloc, free
import numpy as np
cimport numpy as np

cdef int distance(str x,str y,int d,int e):
    cdef int m = len(x) + 1
    cdef int n = len(y) + 1
    cdef int* M = <int*>malloc(m*n*sizeof(int))
    cdef int i = 0
    cdef int j = 0
    cdef int sub
    
    for ii in range(m):
        M[ii] = ii
    for jj in range(n):
        M[m*jj] = jj

    for j in range(n - 1):
        for i in range(m - 1):
            if x[i] == y[j]:
                sub = 0
            else:
                sub = d
            M[i + 1 + m*(j + 1)] = min(min(M[i + m*(j + 1)] + e,M[i + 1 + m*j] + e),M[i + m*j] + sub)

    out = M[m*n - 1]

    free(M)
    
    return out

def distance_table(np.ndarray X,int d,int e):
    M = len(X)
    D = np.zeros((M,M))
    cdef int i
    cdef int j
    for i in range(M):
        for j in range(i):
            D[i,j] = distance(str(X[i]),str(X[j]),d,e)
        print(i)
    D = D + D.T
    return D

性能差距的主要原因 #

• 内存使用与缓存效率低下
  你用malloc分配了完整的m×n二维数组，但主流库通常会优化空间复杂度，只用2行甚至1行数组完成计算。完整二维数组的内存访问模式容易触发缓存失效，尤其是字符串较长时，内存读写的开销会大幅增加。另外，频繁调用malloc/free（批量计算时每次调用distance都会执行）会带来额外的内存管理开销，成熟库一般会用内存池或复用缓冲区来避免这个问题。

• 字符串访问的额外开销
  distance函数接收的是Python的str对象，每次索引x[i]/y[j]都会经过Python的字符串访问逻辑，没有直接操作C级别的字符数组。而主流库会直接处理原始字节（比如UTF-8或ASCII），跳过Python对象的间接访问成本。另外，批量计算时str(X[i])的类型转换是冗余操作，如果输入的X已经是字符串数组，这会重复创建Python字符串对象，增加不必要的开销。

• Cython编译优化未开启
  你的代码没有添加Cython的优化装饰器，比如@cython.boundscheck(False)、@cython.wraparound(False)，这会保留Python的边界检查和负索引支持，拖慢循环执行速度。同时，min(min(a,b),c)的写法会产生多次函数调用，而成熟库会用内联条件判断替代，减少调用开销。

• 底层算法优化差距
  Python的Levenshtein库（比如python-Levenshtein）是纯C实现，并且做了大量底层优化：比如针对ASCII字符串的特殊处理、SIMD指令加速、循环展开、分支预测优化等。你的Cython代码只是把Python逻辑翻译成带C类型的代码，没有利用这些底层优化手段，自然在执行效率上有差距。

内容的提问来源于stack exchange，提问作者user3692990