Por que copiar uma lista embaralhada é muito mais lento?

Copiar uma range(10**6)lista embaralhada dez vezes leva cerca de 0,18 segundos: (são cinco execuções)

0.175597017661
0.173731403198
0.178601711594
0.180330912952
0.180811964451

Copiar a lista não embaralhada dez vezes leva cerca de 0,05 segundos:

0.058402235973
0.0505464636856
0.0509734306934
0.0526022752744
0.0513324916184

Este é meu código de teste:

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)

Também tentei copiar com a[:], os resultados foram semelhantes (ou seja, grande diferença de velocidade)

Por que a grande diferença de velocidade? Eu sei e entendo a diferença de velocidade no famoso Por que é mais rápido processar um array ordenado do que um array não ordenado? exemplo, mas aqui meu processamento não tem decisões. É apenas copiar cegamente as referências dentro da lista, não?

Estou usando o Python 2.7.12 no Windows 10.

Edit: Python 3.5.2 experimentado também agora, os resultados foram quase os mesmos (embaralhado consistentemente em torno de 0,17 segundos, não embaralhado consistentemente em torno de 0,05 segundos). Aqui está o código para isso:

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

O interessante é que isso depende da ordem em que os inteiros são criados pela primeira vez. Por exemplo, em vez de shufflecriar uma sequência aleatória com 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))

Isso é tão rápido quanto copiar o seu list(range(10**6))(primeiro e rápido exemplo).

No entanto, quando você embaralha - então seus inteiros não estão mais na ordem em que foram criados, é o que o torna lento.

Um intermezzo rápido:

• Todos os objetos Python estão no heap, então cada objeto é um ponteiro.
• Copiar uma lista é uma operação superficial.
• No entanto, o Python usa a contagem de referência, portanto, quando um objeto é colocado em um novo contêiner, sua contagem de referência deve ser incrementada ( Py_INCREFemlist_slice ), de modo que o Python realmente precisa ir para onde o objeto está. Ele não pode simplesmente copiar a referência.

Portanto, ao copiar sua lista, você obtém cada item dessa lista e os coloca "como estão" na nova lista. Quando seu próximo item foi criado, logo após o atual, há uma boa chance (não há garantia!) De que ele seja salvo próximo a ele na pilha.

Vamos supor que sempre que seu computador carregar um item no cache, ele também carregará os xpróximos itens na memória (localidade do cache). Então seu computador pode realizar o incremento da contagem de referência para x+1itens no mesmo cache!

Com a sequência embaralhada, ele ainda carrega os próximos itens da memória, mas esses não são os próximos da lista. Portanto, ele não pode realizar o incremento da contagem de referência sem "realmente" procurar o próximo item.

TL; DR: A velocidade real depende do que aconteceu antes da cópia: em que ordem esses itens foram criados e em que ordem estão na lista.

Você pode verificar isso olhando para id:

Detalhe de implementação do CPython: Este é o endereço do objeto na memória.

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

Só para mostrar um pequeno trecho:

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

Portanto, esses objetos estão realmente "próximos uns dos outros na pilha". Com shuffleeles não são:

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

O que mostra que eles não estão realmente próximos um do outro na memória:

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

Nota importante:

Eu não pensei nisso sozinho. A maioria das informações pode ser encontrada na postagem do blog de Ricky Stewart .

Esta resposta é baseada na implementação "oficial" do CPython do Python. Os detalhes em outras implementações (Jython, PyPy, IronPython, ...) podem ser diferentes. Obrigado @ JörgWMittag por apontar isso .

Quando você embaralha os itens da lista, eles têm pior localidade de referência, levando a um pior desempenho do cache.

Você pode pensar que copiar a lista apenas copia as referências, não os objetos, portanto, suas localizações no heap não devem importar. No entanto, a cópia ainda envolve acessar cada objeto para modificar o refcount.

Como explicado por outros, não se trata apenas de copiar as referências, mas também aumenta as contagens de referência dentro dos objetos e, portanto, os objetos são acessados ​​e o cache desempenha um papel.

Aqui, eu só quero adicionar mais experimentos. Não tanto sobre embaralhado versus não embaralhado (onde acessar um elemento pode perder o cache, mas obter os seguintes elementos no cache para que sejam atingidos). Mas sobre elementos de repetição, onde acessos posteriores do mesmo elemento podem atingir o cache porque o elemento ainda está no cache.

Testando uma faixa normal:

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

Uma lista do mesmo tamanho, mas com apenas um elemento repetido várias vezes, é mais rápida porque atinge o cache o tempo todo:

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

E não parece importar qual é o número:

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

Curiosamente, fica ainda mais rápido quando, em vez disso, repito os mesmos dois ou quatro elementos:

>>> 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]

Acho que algo não gosta que o mesmo contador único esteja sempre aumentando. Talvez um pouco pipeline pare porque cada aumento precisa esperar pelo resultado do aumento anterior, mas esse é um palpite.

De qualquer forma, tentando fazer isso para um número ainda maior de elementos repetidos:

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

A saída (a primeira coluna é o número de elementos diferentes, para cada um testo três vezes e depois tiro a média):

       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

Portanto, de cerca de 2,8 segundos para um único elemento (repetido), ele cai para cerca de 2,2 segundos para 2, 4, 8, 16, ... elementos diferentes e permanece em cerca de 2,2 segundos até os cem mil. Eu acho que isso usa meu cache L2 (4 × 256 KB, eu tenho um i7-6700 ).

Depois de alguns passos, o tempo sobe para 3,5 segundos. Eu acho que isso usa uma mistura de meu cache L2 e meu cache L3 (8 MB) até que esteja "esgotado" também.

No final, ele fica em torno de 3,5 segundos, acho que porque meus caches não ajudam mais com os elementos repetidos.

Antes do embaralhamento, quando alocado no heap, os objetos de índice adjacentes são adjacentes na memória e a taxa de acerto de memória é alta quando acessada; após o embaralhamento, o objeto do índice adjacente da nova lista não está na memória. Adjacente, a taxa de acerto é muito baixa.