Tuples Python làm khóa chậm?

Question

Tôi đang cố triển khai tra cứu nhanh các bộ dữ liệu được sắp xếp trong từ điển; một cái gì đó mà trả lời câu hỏi "Liệu tuple (3,8) có một giá trị liên quan, và nếu có, nó là gì?". Để các số nguyên trong các bộ dữ liệu bị ràng buộc từ bên dưới bằng 0 và từ trên xuống bằng max_int.

Tôi đã tiếp tục và sử dụng dict của Python nhưng thấy rằng khá chậm. Một cách tiếp cận khác cho vấn đề này là tạo một danh sách T với các dấu gạch ngang max_int (hầu hết là rỗng), và cho mỗi tuple (3,8) đặt T [3] [8] = giá trị. Tôi cho rằng đây chính xác là phương pháp băm-thùng mà Python sử dụng với dicts, nhưng sau này nhanh hơn khoảng 30 lần (!) Tại đây.

Ngoài ra, mặc dù, nó xấu xí (đặc biệt là kể từ khi tôi bây giờ về để thực hiện 3-tuples), vì vậy tôi rất nhiều đánh giá cao một số gợi ý ở đây.

Để tham khảo, đây là đoạn code tôi sử dụng để có được timings:

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

print d 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    (3,8) in d.keys() 
elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

print t 

# do some lookups 
m = 10000 
start_time = time.time() 
for k in xrange(m): 
    8 in t[3].keys() 
elapsed = time.time() - start_time 
print elapsed 

Answer 1

Dưới đây là kết quả thời gian chính xác với Python 2.7:

>>> %timeit (3, 8) in d.keys() # Slow, indeed 
100000 loops, best of 3: 9.58 us per loop 

>>> %timeit 8 in t[3].keys() # Faster 
1000000 loops, best of 3: 246 ns per loop 

>>> %timeit (3, 8) in d # Even faster! 
10000000 loops, best of 3: 117 ns per loop 

>>> %timeit 8 in t[3] # Slightly slower 
10000000 loops, best of 3: 127 ns per loop 

Họ thấy rằng các tiêu chuẩn (3, 8) in d (không xây dựng danh sách .keys()) thực sự là một chút nhanh hơn (ít nói chung) 8 in t[3] cách tiếp cận, và gấp đôi nhanh là tương đối nhanh 8 in t[3].keys() của câu hỏi. Sự khác biệt này .keys/không .keys xuất phát từ thực tế là (3, 8) in d.keys() tạo danh sách (trong Python 2) của các khóa và sau đó tìm kiếm (3, 8) trong danh sách này, chậm hơn nhiều so với tìm kiếm (3, 8) trong bảng băm từ điển d.

Như đã đề cập trong các ý kiến, kết quả thời gian là khác nhau với Python 3: Python 3 của keys() đã một nhanh in thử nghiệm vì keys() lợi nhuận thay vì một cái nhìn vào các phím, vì vậy mà các nhà điều hành in thể sử dụng bảng băm của tương ứng từ điển.

Sự khác biệt về tốc độ trong câu hỏi ban đầu xuất phát từ thực tế là d.keys() tạo danh sách tương đối dài, so với t[3].keys().

PS: chức năng %timeit được cung cấp bởi vỏ xuất sắc IPython. Chương trình gốc có thể được thực hiện thông qua IPython với %run prog.py.

Answer 2

Bạn đang thử nghiệm cho các giá trị khác nhau. Trong phiên bản từ điển, có tra cứu 100.000 khóa, trong khi trong cấu trúc danh sách nhóm, tra cứu chỉ dành cho 10.000 khóa.

Ngoài ra, đoạn mã này làm chậm mọi thứ xuống: (3,8) in d.keys() nếu bạn vừa viết (3,8) in d, thì thời gian tra cứu trong cả hai phiên bản sẽ tương tự nhau và sự khác biệt không đáng kể. Hãy thử kiểm tra sửa đổi này và xem cho chính mình:

import numpy as np 
import time 

# create a bunch of sorted tuples 
num_tuples = 10 
max_int = 100 
a = np.random.rand(num_tuples,2) * max_int 
a = a.astype(int) 
for k in xrange(len(a)): 
    a[k] = np.sort(a[k]) 

# create dictionary with tuples as keys 
d = {} 
for t in a: 
    d[tuple(t)] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if (3,8) in d: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

# now create the bucket-list structure mentioned above 
t = [{} for k in xrange(max_int)] 
for k in xrange(len(a)): 
    t[a[k][0]][a[k][1]] = 42 

# do some lookups 
m = 100000 
start_time = time.time() 
for k in xrange(m): 
    if 8 in t[3]: 
     pass 

elapsed = time.time() - start_time 
print elapsed 

Lý do cho hành vi quan sát được là cả hai (3,8) in d.keys() và 8 in t[3].keys() đang tạo ra một danh sách tạm thời mới của phím mọi thời gian, nhưng phiên bản thứ hai tạo ra danh sách ngắn hơn. Nếu bạn chỉ đơn giản sử dụng thành ngữ key in dictionary, danh sách tạm thời không còn được tạo và hiệu suất bắt đầu trông giống nhau cho cả hai cách tiếp cận.

Tôi muốn sử dụng phiên bản đầu tiên, đơn giản hơn nhiều, dễ đọc và dễ hiểu và thành ngữ hơn - và khi được sử dụng đúng cách, thực hiện cũng như phiên bản thứ hai.

Answer 3

Hơi lạ khi so sánh tốc độ (a, b) in d đến b in t[a] vì sau này giả định rằng a phải có mặt.

Trong mọi trường hợp, cách đầu tiên phải luôn nhanh hơn. Cả hai phiên bản đều có cả a và b. Việc đầu tiên có thêm chi phí phân bổ một tuple và băm nó. Tuy nhiên, cách thứ hai thực hiện hai tra cứu từ điển riêng biệt.