Dlaczego tworzenie zestawu z połączonej listy jest szybsze niż przy użyciu polecenia `.update`?

Question

Podczas próby odpowiedzi na pytanie What is the preferred way to compose a set from multiple lists in Python wykonałem analizę wydajności i doszedłem do wniosku z nieco zaskakującym wnioskiem.

Korzystanie

python -m timeit -s ' 
import itertools 
import random 
n=1000000 
random.seed(0) 
A = [random.randrange(1<<30) for _ in xrange(n)] 
B = [random.randrange(1<<30) for _ in xrange(n)] 
C = [random.randrange(1<<30) for _ in xrange(n)]' 

dla konfiguracji I timed następujące fragmenty:

> $TIMEIT 'set(A+B+C)' 
10 loops, best of 3: 872 msec per loop 

> $TIMEIT 's = set(A); s.update(B); s.update(C)' 
10 loops, best of 3: 930 msec per loop 

> $TIMEIT 's = set(itertools.chain(A,B,C))' 
10 loops, best of 3: 941 msec per loop 

ku mojemu zaskoczeniu, set(A+B+C) jest najszybciej pomimo faktu, że tworzy listę pośredni zawierający 3000000 elementy . .update i itertools.chain są wolniejsze, mimo że żadne z nich nie kopiuje żadnych list.

Co tu się dzieje?

---

EDIT: Na drugim komputerze (OS X 10.10.5, Python 2.7.10, 2.5GHz Core i7), wpadłem następujący skrypt (który uruchamia testy przodu i do tyłu, aby uniknąć efektów zamawiania):

SETUP='import itertools 
import random 
n=1000000 
random.seed(0) 
A = [random.randrange(1<<30) for _ in xrange(n)] 
B = [random.randrange(1<<30) for _ in xrange(n)] 
C = [random.randrange(1<<30) for _ in xrange(n)]' 

python -m timeit -s "$SETUP" 'set(A+B+C)' 
python -m timeit -s "$SETUP" 's = set(A); s.update(B); s.update(C)' 
python -m timeit -s "$SETUP" 's = set(itertools.chain(A,B,C))' 

python -m timeit -s "$SETUP" 's = set(itertools.chain(A,B,C))' 
python -m timeit -s "$SETUP" 's = set(A); s.update(B); s.update(C)' 
python -m timeit -s "$SETUP" 'set(A+B+C)' 

i uzyskał następujące wyniki:

10 loops, best of 3: 579 msec per loop 
10 loops, best of 3: 726 msec per loop 
10 loops, best of 3: 775 msec per loop 
10 loops, best of 3: 761 msec per loop 
10 loops, best of 3: 737 msec per loop 
10 loops, best of 3: 555 msec per loop 

teraz set(A+B+C) jest wyraźnie szybciej, a wyniki są dość stabl e - trudno jest przypisać to do zwykłego błędu pomiaru. Wielokrotne uruchamianie tego skryptu daje podobne wyniki.

Answer 1

uzyskać różne, nie zaskakujące, wyniki niż ci na moim Win 7 SP1 pudełku z podobnym procesorem Pythonie 2.7.10, gdzie set(A+B+C) wydaje się być sposobem najwolniej to zrobić, jak można by oczekiwać. Podobne wyniki uzyskano po ponownym włączeniu funkcji czyszczenia pamięci i w Pythonie 3.4.3.

użyłem mojego własnego wykonania oceniający srodowiska testowego na podstawie timeit i mam następujące wyniki:

kod

fastest to slowest execution speeds (Python 2.7.10) 
    (10 executions, best of 3 repetitions) 

set(A); s.update(B); s.update(C) : 4.787919 secs, rel speed 1.00x, 0.00% slower 
       set(A).update(B,C) : 6.463666 secs, rel speed 1.35x, 35.00% slower 
    set(itertools.chain(A,B,C)) : 6.743028 secs, rel speed 1.41x, 40.83% slower 
         set(A+B+C) : 8.030483 secs, rel speed 1.68x, 67.72% slower 

analizy porównawcze:

from __future__ import print_function 
import sys 
from textwrap import dedent 
import timeit 

N = 10 # Number of executions of each "algorithm" 
R = 3 # number of Repeations of executions 

# common setup for all algorithms (not timed) 
setup = dedent(""" 
    import itertools 
    import gc 
    import random 

    try: 
     xrange 
    except NameError: 
     xrange = range 

    random.seed(0) 
    n = 1000000 # number of elements in each list 
    A = [random.randrange(1<<30) for _ in xrange(n)] 
    B = [random.randrange(1<<30) for _ in xrange(n)] 
    C = [random.randrange(1<<30) for _ in xrange(n)] 

    # gc.enable() # to (re)enable garbage collection if desired 
""") 

algorithms = { 
    "set(A+B+C)": dedent(""" 
     s = set(A+B+C) 
    """), 

    "set(A); s.update(B); s.update(C)": dedent(""" 
     s = set(A); s.update(B); s.update(C) 
    """), 

    "set(itertools.chain(A,B,C))": dedent(""" 
     s = set(itertools.chain(A,B,C)) 
     """), 

    "set(A).update(B,C)": dedent(""" 
     s = set(A).update(B,C) 
     """), 
} 

# execute and time algorithms, collecting results 
timings = [ 
    (label, 
    min(timeit.repeat(algorithms[label], setup=setup, repeat=R, number=N)), 
    ) for label in algorithms 
] 

print('fastest to slowest execution speeds (Python {}.{}.{})\n'.format(
     *sys.version_info[:3]), 
     ' ({:,d} executions, best of {:d} repetitions)\n'.format(N, R)) 

longest = max(len(timing[0]) for timing in timings) # length of longest label 
ranked = sorted(timings, key=lambda t: t[1]) # ascending sort by execution time 
fastest = ranked[0][1] 
for timing in ranked: 
    print("{:>{width}} : {:9.6f} secs, rel speed {:4.2f}x, {:6.2f}% slower". 
      format(timing[0], timing[1], round(timing[1]/fastest, 2), 
        round((timing[1]/fastest - 1) * 100, 2), width=longest))