Pourquoi une liste Python est-elle plus lente lorsqu'elle est triée ?

Question

Dans le code suivant, je crée deux listes avec les mêmes valeurs : une liste non triée (s_not), l'autre triée (s_yes). Les valeurs sont créées par randint(). Je lance une boucle pour chaque liste et je la chronomètre.

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()

Avec sortie :

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.1345293521881104

Ainsi, lorsque l'on augmente la limite dans la fonction randint(), la boucle sur la liste triée devient plus lente. Pourquoi ?

Answer 1

Le cache manque. Lorsque N Si les objets sont alloués l'un après l'autre, la mémoire réservée pour les contenir a tendance à être dans un bloc contigu. Ainsi, parcourir la liste dans l'ordre d'allocation tend à accéder à la mémoire contenant les valeurs des int dans un ordre séquentiel, contigu et croissant également.

Mélangez-la, et le modèle d'accès lors de l'exploration de la liste est également aléatoire. Les ratés du cache abondent, à condition qu'il y ait suffisamment d'objets int différents pour qu'ils ne tiennent pas tous dans le cache.

Sur r==1 y r==2 il se trouve que CPython traite ces petits ints comme des singletons, donc, par exemple, bien que vous ayez 10 millions d'éléments dans la liste, à r==2 il ne contient que (au maximum) 100 objets int distincts. Toutes les données de ceux-ci tiennent dans le cache simultanément.

Au-delà, cependant, vous risquez d'obtenir de plus en plus d'objets int distincts. Les caches matériels deviennent alors de plus en plus inutiles lorsque le modèle d'accès est aléatoire.

Illustrer :

>>> 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,998

Answer 2

Comme les autres l'ont dit, les ratés du cache. Pas les valeurs/le tri. Les mêmes valeurs triées, mais avec des objets fraîchement créés de manière séquentielle, sont à nouveau rapides (en fait, même un peu plus rapides que la méthode du not cas) :

s_new = [--x for x in s_yes]

Je choisis juste une taille :

For rand 1000000
yes 3.6270992755889893
not 1.198620080947876
new 1.02010178565979

En examinant les différences d'adresses d'un élément à l'autre (seulement 10 6 ) montre que, surtout pour les s_new les éléments sont joliment disposés séquentiellement dans la mémoire (99,2 % du temps, l'élément suivant arrive 32 octets plus tard), alors que dans le cas de s_yes ils ne le sont absolument pas (seulement 0,01% sont venus 32 octets plus tard) :

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.

Un code pour ça :

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()

Answer 3

La réponse est probablement la localité des données. Les nombres entiers dépassant une certaine taille limite sont alloués dynamiquement. Lorsque vous créez la liste, les objets entiers sont alloués à partir de la mémoire (généralement) proche. Ainsi, lorsque vous parcourez la liste en boucle, les objets ont tendance à être dans le cache et le préfetcheur matériel peut les y placer.

Dans le cas d'un tri, les objets sont mélangés, ce qui entraîne un plus grand nombre de manques dans le cache.