python - 如何提高脚本的效率？

Question

我有两个文件，一个有 4K 字符串是 4K 行，一个有 100K 是 100K 行。

对于4k行中的每个字符串，我计算了该字符串与100k行中每个字符串的相似度比，然后我选择了100k行中相似度最高的字符串作为对行的“匹配” 4k 文件。

我尝试使用 python 字典来完成这项工作。有人告诉我这会很有效。

但是我的代码效率不高，看下面:

for k,k2 in itertools.product(dict1.keys(),my_dict1.keys()):
   a=float(difflib.SequenceMatcher(None,k,k2).ratio())
     if a>0.80:
         my_dict3[k+"t"+k2]=a


for key2 in my_dict3.keys():
        k1=key2.split("t")[0]
        k2=key2.split("t")[1]
        mydict[k1][k2]=my_dict3[key2]
        k=key2.split("t")

keylist4=mydict.keys()

for key4 in keylist4:
        key=max(mydict[key4].iteritems(),key=operator.itemgetter(1))[0]
        print "%st%s" % (key4,key) 

我想知道为什么代码效率不高。但它应该是。如何提高？

我想我做错了什么，但不确定在哪里。

谢谢!

Answer 1

虽然这段代码可以稍微优化一下，但时间复杂度仍然是O(m*n)，其中m，n 是每个字典中的键数。

因为 dict_1 有 4K 键，而 dict_2 有 100K 键，总组合要迭代

100K*4K = 400M

如果对于每个组合，您花费 0.1 毫秒 来解决问题，那么完全运行该程序仍需要时间

400M/(10000*86400) = 472 days = 1.4 years

即使您能够将性能提高 20%，您仍然需要 1.4*0.8 = 1.1 年。

即使您使用 10 个并发线程来执行此操作，您也需要一个半月的时间来运行它。

所以，你这个问题最好是另想一个时间复杂度更好的算法解决方案。