Python: lặp qua danh sách so với hiệu quả các mục dict

Question

Đang lặp lại trên some_dict.items() hiệu quả khi lặp qua danh sách các mục giống nhau trong CPython?

Answer 1

Tùy thuộc vào phiên bản Python bạn đang sử dụng. Trong Python 2, some_dict.items() tạo danh sách mới, danh sách này mất thêm thời gian và sử dụng hết bộ nhớ bổ sung. Mặt khác, một khi danh sách được tạo ra, đó là một danh sách, và vì vậy cần có các đặc tính hiệu năng giống nhau sau khi hoàn thành việc tạo danh sách.

Trong Python 3, some_dict.items() tạo đối tượng xem thay vì danh sách và tôi dự đoán rằng việc tạo và lặp qua items() sẽ nhanh hơn trong Python 2, vì không có gì phải được sao chép. Nhưng tôi cũng dự đoán rằng việc lặp qua chế độ xem đã tạo sẽ chậm hơn một chút so với danh sách đã tạo, vì dữ liệu từ điển được lưu trữ hơi thưa thớt và tôi tin rằng không có cách nào tốt để python tránh lặp lại bin trong từ điển - ngay cả từ trống.

Trong Python 2, một số timings xác nhận trực giác của tôi:

>>> some_dict = dict(zip(xrange(1000), reversed(xrange(1000)))) 
>>> some_list = zip(xrange(1000), xrange(1000)) 
>>> %timeit for t in some_list: t 
10000 loops, best of 3: 25.6 us per loop 
>>> %timeit for t in some_dict.items(): t 
10000 loops, best of 3: 57.3 us per loop 

iterating trên items là khoảng gấp đôi chậm. Sử dụng iteritems được một chút chút nhanh hơn ...

>>> %timeit for t in some_dict.iteritems(): t 
10000 loops, best of 3: 41.3 us per loop 

Nhưng lặp qua danh sách chính nó là cơ bản giống như iterating trên bất kỳ danh sách khác:

>>> some_dict_list = some_dict.items() 
>>> %timeit for t in some_dict_list: t 
10000 loops, best of 3: 26.1 us per loop 

Python 3 có thể tạo ra và duyệt qua items nhanh hơn so với Python 2 có thể (so sánh với 57.3 chúng tôi ở trên):

>>> some_dict = dict(zip(range(1000), reversed(range(1000)))) 
>>> %timeit for t in some_dict.items(): t  
10000 loops, best of 3: 33.4 us per loop 

Nhưng thời gian tạo chế độ xem là không thể bỏ qua; nó thực sự chậm hơn để lặp qua hơn một danh sách.

>>> some_list = list(zip(range(1000), reversed(range(1000)))) 
>>> some_dict_view = some_dict.items() 
>>> %timeit for t in some_list: t 
10000 loops, best of 3: 18.6 us per loop 
>>> %timeit for t in some_dict_view: t 
10000 loops, best of 3: 33.3 us per loop 

Điều này có nghĩa rằng trong Python 3, nếu bạn muốn lặp nhiều lần so với các mục trong một cuốn từ điển, và hiệu suất là rất quan trọng, bạn có thể có được một tốc độ tăng 30% bằng cách cache xem như một danh sách.

>>> some_list = list(some_dict_view) 
>>> %timeit for t in some_list: t 
100000 loops, best of 3: 18.6 us per loop 

Answer 2

Một điểm chuẩn nhỏ cho thấy rằng việc lặp lại danh sách chắc chắn nhanh hơn.

def iterlist(list_): 
    i = 0 
    for _ in list_: 
     i += 1 
    return i 

def iterdict(dict_): 
    i = 0 
    for _ in dict_.iteritems(): 
     i += 1 
    return i 

def noiterdict(dict_): 
    i = 0 
    for _ in dict_.items(): 
     i += 1 
    return i 

list_ = range(1000000) 
dict_ = dict(zip(range(1000000), range(1000000))) 

Thử nghiệm với IPython trên Python 2,7 (Kubuntu):

%timeit iterlist(list_) 
10 loops, best of 3: 28.5 ms per loop 

%timeit iterdict(dict_) 
10 loops, best of 3: 39.7 ms per loop 

%timeit noiterdict(dict_) 
10 loops, best of 3: 86.1 ms per loop 

Answer 3

Mặc dù iterating qua some_list là tăng tốc 2x hơn some_dict.items(), nhưng lặp lại qua some_list bởi chỉ số này gần như là giống như lặp lại qua some_dict bằng phím .

K = 1000000 
some_dict = dict(zip(xrange(K), reversed(xrange(K)))) 
some_list = zip(xrange(K), xrange(K)) 
%timeit for t in some_list: t 
10 loops, best of 3: 55.7 ms per loop 
%timeit for i in xrange(len(some_list)):some_list[i] 
10 loops, best of 3: 94 ms per loop 
%timeit for key in some_dict: some_dict[key] 
10 loops, best of 3: 115 ms per loop 
%timeit for i,t in enumerate(some_list): t 
10 loops, best of 3: 103 ms per loop