字符串操作似乎效率低下

Question

我觉得我的代码效率太低了。我猜这和使用字符串有关，不过我不确定。代码如下：

genome = FASTAdata[1]
genomeLength = len(genome);

# Hash table holding all the k-mers we will come across
kmers = dict()

# We go through all the possible k-mers by index
for outer in range (0, genomeLength-1):
    for inner in range (outer+2, outer+22):
        substring = genome[outer:inner]
        if substring in kmers:              # if we already have this substring on record, increase its value (count of num of appearances) by 1
            kmers[substring] += 1
        else:
            kmers[substring] = 1            # otherwise record that it's here once

这是搜索所有长度不超过20的子串。现在这段代码似乎要花很长时间，而且永远不会终止，所以这里一定出了问题。在字符串上使用[：]会导致巨大的开销吗？如果是的话，我能用什么来代替它呢？在

为了清楚起见，这个文件有将近200mb，非常大。在

Answer 1

您应该使用memoryview来避免创建子字符串，因为[:]将返回一个“view”而不是一个副本，但是您必须使用python3.3或更高版本（在此之前，它们是不可散列的）。在

另外，Counter可以简化代码。在

from collections import Counter

genome = memoryview("abcdefghijkrhirejtvejtijvioecjtiovjitrejabababcd".encode('ascii'))
genomeLength = len(genome)

minlen, maxlen = 2, 22

def fragments():
    for start in range (0, genomeLength-minlen):
        for finish in range (start+minlen, start+maxlen):
            if finish <= genomeLength:
                yield genome[start:finish]

count = Counter(fragments())
for (mv, n) in count.most_common(3):
    print(n, mv.tobytes())

产生：

^{pr2}$

在我的笔记本电脑上，一个1000000字节的随机数组需要45秒，但是2000000字节会导致交换（超过8GB的内存使用）。然而，由于片段的大小很小，所以可以很容易地将问题分解成数百万个长的子序列，然后在最后合并结果（只是要小心重叠）。幸运的话，200MB阵列的总运行时间为~3小时。在

为了清楚起见，通过“最后合并结果”，我假设您只需要保存每个1M子序列的最流行的子序列，例如，将它们写入一个文件。您不能将计数器保存在内存中—这就是使用8GB的原因。如果你有成千上万次出现的片段，那就很好了，但是显然对于较小的数量是不起作用的（例如，你可能在2001M子序列中的每一个子序列中只看到一个片段，因此永远不要保存它）。换句话说，结果将是下界，即不完整，尤其是在较低的频率下（只有在每个子序列中找到并记录片段时，值才是完整的）。如果你需要一个确切的结果，这是不合适的。在

Answer 2

我建议使用动态规划算法。问题是，对于所有未找到的inner字符串，您将再次使用附加字符重新搜索这些字符串，因此当然也找不到这些字符串。我心里没有具体的算法，但这肯定是动态编程的一个例子，你可以记住你已经搜索过的内容。作为一个非常糟糕的例子，记住长度为1，2，3，。。。在下一次迭代中，如果字符串只是较长的，则永远不会扩展这些基。在