Perché creare un set da un elenco concatenato più velocemente di usare `.update`?

Question

Durante il tentativo di rispondere a What is the preferred way to compose a set from multiple lists in Python, ho eseguito alcune analisi delle prestazioni e ho trovato una conclusione piuttosto sorprendente.

Utilizzando

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

per la configurazione, ho cronometrato i seguenti frammenti:

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

Con mia grande sorpresa, set(A+B+C) è la più veloce nonostante il fatto che essa crea una lista intermedia contenente 3000000 elementi . .update e itertools.chain sono entrambi più lenti, anche se nessuno dei due copia alcuna lista.

Cosa sta succedendo qui?

---

EDIT: su una seconda macchina (OS X 10.10.5, Python 2.7.10, 2.5GHz Core i7), ho eseguito il seguente script (che esegue i test in avanti e indietro per evitare gli effetti di ordinazione):

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

e ottenuti i seguenti risultati:

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 

Ora set(A+B+C) è chiaramente più veloce, ed i risultati sono abbastanza Stabl e - è difficile calcolarlo fino al semplice errore di misura. L'esecuzione ripetuta di questo script produce risultati simili.

Answer 1

ottengo risultati diversi, non sorprendenti, di te sulla mia macchina Win 7 SP1 con un processore simile con Python 2.7.10, dove set(A+B+C) sembra essere il modo più lento di farlo come ci si potrebbe aspettare. Risultati simili sono stati ottenuti con la garbage collection riattivata e con Python 3.4.3.

ho usato il mio prestazioni banco di prova per valutare sulla base di timeit e ottenuto i seguenti risultati:

codice

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 

Benchmarking:

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