环路性能下降

Question

我有以下代码：

keywordindex = cPickle.load(open('keywordindex.p','rb'))#contains~340 thousand items
masterIndex = {}

indexes = [keywordindex]
for partialIndex in indexes:
    start = time.time()
    for key in partialIndex.iterkeys():
        if key not in masterIndex.keys():
            masterIndex[key]= partialIndex[key]
        elif key in masterIndex.keys():
            masterIndex[key].extend(partialIndex[key])
    cPickle.dump(masterIndex,open('MasterIndex.p','wb'))

    print int(time.time() - start), ' seconds'#every thousand loops

当循环运行时，我体验到性能下降，前10000个循环大约需要5秒，但是每10000个大约需要另一个秒，直到花费3倍的时间。我试着用各种可能的方式简化代码，但我似乎不知道是什么原因造成的。这有什么原因吗？这不是内存问题，我的使用率只有30%

Answer 1

您不需要搜索masterIndex.keys()。另外，只需使用一个空的else子句：

if key not in masterIndex:
    ...
else:
    ...

dict上的in运算符查询该dict的键，该操作的时间复杂度平均为O（1）。在

Answer 2

此块包含两个极其低效的编码实例：

    if key not in masterIndex.keys():
        masterIndex[key]= partialIndex[key]
    elif key in masterIndex.keys():
        masterIndex[key].extend(partialIndex[key])

首先，密钥在masterIndex中或不在masterIndex中，因此elif测试根本就没有有用的点。如果not in测试失败，in测试必须成功。所以这个代码也是这样做的：

^{pr2}$

其次，masterIndex是dict。dict支持非常高效的成员资格测试，而无需您的任何帮助；-）通过将其键具体化到一个列表中（通过.keys()），您正在将应该的快速dict查找改为对列表进行可怕的缓慢线性搜索。所以改为这样做：

^{3}$

代码运行速度会快得多。在