Numpy数组与嵌套列表逐元素赋值性能对比及编辑距离算法优化求助

为什么你当前的Numpy实现比嵌套列表慢 #

你当前的写法没有用到Numpy的核心优势：向量化运算。你手写了双层Python循环逐元素操作，每次读写Numpy数组元素时，都需要付出Python层和Numpy底层C层交互的额外开销（包括类型检查、边界校验、Python对象和C原生类型的转换等）。而Python嵌套列表存储的是原生Python int对象，读写和运算的开销远低于这种跨层交互的成本，所以在这种逐元素Python循环的场景下，列表性能更好。

1. 如何优化Numpy版本的运行速度 #

你可以从以下几个维度优化：

• 指定匹配的数组类型：你当前用np.zeros默认生成的是float64类型数组，存储整数会有额外的类型转换开销，修改为整数类型可直接提升性能：

  D = np.zeros((x_dim, y_dim), dtype=np.int32)
  

• 替换Python内置运算为Numpy原生运算：把Python内置的min替换为Numpy的逐元素最小运算，减少类型转换开销：

  D[i,j] = np.minimum(np.minimum(distHor, distVer), distDiag)
  

• 完全改写为向量化实现，消除Python层面的循环：编辑距离运算可以通过广播和批量操作实现，把循环下沉到Numpy的C层面执行。长度1000以上的序列用向量化实现后，性能会远超嵌套列表的实现。
• 如果允许引入第三方库，还可以用Numba装饰器编译循环逻辑，性能可以比纯Python列表实现再快1~2个数量级。

2. 这类场景下嵌套列表确实是更优选择吗 #

分情况判断：

• 如果你必须保留Python层面的逐元素循环逻辑，不愿意改写为向量化实现，那么嵌套列表确实是更优选择，原生列表的小数据读写开销远低于Numpy的跨层交互开销。
• 如果你可以改写为向量化实现，那么Numpy的性能会远高于嵌套列表，尤其是序列长度超过1000的场景下，O(n²)复杂度的Python循环会成为明显瓶颈，而Numpy的C层面循环性能优势会完全体现出来。

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