嵌套枚举 for 循环到理解列表

Question

我正在使用 textdistance 库 (https://github.com/life4/textdistance) 中的 textdistance.needleman_wunsch.normalized_distance。我将它与 Scipy 库中的 cdist 一起使用来计算序列对距离。但是由于嵌套枚举for循环，过程很长。

在这里你可以找到 textdistance 库中使用的代码，这需要时间，我想知道你是否知道我可以如何加速嵌套嵌套 for 循环，也许使用列表理解？

s1 = "sentence1"
s2 = "sentevfers2"
gap = 1


def sim_func(*elements):
    """Return True if all sequences are equal.
    """
    try:
        # for hashable elements
        return len(set(elements)) == 1
    except TypeError:
        # for unhashable elements
        for e1, e2 in zip(elements, elements[1:]):
            if e1 != e2:
                return False
        return True


dist_mat = numpy.zeros(
    (len(s1) + 1, len(s2) + 1),
    dtype=numpy.float,
)

# DP initialization
for i in range(len(s1) + 1):
    dist_mat[i, 0] = -(i * gap)

# DP initialization
for j in range(len(s2) + 1):
    dist_mat[0, j] = -(j * gap)

""" Possible enhancement with list comprehension ? """
# Needleman-Wunsch DP calculation
for i, c1 in enumerate(s1, 1):
    for j, c2 in enumerate(s2, 1):
        match = dist_mat[i - 1, j - 1] + sim_func(c1, c2)
        delete = dist_mat[i - 1, j] - gap
        insert = dist_mat[i, j - 1] - gap
        dist_mat[i, j] = max(match, delete, insert)
distance = dist_mat[dist_mat.shape[0] - 1, dist_mat.shape[1] - 1]
print(distance)

Answer 1

这段代码运行缓慢有几个原因：

它（可能）在 CPython 中执行并用纯 Python 编写，这是一个 不是为这种数字代码设计的慢速解释器 ;
sim_func 是比较各种元素的通用方法，但也非常低效（分配，散列，异常处理和字符串操作）。

代码无法轻松并行化，因此需要对 numpy 进行矢量化。但是，您可以使用 Numba 来加快速度。仅当输入字符串非常大或此处理执行了很多时间时才值得。如果不是这种情况，请使用更合适的编程语言（例如 C、C++、D、Rust 等）或原生的Python 专用于 .

的模块

这是优化后的 Numba 代码：

s1 = "sentence1"
s2 = "sentevfers2"
gap = 1  # Assume this is an integer

@njit
def NeedlemanWunschDP(dist_mat, s1, s2):
    for i in range(1, len(s1)+1):
        for j in range(1, len(s2)+1):
            match = dist_mat[i - 1, j - 1] + (s1[i-1] == s2[j-1])
            delete = dist_mat[i - 1, j] - gap
            insert = dist_mat[i, j - 1] - gap
            dist_mat[i, j] = max(match, delete, insert)

dist_mat = numpy.empty(
    (len(s1) + 1, len(s2) + 1),
    dtype=numpy.int64,
)

# DP initialization
for i in range(len(s1) + 1):
    dist_mat[i, 0] = -(i * gap)

# DP initialization
for j in range(len(s2) + 1):
    dist_mat[0, j] = -(j * gap)

# Transform the strings to fast integer arrays
tmp_s1 = numpy.array([ord(e) for e in s1], dtype=numpy.int64)
tmp_s2 = numpy.array([ord(e) for e in s2], dtype=numpy.int64)
# Needleman-Wunsch DP calculation
NeedlemanWunschDP(dist_mat, tmp_s1, tmp_s2)
distance = dist_mat[dist_mat.shape[0] - 1, dist_mat.shape[1] - 1]
print(distance)

NeedlemanWunschDP 的编译时间在我的机器上大约需要 400 毫秒，但生成的代码在大字符串上快 1800 倍。

嵌套枚举 for 循环到理解列表

Nested enumerated for loops to comprehension list

python

performance

list-comprehension

nested-loops