1

我正在编写一些使用 Python 进行排序算法比较的程序。我想测量平均排序时间。第一次测量有问题。

这：

for i in xrange(self.repeats):
    # random list generator
    data_orig = [random.randint(0, self.size - 1) for x in xrange(self.size)]

    sorter = self.class_()
    data = data_orig[:]
    debug("%s for data size: %d, try #%d" % (sorter.__class__.__name__, self.size, i+1))
    t1 = time.clock()
    sorter.sort(data)
    t2 = time.clock()
    debug("Took: %0.4fms, shifts: %d, comparisons: %d" % ((t2-t1)*1000.0, sorter.shifts, sorter.comps))

class_是对 InsertionSort 类的引用。对于 size = 1000 和 5 次重复，我得到以下结果：

InsertionSort for data size: 1000, try #1
Took: 39.5341ms, shifts: 254340, comparisons: 255331
InsertionSort for data size: 1000, try #2
Took: 6.0765ms, shifts: 250778, comparisons: 251772
InsertionSort for data size: 1000, try #3
Took: 6.9946ms, shifts: 254189, comparisons: 255180
InsertionSort for data size: 1000, try #4
Took: 6.7421ms, shifts: 252162, comparisons: 253156
InsertionSort for data size: 1000, try #5
Took: 5.9584ms, shifts: 241412, comparisons: 242404

对于每种排序算法，每次我运行程序时，第一个结果都比其他结果大。我用 PyPy 运行它（用 Python 看起来不错，但速度要慢得多）。

我知道我可以简单地省略第一个结果，但这个解决方案并不让我满意 :-)

有任何想法吗？

4

1 回答 1

5

因为这就是 PyPy 的全部意义所在。它是一个优化的即时编译器，这意味着你运行一段代码的次数越多，它得到的优化就越多。第一次运行时，它还没有机会做任何优化，所以结果会很慢。随后的运行将考虑第一次的经验教训，因此会更快。

于 2012-11-07T10:04:13.107 回答