速度测试导致奇怪的行为.在一种情况下将花费的时间乘以100，在另一种情况下只乘以10

Question

我正在做一个有三个函数的速度测试，readFile, prepDict和test。测试就是简单的prepDict(readFile)。然后我用timeit模块运行这些多次。

当我将循环次数增加10倍时，函数prepDict花费的时间增加了100倍，而使用函数prepDict的函数test只增加了10倍。

下面是函数和测试。

def readFile(filepath):
    tempDict = {}
    file = open(filepath,'rb')
    for line in file:
        split = line.split('t')
        tempDict[split[1]] = split[2]
    return tempDict
def prepDict(tempDict):
    for key in tempDict.keys():
        tempDict[key+'a'] = tempDict[key].upper()
        del tempDict[key]
    return tempDict
def test():
    prepDict(readFile('two.txt'))
if __name__=='__main__':
    from timeit import Timer
    t = Timer(lambda: readFile('two.txt'))
    print 'readFile(10000): ' + str(t.timeit(number=10000))
    tempDict = readFile('two.txt')
    t = Timer(lambda: prepDict(tempDict))
    print 'prepDict (10000): ' + str(t.timeit(number=10000))
    t = Timer(lambda: test())
    print 'prepDict(readFile) (10000): ' + str(t.timeit(number=10000))
    t = Timer(lambda: readFile('two.txt'))
    print 'readFile(100000): ' + str(t.timeit(number=100000))
    tempDict = readFile('two.txt')
    t = Timer(lambda: prepDict(tempDict))
    print 'prepDict (100000): ' + str(t.timeit(number=100000))
    t = Timer(lambda: test())
    print 'prepDict(readFile) (100000): ' + str(t.timeit(number=100000))

我得到的结果如下:

readFile(10000): 0.61602914474
prepDict (10000): 0.200615847469
prepDict(readFile) (10000): 0.609288647286
readFile(100000): 5.91858320729
prepDict (100000): 18.8842101717
prepDict(readFile) (100000): 6.45040039665

如果我多次运行它，我得到类似的结果。为什么在使用prepDict函数的情况下，prepDict(readFile)只增加了10倍，而prepDict(readFile)却增加了100倍?

two.txt是一个表格分隔文件，包含以下数据点:

Item    Title   Hello2
Item    Desc    Testing1232
Item    Release 2011-02-03

Answer 1

这里的问题是您的prepDict函数扩展了输入。每次按顺序调用它，它都有更多的数据要处理。数据呈线性增长，所以第10000次运行的时间大约是第一次的10000x。*

当你调用test时，它每次都创建一个新的字典，所以时间是恒定的。

您可以很容易地看到这一点，通过更改prepDict测试，每次在字典的新副本上运行:

t = Timer(lambda: prepDict(tempDict.copy()))

---

顺便说一下，你的prepDict实际上并没有随着number呈指数增长，只是二次增长。一般来说，当某物呈超线性增长时，你想要估计算法成本，你真的需要得到两个以上的数据点。

---

*这并不是完全正确的——只有当字符串和哈希操作(线性增长)所花费的时间开始淹没其他所有操作(都是常量)所花费的时间时，它才开始线性增长。

**你在这里没有提到任何关于指数增长的东西，但在你之前的问题中你提到了，所以你可能在你的实际问题中做出了同样的毫无根据的假设。

Answer 2

您对prepDict的调用不是发生在孤立的环境中。每次调用prepDict都会修改tempDict——键每次都变长一点。因此，在调用prepDict 10**5之后，prepDict中的键是相当大的字符串。如果在prepDict:

中输入print语句，就可以看到这一点。

def prepDict(tempDict):
    for key in tempDict.keys():
        tempDict[key+'a'] = tempDict[key].upper()
        del tempDict[key]
    print(tempDict)
    return tempDict

解决这个问题的方法是确保对prepDict的每次调用——或者更一般地说，您正在计时的语句——不会影响您正在计时的下一个调用(或语句)。abarnert已经展示了解决方案:prepDict(tempDict.copy())。

顺便说一下，您可以使用for-loop来减少代码重复:

import timeit
import collections    
if __name__=='__main__':
    Ns = [10**4, 10**5]
    timing = collections.defaultdict(list)
    for N in Ns:
        timing['readFile'].append(timeit.timeit(
            "readFile('two.txt')",
            "from __main__ import readFile",
            number = N))
        timing['prepDict'].append(timeit.timeit(
            "prepDict(tempDict.copy())",
            "from __main__ import readFile, prepDict; tempDict = readFile('two.txt')",
            number = N))
        timing['test'].append(timeit.timeit(
            "test()",
            "from __main__ import test",
            number = N))
    print('{k:10}: {N[0]:7} {N[1]:7} {r}'.format(k='key', N=Ns, r='ratio'))
    for key, t in timing.iteritems():
        print('{k:10}: {t[0]:0.5f} {t[1]:0.5f} {r:>5.2f}'.format(k=key, t=t, r=t[1]/t[0]))

产生的时间如

key       :   10000  100000 ratio
test      : 0.11320 1.12601  9.95
prepDict  : 0.01604 0.16167 10.08
readFile  : 0.08977 0.91053 10.14

Answer 3

这是因为当您测试prepDict时，您正在重用tempDict对prepDict的所有调用。由于prepDict循环遍历字典中给定的所有项，然后基本上只是将每个字符串键的长度增加1，因此最终会得到一堆非常长的键。随着操作的进行，这开始降低函数的速度，因为字符串连接操作正在使用/重新创建越来越大的字符串。

在test中这不是问题，因为您每次都重新初始化字典。