Python SequenceMatcher开销 - 100% CPU利用率和极慢处理

Question

我正在使用difflib来比较两个文件夹中的文件（这些文件是连续年份的版本）。

首先，我用filecmp来找出哪些文件发生了变化，然后我逐个使用difflib.SequenceMatcher来比较这些文件，并生成一个HTML格式的差异对比，具体的做法可以参考这里。

不过，我发现这个程序运行得太慢了，Python的CPU使用率达到了100%。经过时间分析，我发现seqm.get_opcodes()这个调用占用了所有的时间。

如果有人能提供一些见解，我将非常感激。谢谢！

代码：

#changed_set contains the files to be compared
for i in changed_set:
  oldLines = open(old_dir +"/" + i).read()
  newLines = open(new_dir +"/" + i).read()
  seqm = difflib.SequenceMatcher(lambda(x): x in string.whitespace, oldLines, newLines)
  opcodes = seqm.get_opcodes() #XXX: Lots of time spent in this !
  produceDiffs(seqm, opcodes)
  del seqm

Answer 1

你也可以试试这个叫做 diff-match-patch 的库，根据我的经验，它的速度可以快10倍。

补充一下：我在这里的另一个回答有例子

from diff_match_patch import diff_match_patch

def compute_similarity_and_diff(text1, text2):
    dmp = diff_match_patch()
    dmp.Diff_Timeout = 0.0
    diff = dmp.diff_main(text1, text2, False)

    # similarity
    common_text = sum([len(txt) for op, txt in diff if op == 0])
    text_length = max(len(text1), len(text2))
    sim = common_text / text_length

    return sim, diff

Answer 2

我的建议是用一种不同的方法来解决这个问题：试试使用像git这样的版本控制系统，来查看这个文件夹这些年来是怎么变化的。

首先，把第一年的文件夹做成一个仓库，然后把内容替换成下一年的文件夹，并把这个变化提交上去。（或者把.git这个文件夹移动到下一年的文件夹里，这样可以省去复制和删除的麻烦。）然后重复这个过程。

接着运行gitk，你就能看到任何两个版本之间的变化。你可以看到是某个二进制文件发生了变化，或者对于文本文件来说，可以看到具体的差异。