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 クラスへの参照です。サイズ = 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 に答える