使用全局变量加快python中的Levenshtein距离计算

Question

嗨，我正在将python用于生物信息学的项目。

我有一个函数，该函数使用Needleman-Wunsch算法来计算查询和从我们的下一代测序平台读取的内容之间的编辑距离。 （两个字母均为'ACGT'的字符串）我的脚本运行良好，但是运行时间很长，因为该函数总共被调用了1亿多次。在该函数中，我使用尺寸为MxN的二维列表，其中M是查询的长度，而N是读取的长度。每次调用该函数时，都必须在内存中重新创建此2D列表，然后才能将其填充计算。我想知道是否可以通过创建一个2D-List作为全局变量，然后将句柄作为该函数的参数传递给此List来加快处理过程。这样，内存只需要由操作系统分配一次。希望我把问题弄清楚。从操作系统向内存请求列表需要花费多少时间。重要吗？

编辑：根据要求提供一些示例代码：

该函数通过2D数组并用数字填充：

import time
import random

def do_stuff():
    row = 12
    col = 12
    newlist = [[0 for _ in range(row)] for _ in range(col)]

    myrand = random.choice(range(100))

    for i in range(col):
        for j in range(row):
            newlist[i][j] = myrand

time1 = time.time()

for _ in range(1000000):
    do_stuff()

print(f'This took {time.time()-time1} seconds')

此代码在我的笔记本电脑上运行约22秒。

import time
import random

row = 12
col = 12
newlist = [[0 for _ in range(row)] for _ in range(col)]

def do_stuff():
    myrand = random.choice(range(100))

    for i in range(col):
        for j in range(row):
            newlist[i][j] = myrand

time1 = time.time()

for _ in range(1000000):
    do_stuff()

print(f'This took {time.time()-time1} seconds')

更改代码时，仅创建一次二维列表仅需14秒钟。

当然，实际函数会在将数字插入列表之前进行一些计算。让我知道您是否需要完整的功能，但我认为这样可能会更快。

Answer 1

这是我对性能的影响，方法是将列表放在函数的本地而不是“全局”。

---

Edit：正如@DanD在评论中指出的那样，我在更传统的堆栈和堆方式之前编写（并删除了）。对于Python，这并非完全正确。 Python虚拟机（PVM）仅使用私有堆分配其对象。但是PVM本身已实现为堆栈。然后，Python使用引用计数器（除其他外）来跟踪对象，无论是否应该丢弃它们。当您使用第一个示例时，列表对象一次又一次地被压入堆栈。前一个列表对象的引用计数器减小，然后在引用计数器达到0时将其删除。这是相当大的开销。第二个示例创建一次列表对象，使引用计数器保持满意，然后PVM可以在每次调用时使用该对象。

因此：不必为每个调用重新创建列表对象并生成新的引用，而是通过仅使用相同的引用创建一个列表对象来提高性能。

这是一个小例子，您的第一个和第二个例子简而言之：

# Creating a list of lists. Notice the reference ID's
>>> z = ([], [], [])
>>> id(z), [id(i) for i in z]
(2319201223088, [2319201319560, 2319201317128, 2319201318280])

# Overwriting the z variable with a new list of lists. Notice the reference ID's changes
>>> z = ([], [], [])
>>> id(z), [id(i) for i in z]
(2319201201752, [2319201354120, 2319201320776, 2319201318216])

# This is just to show, that the reference ID's are preserved, if you use the second example
>>> z = list(z)
>>> id(z), [id(i) for i in z]
(2319201357704, [2319201354120, 2319201320776, 2319201318216])

对于您的原始问题：OS检索内存分配的速度很快，但由于PVM具有两个内存处理程序，因此很难准确确定您的情况：a raw memory allocator and an object-specific allocator。但这不是您遇到的主要问题。