En el siguiente código, creo dos listas con los mismos valores: una lista sin ordenar (s_not), la otra ordenada (s_yes). Los valores son creados por randint(). Ejecuto un bucle para cada lista y lo cronometro.
import random import time for x in range(1,9): r = 10**x # do different val for the bound in randint() m = int(r/2) print("For rand", r) # s_not is non sorted list s_not = [random.randint(1,r) for i in range(10**7)] # s_yes is sorted s_yes = sorted(s_not) # do some loop over the sorted list start = time.time() for i in s_yes: if i > m: _ = 1 else: _ = 1 end = time.time() print("yes", end-start) # do the same to the unsorted list start = time.time() for i in s_not: if i > m: _ = 1 else: _ = 1 end = time.time() print("not", end-start) print()Con salida:
For rand 10 yes 1.0437555313110352 not 1.1074268817901611 For rand 100 yes 1.0802974700927734 not 1.1524150371551514 For rand 1000 yes 2.5082249641418457 not 1.129960298538208 For rand 10000 yes 3.145440101623535 not 1.1366300582885742 For rand 100000 yes 3.313387393951416 not 1.1393756866455078 For rand 1000000 yes 3.3180911540985107 not 1.1336982250213623 For rand 10000000 yes 3.3231537342071533 not 1.13503098487854 For rand 100000000 yes 3.311596393585205 not 1.1345293521881104Entonces, al aumentar el límite en randint(), el bucle sobre la lista ordenada se vuelve más lento. ¿Por qué?
Caché falla. Cuando los objetos N int se asignan uno al lado del otro, la memoria reservada para contenerlos tiende a estar en un fragmento contiguo. Entonces, rastrear la lista en orden de asignación tiende a acceder a la memoria que contiene los valores de los enteros en orden secuencial, contiguo y creciente también.
Barájelo, y el patrón de acceso al rastrear la lista también se aleatorizará. Los errores de caché abundan, siempre que haya suficientes objetos int diferentes que no quepan todos en la memoria caché.
En r==1 , y r==2 , CPython trata a estos pequeños ints como singletons, por lo que, por ejemplo, a pesar de que tiene 10 millones de elementos en la lista, en r==2 contiene solo (como máximo) 100 objetos int distintos. Todos los datos para aquellos caben en caché simultáneamente.
Sin embargo, más allá de eso, es probable que obtenga más y más objetos int distintos. Los cachés de hardware se vuelven cada vez más inútiles cuando el patrón de acceso es aleatorio.
ilustrando:
>>> from random import randint, seed >>> seed(987987987) >>> for x in range(1, 9): ... r = 10 ** x ... js = [randint(1, r) for _ in range(10_000_000)] ... unique = set(map(id, js)) ... print(f"{r:12,} {len(unique):12,}") ... 10 10 100 100 1,000 7,440,909 10,000 9,744,400 100,000 9,974,838 1,000,000 9,997,739 10,000,000 9,999,908 100,000,000 9,999,998La respuesta es probablemente la localidad de los datos. Los números enteros por encima de un cierto límite de tamaño se asignan dinámicamente. Cuando crea la lista, los objetos enteros se asignan (principalmente) desde la memoria cercana. Entonces, cuando recorre la lista, las cosas tienden a estar en caché y el precapturador de hardware puede colocarlas allí.
En el caso ordenado, los objetos se barajan, lo que genera más errores de caché.
Como dijeron los demás, el caché falla. No los valores/clasificación. Los mismos valores ordenados, pero con objetos recién creados secuencialmente, son rápidos nuevamente (en realidad, incluso un poco más rápido que el caso not ):
s_new = [--x for x in s_yes]Solo eligiendo un tamaño:
For rand 1000000 yes 3.6270992755889893 not 1.198620080947876 new 1.02010178565979 Observar las diferencias de direcciones de un elemento al siguiente (solo 10 6 elementos) muestra que, especialmente para s_new , los elementos están organizados secuencialmente en la memoria (el 99,2 % de las veces el siguiente elemento llegó 32 bytes después), mientras que para s_yes re totalmente no (sólo el 0,01% llegó 32 bytes más tarde):
s_yes: 741022 different address differences occurred. Top 5: Address difference 32 occurred 102 times. Address difference 0 occurred 90 times. Address difference 64 occurred 37 times. Address difference 96 occurred 17 times. Address difference 128 occurred 9 times. s_not: 1048 different address differences occurred. Top 5: Address difference 32 occurred 906649 times. Address difference 96 occurred 8931 times. Address difference 64 occurred 1845 times. Address difference -32 occurred 1816 times. Address difference -64 occurred 1812 times. s_new: 19 different address differences occurred. Top 5: Address difference 32 occurred 991911 times. Address difference 96 occurred 7825 times. Address difference -524192 occurred 117 times. Address difference 0 occurred 90 times. Address difference 64 occurred 37 times.Código para eso:
from collections import Counter for s in 's_yes', 's_not', 's_new': print(s + ':') ids = list(map(id, eval(s))) ctr = Counter(j - i for i, j in zip(ids, ids[1:])) print(' ', len(ctr), 'different address differences occurred. Top 5:') for delta, count in ctr.most_common(5): print(f' Address difference {delta} occurred {count} times.') print()