Warum ist das Kopieren einer gemischten Liste viel langsamer?

Das range(10**6)zehnmalige Kopieren einer gemischten Liste dauert ungefähr 0,18 Sekunden: (Dies sind fünf Läufe.)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

Das zehnmalige Kopieren der nicht gemischten Liste dauert ungefähr 0,05 Sekunden:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Hier ist mein Testcode:

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)

Ich habe auch versucht, mit zu kopieren a[:], die Ergebnisse waren ähnlich (dh großer Geschwindigkeitsunterschied)

Warum der große Geschwindigkeitsunterschied? Ich kenne und verstehe den Geschwindigkeitsunterschied im berühmten Warum ist es schneller, ein sortiertes Array zu verarbeiten als ein unsortiertes Array? Beispiel, aber hier hat meine Verarbeitung keine Entscheidungen. Es wird nur blind die Referenzen in der Liste kopiert, nein?

Ich verwende Python 2.7.12 unter Windows 10.

Bearbeiten: Versuchte jetzt auch Python 3.5.2, die Ergebnisse waren fast gleich (konsistent gemischt um 0,17 Sekunden, konsistent gemischt um 0,05 Sekunden). Hier ist der Code dafür:

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

Das Interessante ist, dass es von der Reihenfolge abhängt, in der die Ganzzahlen zuerst erstellt werden. Zum Beispiel anstatt shuffleeine zufällige Sequenz zu erstellen mit 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))

Dies ist so schnell wie das Kopieren Ihres list(range(10**6))(erstes und schnelles Beispiel).

Wenn Sie jedoch mischen - dann sind Ihre Ganzzahlen nicht mehr in der Reihenfolge, in der sie zuerst erstellt wurden. Das macht es langsam.

Ein kurzes Intermezzo:

• Alle Python-Objekte befinden sich auf dem Heap, daher ist jedes Objekt ein Zeiger.
• Das Kopieren einer Liste ist eine flache Operation.
• Python verwendet jedoch die Referenzzählung. Wenn ein Objekt in einen neuen Container gestellt wird, muss die Referenzanzahl erhöht werden ( Py_INCREFinlist_slice ), sodass Python wirklich dorthin gehen muss, wo sich das Objekt befindet. Es kann nicht einfach die Referenz kopieren.

Wenn Sie also Ihre Liste kopieren, erhalten Sie jedes Element dieser Liste und fügen es "wie es ist" in die neue Liste ein. Wenn Ihr nächster Artikel kurz nach dem aktuellen erstellt wurde, besteht eine gute Chance (keine Garantie!), Dass er daneben auf dem Heap gespeichert wird.

Nehmen wir an, dass Ihr Computer jedes Mal, wenn er ein Element in den Cache lädt, auch die xElemente im nächsten Speicher lädt (Cache-Lokalität). Dann kann Ihr Computer das Referenzzählinkrement für x+1Elemente im selben Cache durchführen!

Bei der gemischten Sequenz werden weiterhin die Elemente im nächsten Speicher geladen, diese sind jedoch nicht die Elemente im nächsten in der Liste. Es kann also das Referenzzählinkrement nicht ausführen, ohne "wirklich" nach dem nächsten Element zu suchen.

TL; DR: Die tatsächliche Geschwindigkeit hängt davon ab, was vor dem Kopieren passiert ist: In welcher Reihenfolge wurden diese Elemente erstellt und in welcher Reihenfolge befinden sich diese in der Liste.

Sie können dies überprüfen, indem Sie sich Folgendes ansehen id:

CPython-Implementierungsdetail: Dies ist die Adresse des Objekts im Speicher.

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

Nur um einen kurzen Auszug zu zeigen:

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

Diese Objekte sind also wirklich "nebeneinander auf dem Haufen". Mit sind shufflesie nicht:

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

Was zeigt, dass diese im Gedächtnis nicht wirklich nebeneinander liegen:

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

Wichtige Notiz:

Ich habe mir das nicht ausgedacht. Die meisten Informationen finden Sie im Blogpost von Ricky Stewart .

Diese Antwort basiert auf der "offiziellen" CPython-Implementierung von Python. Die Details in anderen Implementierungen (Jython, PyPy, IronPython, ...) können abweichen. Vielen Dank an JörgWMittag für diesen Hinweis .

Wenn Sie die Listenelemente mischen, haben sie eine schlechtere Referenzlokalität, was zu einer schlechteren Cache-Leistung führt.

Sie könnten denken, dass beim Kopieren der Liste nur die Referenzen und nicht die Objekte kopiert werden, sodass ihre Position auf dem Heap keine Rolle spielen sollte. Beim Kopieren muss jedoch weiterhin auf jedes Objekt zugegriffen werden, um die Nachzählung zu ändern.

Wie bereits von anderen erklärt, es ist nicht nur die Referenzen zu kopieren , sondern erhöht auch die Referenzzahl innerhalb der Objekte und damit die Objekte werden abgerufen und der Cache eine Rolle spielt.

Hier möchte ich nur weitere Experimente hinzufügen. Nicht so sehr über gemischt oder nicht gemischt (wo beim Zugriff auf ein Element der Cache möglicherweise übersehen wird, aber die folgenden Elemente in den Cache gelangen, damit sie getroffen werden). Aber über das Wiederholen von Elementen, bei denen spätere Zugriffe auf dasselbe Element den Cache treffen könnten, weil sich das Element noch im Cache befindet.

Testen eines normalen Bereichs:

>>> from timeit import timeit
>>> a = range(10**7)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[5.1915339142808925, 5.1436351868889645, 5.18055115701749]

Eine Liste derselben Größe, bei der jedoch nur ein Element immer wieder wiederholt wird, ist schneller, da sie ständig in den Cache gelangt:

>>> a = [0] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.125743135926939, 4.128927210087596, 4.0941229388550795]

Und es scheint egal zu sein, um welche Zahl es sich handelt:

>>> a = [1234567] * 10**7
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[4.124106479141709, 4.156590225249886, 4.219242600790949]

Interessanterweise wird es noch schneller, wenn ich stattdessen dieselben zwei oder vier Elemente wiederhole:

>>> a = [0, 1] * (10**7 / 2)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.130586101607932, 3.1001001764957294, 3.1318465707127814]

>>> a = [0, 1, 2, 3] * (10**7 / 4)
>>> [timeit(lambda: list(a), number=100) for _ in range(3)]
[3.096105435911994, 3.127148431279352, 3.132872673690855]

Ich denke, etwas mag es nicht, wenn derselbe einzelne Zähler ständig erhöht wird. Vielleicht ist eine Pipeline stehen geblieben, weil jede Erhöhung auf das Ergebnis der vorherigen Erhöhung warten muss, aber dies ist eine wilde Vermutung.

Wie auch immer, versuchen Sie dies für eine noch größere Anzahl von wiederholten Elementen:

from timeit import timeit
for e in range(26):
    n = 2**e
    a = range(n) * (2**25 / n)
    times = [timeit(lambda: list(a), number=20) for _ in range(3)]
    print '%8d ' % n, '  '.join('%.3f' % t for t in times), ' => ', sum(times) / 3

Die Ausgabe (erste Spalte ist die Anzahl der verschiedenen Elemente, für die ich dreimal teste und dann den Durchschnitt nehme):

       1  2.871  2.828  2.835  =>  2.84446732686
       2  2.144  2.097  2.157  =>  2.13275338734
       4  2.129  2.297  2.247  =>  2.22436720645
       8  2.151  2.174  2.170  =>  2.16477771575
      16  2.164  2.159  2.167  =>  2.16328197911
      32  2.102  2.117  2.154  =>  2.12437970598
      64  2.145  2.133  2.126  =>  2.13462250728
     128  2.135  2.122  2.137  =>  2.13145065221
     256  2.136  2.124  2.140  =>  2.13336283943
     512  2.140  2.188  2.179  =>  2.1688431668
    1024  2.162  2.158  2.167  =>  2.16208440826
    2048  2.207  2.176  2.213  =>  2.19829998424
    4096  2.180  2.196  2.202  =>  2.19291917834
    8192  2.173  2.215  2.188  =>  2.19207065277
   16384  2.258  2.232  2.249  =>  2.24609975704
   32768  2.262  2.251  2.274  =>  2.26239771771
   65536  2.298  2.264  2.246  =>  2.26917420394
  131072  2.285  2.266  2.313  =>  2.28767871168
  262144  2.351  2.333  2.366  =>  2.35030805124
  524288  2.932  2.816  2.834  =>  2.86047313113
 1048576  3.312  3.343  3.326  =>  3.32721167007
 2097152  3.461  3.451  3.547  =>  3.48622758473
 4194304  3.479  3.503  3.547  =>  3.50964316455
 8388608  3.733  3.496  3.532  =>  3.58716466865
16777216  3.583  3.522  3.569  =>  3.55790996695
33554432  3.550  3.556  3.512  =>  3.53952594744

Von ungefähr 2,8 Sekunden für ein einzelnes (wiederholtes) Element fällt es für 2, 4, 8, 16, ... verschiedene Elemente auf ungefähr 2,2 Sekunden ab und bleibt bei ungefähr 2,2 Sekunden bis zu den Hunderttausenden. Ich denke, dies verwendet meinen L2-Cache (4 × 256 KB, ich habe einen i7-6700 ).

Dann steigen die Zeiten in wenigen Schritten auf 3,5 Sekunden. Ich denke, dies verwendet eine Mischung aus meinem L2-Cache und meinem L3-Cache (8 MB), bis dies ebenfalls "erschöpft" ist.

Am Ende bleibt es bei ungefähr 3,5 Sekunden, denke ich, weil meine Caches bei den wiederholten Elementen nicht mehr helfen.

Vor dem Mischen sind die benachbarten Indexobjekte, wenn sie im Heap zugeordnet sind, im Speicher benachbart, und die Speicher-Trefferquote ist beim Zugriff hoch. Nach dem Mischen befindet sich das Objekt des benachbarten Index der neuen Liste nicht im Speicher. Angrenzend ist die Trefferquote sehr schlecht.