range(10**6)Dziesięciokrotne skopiowanie potasowanej listy zajmuje mi około 0,18 sekundy: (to jest pięć uruchomień)
0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451
Dziesięciokrotne skopiowanie nieprzetasowanej listy zajmuje mi około 0,05 sekundy:
0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184
Oto mój kod testowy:
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)
Próbowałem też kopiować z a[:], wyniki były podobne (tj. Duża różnica prędkości)
Skąd ta duża różnica prędkości? Znam i rozumiem różnicę prędkości w słynnym Dlaczego szybciej przetwarzać posortowaną tablicę niż nieposortowaną? na przykład, ale tutaj moje przetwarzanie nie ma żadnych decyzji. To po prostu ślepe kopiowanie referencji z listy, prawda?
Używam Pythona 2.7.12 w systemie Windows 10.
Edycja: Próbowałem teraz również Pythona 3.5.2, wyniki były prawie takie same (tasowane konsekwentnie około 0,17 sekundy, nieprzetasowane konsekwentnie około 0,05 sekundy). Oto kod:
a = list(range(10**6))
random.shuffle(a)
a = list(a)
for _ in range(5):
print(timeit(lambda: list(a), number=10))
źródło
0.25w każdej iteracji każdego z testów. Na mojej platformie kolejność ma znaczenie.Odpowiedzi:
Interesujące jest to, że zależy to od kolejności, w jakiej liczby całkowite są tworzone po raz pierwszy . Na przykład zamiast
shuffletworzyć losową sekwencję zrandom.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))Jest to tak szybkie, jak skopiowanie twojego
list(range(10**6))(pierwszy i szybki przykład).Jednak podczas tasowania - wtedy liczby całkowite nie są już w takiej kolejności, w jakiej zostały utworzone, to właśnie sprawia, że jest powolny.
Szybkie intermezzo:
Py_INCREFinlist_slice), więc Python naprawdę musi przejść do miejsca, w którym znajduje się obiekt. Nie może po prostu skopiować odniesienia.Więc kiedy kopiujesz swoją listę, otrzymujesz każdą pozycję z tej listy i umieszczasz ją „tak, jak jest” na nowej liście. Kiedy twój następny przedmiot został utworzony wkrótce po obecnym, istnieje duża szansa (bez gwarancji!), Że zostanie on zapisany obok niego na stercie.
Załóżmy, że za każdym razem, gdy komputer ładuje element w pamięci podręcznej, ładuje również
xnastępne elementy w pamięci (lokalizacja pamięci podręcznej). Wtedy twój komputer może wykonać przyrost liczby odwołań dlax+1pozycji w tej samej pamięci podręcznej!Z potasowaną sekwencją nadal ładuje następne elementy w pamięci, ale nie są to następne elementy na liście. Więc nie może wykonać inkrementacji liczby odwołań bez "naprawdę" szukania następnego elementu.
TL; DR: Rzeczywista prędkość zależy od tego, co wydarzyło się przed kopiowaniem: w jakiej kolejności zostały utworzone te elementy iw jakiej kolejności znajdują się na liście.
Możesz to sprawdzić, patrząc na
id:a = list(range(10**6, 10**6+100)) for item in a: print(id(item))Żeby pokazać krótki fragment:
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 1496507298192Więc te obiekty są naprawdę „obok siebie na stercie”. Z
shufflenimi nie są: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 = itemCo pokazuje, że tak naprawdę nie są one obok siebie w pamięci:
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 448Ważna uwaga:
Sam tego nie wymyśliłem. Większość informacji można znaleźć w poście Ricky'ego Stewarta .
Ta odpowiedź jest oparta na „oficjalnej” implementacji języka Python w CPythonie. Szczegóły w innych implementacjach (Jython, PyPy, IronPython, ...) mogą być inne. Dzięki @ JörgWMittag za wskazanie tego .
źródło
list_sliceiw linii 453 możesz zobaczyćPy_INCREF(v);wywołanie, które musi uzyskać dostęp do obiektu przydzielonego do sterty.a = [0] * 10**7(z 10 ** 6, ponieważ było zbyt niestabilne), które jest nawet szybsze niż używaniea = range(10**7)(o współczynnik około 1,25). Oczywiście, ponieważ jest to jeszcze lepsze w przypadku buforowania.[0,1,2,3]*((10**6) // 4)jest tak szybkie, jaka = [0] * 10**6. Jednak w przypadku liczb całkowitych od 0-255 pojawia się inny fakt: są one internowane, więc kolejność ich tworzenia (wewnątrz skryptu) nie jest już ważna - ponieważ są tworzone podczas uruchamiania Pythona.Podczas tasowania elementów listy mają gorszą lokalizację odniesienia, co prowadzi do gorszej wydajności pamięci podręcznej.
Możesz pomyśleć, że skopiowanie listy po prostu kopiuje odniesienia, a nie obiekty, więc ich położenie na stercie nie powinno mieć znaczenia. Jednak kopiowanie nadal obejmuje dostęp do każdego obiektu w celu zmodyfikowania refcount.
źródło
Jak wyjaśnili inni, nie tylko kopiuje referencje, ale także zwiększa liczbę referencji wewnątrz obiektów, a tym samym uzyskuje się dostęp do obiektów, a pamięć podręczna odgrywa rolę.
Tutaj chcę tylko dodać więcej eksperymentów. Nie tyle o shuffled vs unshuffled (gdzie dostęp do jednego elementu może przegapić pamięć podręczną, ale pobierz następujące elementy do pamięci podręcznej, aby zostały trafione). Ale o powtarzających się elementach, gdzie późniejszy dostęp do tego samego elementu może trafić do pamięci podręcznej, ponieważ element nadal znajduje się w pamięci podręcznej.
Testowanie normalnego zakresu:
>>> from timeit import timeit >>> a = range(10**7) >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [5.1915339142808925, 5.1436351868889645, 5.18055115701749]Lista o tym samym rozmiarze, ale z tylko jednym powtarzanym w kółko elementem, jest szybsza, ponieważ cały czas trafia do pamięci podręcznej:
>>> a = [0] * 10**7 >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [4.125743135926939, 4.128927210087596, 4.0941229388550795]I wydaje się, że nie ma znaczenia, jaka to liczba:
>>> a = [1234567] * 10**7 >>> [timeit(lambda: list(a), number=100) for _ in range(3)] [4.124106479141709, 4.156590225249886, 4.219242600790949]Co ciekawe, robi się to jeszcze szybciej, gdy zamiast tego powtarzam te same dwa lub cztery elementy:
>>> 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]Myślę, że coś nie lubi tego samego pojedynczego licznika zwiększanego przez cały czas. Może jakieś opóźnienie w rurociągu, ponieważ każdy wzrost musi czekać na wynik poprzedniego wzrostu, ale jest to szalone przypuszczenie.
W każdym razie, próbując tego dla jeszcze większej liczby powtarzających się elementów:
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) / 3Wynik (pierwsza kolumna to liczba różnych elementów, dla każdego testuję trzy razy, a następnie biorę średnią):
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.53952594744Czyli od około 2,8 sekundy dla pojedynczego (powtarzanego) elementu spada do około 2,2 sekundy dla 2, 4, 8, 16, ... różnych elementów i pozostaje na około 2,2 sekundy do setek tysięcy. Myślę, że to używa mojej pamięci podręcznej L2 (4 × 256 KB, mam i7-6700 ).
Następnie po kilku krokach czas dochodzi do 3,5 sekundy. Myślę, że to używa kombinacji mojej pamięci podręcznej L2 i mojej pamięci podręcznej L3 (8 MB), dopóki to również nie zostanie „wyczerpane”.
Pod koniec wydaje mi się, że pozostaje to około 3,5 sekundy, ponieważ moje pamięci podręczne nie pomagają już z powtarzającymi się elementami.
źródło
Przed tasowaniem, po przydzieleniu w stercie, sąsiednie obiekty indeksu sąsiadują ze sobą w pamięci, a wskaźnik trafień w pamięć jest wysoki podczas uzyskiwania do nich dostępu; po tasowaniu obiekt z sąsiedniego indeksu nowej listy nie znajduje się w pamięci. Obok, wskaźnik trafień jest bardzo słaby.
źródło