Tại sao tạo một tập hợp từ danh sách được nối nhanh hơn sử dụng `.update`?

Question

Trong khi cố gắng trả lời What is the preferred way to compose a set from multiple lists in Python, tôi đã thực hiện một số phân tích hiệu suất và đưa ra một kết luận hơi ngạc nhiên.

Sử dụng

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

cho các thiết lập, tôi timed các đoạn sau:

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

Trước sự ngạc nhiên của tôi, set(A+B+C) là nhanh nhất mặc dù thực tế là nó tạo ra một danh sách trung gian chứa 3000000 yếu tố . .update và itertools.chain đều chậm hơn, mặc dù cả hai đều không sao chép bất kỳ danh sách nào.

Điều gì đang xảy ra ở đây?

---

EDIT: Trên một máy thứ hai (OS X 10.10.5, Python 2.7.10, 2.5GHz Core i7), tôi chạy đoạn mã sau (chạy các bài kiểm tra tới lui để tránh đặt hiệu ứng):

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

và thu được kết quả như sau:

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 

Bây giờ set(A+B+C) là rõ nhanh hơn, và kết quả là khá stabl e - khó có thể vạch ra điều này lên chỉ là lỗi đo lường. Chạy tập lệnh này nhiều lần sẽ tạo ra các kết quả tương tự.

Answer 1

Tôi nhận được kết quả khác nhau, không đáng ngạc nhiên so với bạn trên hộp Win 7 SP1 với bộ xử lý tương tự với Python 2.7.10, trong đó set(A+B+C) dường như là cách chậm nhất. Kết quả tương tự thu được với bộ sưu tập rác được kích hoạt lại và với Python 3.4.3.

tôi đã sử dụng hiệu suất của việc đánh giá thử nghiệm của tôi dựa trên timeit và nhận được kết quả như sau:

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 

Điểm chuẩn mã:

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