4

次の簡単な例では、乱数のリストをソートする 2 つの関数があります。最初のメソッドはジェネレータ式を渡しsorted、2 番目のメソッドは最初にリストを作成します。

import random
l = [int(1000*random.random()) for i in xrange(10*6)]

def sort_with_generator():
    return sorted(a for a in l)

def sort_with_list():
    return sorted([a for a in l])

ライン プロファイラーでのベンチマークは、2 番目のオプション ( sort_with_list) がジェネレーター式の約 2 倍の速度であることを示しています。

何が起こっているのか、なぜ最初の方法が2番目の方法よりもずっと遅いのか、誰でも説明できますか?

4

3 に答える 3

6

最初の例は、リストを反復処理するジェネレータ式です。2 番目の例は、リストを反復処理するリスト式です。実際、2 番目の例はわずかに高速です。

>>> import timeit
>>> timeit("sorted(a for a in l)", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.963912010192871
>>> timeit("sorted([a for a in l])", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.021576881408691

この理由は間違いなく、リストの作成は一度に行われますが、ジェネレーターの反復には関数呼び出しが必要です。

ジェネレーターは、このような小さなリストを高速化するものではありません (リストには 60 個の要素があり、非常に小さいです)。主に、長いリストを作成するときにメモリを節約するためです。

于 2013-09-06T02:15:17.360 に答える
2

のソースを見ると、sorted渡したシーケンスが最初に新しいリストにコピーされます。

newlist = PySequence_List(seq);

generator-->は-->listよりも遅いようです。listlist

>>> timeit.timeit('x = list(l)', setup = 'l = xrange(1000)')
16.656711101531982
>>> timeit.timeit('x = list(l)', setup = 'l = range(1000)')
4.525658845901489

コピーを作成する必要がある理由については、並べ替えのしくみを考えてみてください。並べ替えは線形アルゴリズムではありません。データを複数回移動し、データを両方向にトラバースすることもあります。ジェネレーターは、開始からその後のどこかまで、一度だけ反復するシーケンスを生成することを目的としています。リストはランダム アクセスを許可します。

一方、ジェネレーターからリストを作成することは、メモリ内に 1 つのリストのみを意味しますが、リストのコピーを作成することは、メモリ内に 2 つのリストを意味します。古き良き時空間のトレードオフ。

Python は、マージソートと挿入ソートのハイブリッドであるTimsortを使用します。

于 2013-09-06T02:57:21.940 に答える
0

リスト式は、最初にデータをメモリにロードします。次に、結果のリストで操作を行います。割り当て時間をT2(2 番目のケースの場合) とします。ジェネレータ式は一度に時間を割り当てませんが、 time のイテレータ値を変更しますt1[i]。すべての合計はt1[i]になりますT1。T1≒ T2.

ただし、 を呼び出すsorted()と、最初のケースでは、T1sort( ) と比較してすべてのペアの割り当てメモリの時間が追加されますtx1[i]。その結果、T1すべての合計で加算されますtx1[i]。

したがって、T2<T1 + sum(tx1[i])

于 2013-09-06T02:20:54.367 に答える