<p>我更关注于优化Python,而不是优化算法,因为我不认为这里有多少算法上的改进。下面是我提出的一些Python优化。在</p>
<p>(一)。由于您似乎使用的是python2.x,所以将all range()更改为xrange()。range()在迭代之前生成完整的数字列表,而xrange根据需要生成数字。在</p>
<p>(二)。对“最大”和“最小”进行以下替换:</p>
<pre><code>start = max(0,i-halflen)
</code></pre>
<p>与</p>
^{2}$
<p>以及</p>
<pre><code>end = min(i+halflen+1,len2)
</code></pre>
<p>与</p>
<pre><code>end = i+halflen+1 if i+halflen+1 < len2 else len2
</code></pre>
<p>第一个循环中的第二个和第二个相似的循环。下面还有一个min(),函数开头附近有一个max(),所以对这些函数也要做同样的处理。替换min()和max()确实有助于减少时间。这些都是方便的函数,但是比我替换它们的方法更昂贵。在</p>
<p>(三)。使用common1代替len(ass1)。您已经在common1中跟踪了ass1的长度,所以让我们使用它,而不是调用一个昂贵的函数来再次找到它。在</p>
<p>(四)。替换以下代码:</p>
<pre><code>minlen = min(len1,len2)
for same in xrange(minlen+1):
if (str1[:same] != str2[:same]):
break
same -= 1
</code></pre>
<p>与</p>
<pre><code>for same in xrange(minlen):
if str1[same] != str2[same]:
break
</code></pre>
<p>这样做的原因主要是str1[:same]每次通过循环都会创建一个新字符串,您将检查已经检查过的部分。另外,如果我们不需要检查<code>'' != ''</code>和递减{<cd2>},那么就不必再检查了。在</p>
<p>(五)。使用<a href="http://psyco.sourceforge.net/" rel="nofollow noreferrer">psyco</a>,一个实时编译器。一旦您下载并安装了它,只需添加行</p>
<pre><code>import psyco
psyco.full()
</code></pre>
<p>在文件的顶部使用它。除非你做了我提到的其他改变,否则不要使用psyco。出于某种原因,当我在你的原始代码上运行它时,它实际上减慢了速度。在</p>
<p>使用timeit,我发现在前4个更改中,我得到了大约20%的时间减少。但是,当我添加psyco和这些更改时,代码比原始代码快3到4倍。在</p>
<p><strong>如果您想要更快的速度</strong></p>
<p>相当多的剩余时间在字符串的find()方法中。我决定试着用我自己的代替这个。对于第一个循环,我替换了</p>
<pre><code>index = workstr2.find(str1[i],start,end)
</code></pre>
<p>与</p>
<pre><code>index = -1
for j in xrange(start,end):
if workstr2[j] == str1[i]:
index = j
break
</code></pre>
<p>和第二个循环的相似形式。没有psyco,这会减慢代码的速度,但是有了psyco,它会大大加快速度。经过最后的修改,代码比原来快了8到9倍。在</p>
<p><strong>如果速度不够快</strong></p>
<p>那么你应该开始制作一个C模块。在</p>
<p>祝你好运!在</p>