Birleştirilmiş bir listeden bir grup neden `.update` kullanmadan daha hızlı oluşturuluyor?

Question

What is the preferred way to compose a set from multiple lists in Python'u yanıtlamaya çalışırken, bazı performans analizleri yaptım ve biraz şaşırtıcı bir sonuçla karşılaştım.

kurulum için

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

kullanarak, aşağıdaki parçacıkları zaman aşımına: Benim için sürpriz

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

, set(A+B+C) o 3000000 unsurları içeren bir ara liste oluşturur olmasına rağmen en hızlı olduğunu . .update ve itertools.chain öğelerinin ikisi de daha yavaştır;

Neler oluyor burda?

---

DÜZENLEME: İkinci makinede (OS X 10.10.5, Python 2.7.10, 2,5 GHz Core i7), I (etkileri sipariş önlemek için ileri ve geri testleri çalıştırır) Aşağıdaki senaryoyu koştum:

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

ve elde aşağıdaki sonuçlar:

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 

Şimdi set(A+B+C) açıkça hızlı ve sonuçlar oldukça stabl olan e - bu, sadece ölçüm hatasına kadar yazmak zor. Bu betiği çalıştırmak tekrar tekrar benzer sonuçlar üretir.

Answer 1

Ben set(A+B+C) bir tahmin edebileceğiniz gibi bunu yapmak için yavaş yol olarak görünmektedir Python 2.7.10, benzer bir işlemci ile benim Win 7 SP1 kutuyu senden olmayan şaşırtıcı, farklı sonuçlar elde ederler. Benzer sonuçlar, çöp toplama yeniden etkinleştirildi ve Python 3.4.3 ile elde edildi.

Ben timeit dayalı kendi performans değerlendirme test yatağı kullanılan ve aşağıdaki sonuçları aldık:

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 

Kıyaslama kodu:

birinci durumda a geçer

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