python - Why is copying a shuffled list much slower? -

copying shuffled range(10**6) list ten times takes me 0.18 seconds: (these 5 runs)

0.175597017661 0.173731403198 0.178601711594 0.180330912952 0.180811964451 

copying unshuffled list ten times takes me 0.05 seconds:

0.058402235973 0.0505464636856 0.0509734306934 0.0526022752744 0.0513324916184 

here's testing code:

from timeit import timeit import random  = range(10**6) random.shuffle(a)    # remove second test. = list(a)          # attempt "normalize" list. _ in range(5):     print timeit(lambda: list(a), number=10) 

i tried copying a[:], results similar (i.e., big speed difference)

why big speed difference? know , understand speed difference in famous why faster process sorted array unsorted array? example, here processing has no decisions. it's blindly copying references inside list, no?

i'm using python 2.7.12 on windows 10.

edit: tried python 3.5.2 now, results same (shuffled consistently around 0.17 seconds, unshuffled consistently around 0.05 seconds). here's code that:

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

the interesting bit depends on order in integers first created. example instead of shuffle create random sequence random.randint:

from timeit import timeit import random  = [random.randint(0, 10**6) _ in range(10**6)] _ in range(5):     print(timeit(lambda: list(a), number=10)) 

this fast copying list(range(10**6)) (first , fast example).

however when shuffle - integers aren't in order first created anymore, that's makes slow.

a quick intermezzo:

• all python objects on heap, every object pointer.
• copying list shallow operation.
• however python uses reference counting when object put in new container it's reference count must incremented (py_incref in list_slice), python needs go object is. can't copy reference.

so when copy list each item of list , put "as is" in new list. when next item created shortly after current 1 there chance (no guarantee!) it's saved next on heap.

let's assume whenever computer loads item in cache loads x next-in-memory items (cache locality). computer can perform reference count increment x+1 items on same cache!

with shuffled sequence still loads next-in-memory items these aren't ones next-in-list. can't perform reference-count increment without "really" looking next item.

tl;dr: actual speed depends on happened before copy: in order these items created , in order these in list.

---

you can verify looking @ id:

cpython implementation detail: address of object in memory.

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

just show short excerpt:

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 

so these objects "next each other on heap". shuffle aren't:

import random = list(range(10**6, 100+10**6)) random.shuffle(a) last = none item in a:     if last not none:         print('diff', id(item) - id(last))     last = item 

which shows these not next each other in memory:

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 

---

important note:

i haven't thought myself. of informations can found in blogpost of ricky stewart.

this answer based on "official" cpython implementation of python. details in other implementations (jython, pypy, ironpython, ...) may different. @jörgwmittag for pointing out.