[解決済み] シャッフルされたリストのコピーが遅いのはなぜですか？

疑問点

シャッフルしたものをコピーする range(10**6) のリストを 10 回コピーすると、約 0.18 秒かかります。(これは5回実行したものです)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

シャッフルされていないリストを10回コピーすると、約0.05秒かかります。

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

以下は私のテストコードです。

from timeit import timeit
import random

a = range(10**6)
random.shuffle(a)    # Remove this for the second test.
a = list(a)          # Just an attempt to "normalize" the list.
for _ in range(5):
    print timeit(lambda: list(a), number=10)

また、コピーする際に a[:] でコピーしてみましたが、結果は同じようなものでした（つまり、大きな速度差がありました）。

なぜ、大きな速度差が出るのか？速度差については、有名な なぜソートされていない配列よりソートされた配列の方が処理が速いのか？ の例ですが、ここでは私の処理には何の判断もありません。リスト内の参照をただやみくもにコピーしているだけではないか？

Windows10でPython2.7.12を使用しています。

編集しています。 Python 3.5.2でも試してみましたが、結果はほぼ同じでした(シャッフルされるのは一貫して0.17秒前後、シャッフルされないのは一貫して0.05秒前後)。以下はそのコードです。

a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

どのように解決するのですか？

面白いのは、整数の順番に依存することです。 最初 が作られる順番に依存します。例えば、代わりに shuffle でランダムなシーケンスを作成します。 random.randint :

from timeit import timeit
import random

a = [random.randint(0, 10**6) for _ in range(10**6)]
for _ in range(5):
    print(timeit(lambda: list(a), number=10))

をコピーするのと同じ速さです。 list(range(10**6)) をコピーするのと同じくらい速いです (最初の、速い例)。

しかし、シャッフルすると、整数が最初に作られた順番でなくなってしまうので、遅くなります。

簡単な間奏曲です。

• すべてのPythonオブジェクトはヒープ上にあるので、すべてのオブジェクトはポインタです。
• リストをコピーするのは浅い操作です。
• しかし、Pythonは参照カウントを使うので、オブジェクトが新しいコンテナに入れられると、その参照カウントはインクリメントされなければなりません( Py_INCREF で list_slice ) で、Pythonは本当にオブジェクトがある場所に行く必要があります。単に参照をコピーすることはできません。

ですから、リストをコピーするときは、そのリストの各項目を取得して、新しいリストに "そのまま" 入れるのです。次のアイテムが現在のアイテムのすぐ後に作成された場合、ヒープ上でその隣に保存される可能性は十分にあります (保証はありません!)。

コンピュータがキャッシュ内のアイテムをロードするたびに、キャッシュ内の x 次のメモリ内の項目もロードすると仮定します (キャッシュの局所性)。この場合、コンピュータは参照カウントのインクリメントを x+1 アイテムに対して参照カウントのインクリメントを行うことができます。

シャッフルされたシーケンスでは、まだ次のメモリ内のアイテムをロードしていますが、これらは次のリスト内のものではありません。そのため、次のアイテムを探すことなく、参照カウントのインクリメントを実行することができません。

TL;DR: 実際の速度は、コピーの前に何が起こったかに依存します：これらのアイテムがどのような順序で作成され、これらがリストの中でどのような順序であるか。

を見ることで検証できます。 id :

CPythonの実装の詳細です。これはメモリ上のオブジェクトのアドレスです。

a = list(range(10**6, 10**6+100))
for item in a:
    print(id(item))

短い抜粋を表示するだけです。

1496489995888
1496489995920  # +32
1496489995952  # +32
1496489995984  # +32
1496489996016  # +32
1496489996048  # +32
1496489996080  # +32
1496489996112
1496489996144
1496489996176
1496489996208
1496489996240
1496507297840
1496507297872
1496507297904
1496507297936
1496507297968
1496507298000
1496507298032
1496507298064
1496507298096
1496507298128
1496507298160
1496507298192

つまり、これらのオブジェクトはヒープ上で本当に "隣り合っているのです" 。とは shuffle ではそうではありません。

import random
a = list(range(10**6, 100+10**6))
random.shuffle(a)
last = None
for item in a:
    if last is not None:
        print('diff', id(item) - id(last))
    last = item

これは、これらがメモリ上で実際に隣り合っていないことを示しています。

diff 736
diff -64
diff -17291008
diff -128
diff 288
diff -224
diff 17292032
diff -1312
diff 1088
diff -17292384
diff 17291072
diff 608
diff -17290848
diff 17289856
diff 928
diff -672
diff 864
diff -17290816
diff -128
diff -96
diff 17291552
diff -192
diff 96
diff -17291904
diff 17291680
diff -1152
diff 896
diff -17290528
diff 17290816
diff -992
diff 448

重要なお知らせです。

私自身が考えたわけではありません。ほとんどの情報が リッキー・スチュワート氏のブログ記事 .

この回答は、PythonのCPythonの公式実装に基づいています。他の実装(Jython, PyPy, IronPython, ...)の詳細は異なるかもしれません。ありがとうございます @JörgWMittag によるご指摘に感謝します。 .