1

私はPythonのcollection.dequeで遊んでいて、次のベンチマークを作成しました。

#!/usr/bin/python

import timeit

if __name__=='__main__':
    number = 1000000
    for r in (1,10,100,1000,5000,10000,100000):
        print r
        print timeit.timeit("while x: x.pop(0);",
                            "x = list(range("+str(r)+"))",
                            number=number)
        print timeit.timeit("while x: x.popleft();",
                            "from collections import deque; x = deque(range("+str(r)+"))",
                             number=number)

これにより、さまざまなサイズのリスト/両端キューからpop（0）/ popleft（）が実行されます。結果は次のとおりです。

1
0.0801048278809
0.0822219848633
10
0.081041097641
0.080836057663
100
0.0806250572205
0.0807700157166
1000
0.081248998642
0.082062959671
5000
0.0976719856262
0.0825741291046
10000
0.157499074936
0.0825819969177
100000
16.0247170925
0.097559928894

私の質問は、小さな両端キューとリスト（〜1000要素）のパフォーマンスがほぼ同じなのはなぜですか？

4

3 に答える 3

4

timeit モジュールはセットアップ コードを 1 回実行し、次に時間指定numberされたコード (この場合はnumber==1000000) を実行します。あなたの場合、これは次のようになります(リストの場合):

x = list(range(r))
#timer is started here
for iteration in xrange(1000000):
    while x: x.pop(0)
#timer is stopped here

ご覧のとおり、最初の反復だけが何もしません。他の 999999 回の反復xでは、空になるため、サイズを 1 回だけチェックします。このチェックには、リストと両端キューの場合、ほぼ同じ時間がかかります。

小さなリスト/両端キューの場合、最初の反復は他の 999999 回の反復を組み合わせたものに比べて短いため、関連するものを実際に測定することはなく、同様の時間が得られます。

使用すればnumber==1、この問題は発生しません。別のオプションは、リスト/両端キューが同じサイズのままになるように、時間指定されたコードで項目をプッシュおよびポップすることです。

于 2010-01-16T13:49:21.500 に答える
3

I always find timeit more suitable for use from the shell command line. Here, for example:

$ python -mtimeit -s'from collections import deque; base=range(100); ctr=list' 'x=ctr(base)' 'while x: x.pop(0)'
10000 loops, best of 3: 77.3 usec per loop
$ python -mtimeit -s'from collections import deque; base=range(100); ctr=deque' 'x=ctr(base)' 'while x: x.popleft()'
10000 loops, best of 3: 36 usec per loop

The needed precautions (doing the import outside the loop, making a fresh copy of the data within the loop) are so much easier to see and implement, this way...

于 2010-01-16T16:08:06.673 に答える
2

要素の数が少ない場合、両端キューとリストの作成にかかる時間は重要です。

f要素の数が増えると、これは結果では重要ではなくなります。

リストの作成がtimeit呼び出しの範囲外になるように、テストを書き直します。

編集：@Interjarが指摘しているように、クラスの初期化はメソッドのタイミングの外で行われるため、これがエントリ数が少ない場合に同様のタイミングが発生する理由ではありません。

于 2010-01-16T12:58:59.647 に答える