Từ điển Python so với danh sách, nhanh hơn?

Question

Tôi đã mã hóa một vấn đề Euler, và tôi chạy vào câu hỏi làm tôi tò mò. Tôi có hai đoạn mã. Một là với danh sách các từ điển sử dụng khác.

sử dụng danh sách:

n=100000 
num=[] 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num.append(tmp) 
      suma+=i 

sử dụng từ điển:

n=100000 
num={} 
suma=0 
for i in range(n,1,-1): 
    tmp=tuple(set([n for n in factors(i)])) 
    if len(tmp) != 2: continue 
    if tmp not in num: 
     num[tmp]=i 
     suma+=i 

Tôi chỉ quan tâm đến hiệu suất. Tại sao ví dụ thứ hai sử dụng từ điển chạy cực nhanh, nhanh hơn ví dụ đầu tiên với danh sách. ví dụ với từ điển chạy nhanh hơn gấp ba mươi lần!

Tôi đã thử nghiệm 2 mã này bằng cách sử dụng n = 1000000 và mã đầu tiên chạy trong 1032 giây và mã thứ hai chạy chỉ trong 3,3 giây ,,, amazin '!

Answer 1

Trong danh sách, mã if tmp not in num: là O (n) , trong khi đó là O (lgn) trong dict .

Chỉnh sửa: Nguyên tắc dựa trên băm, do đó, nó nhanh hơn tìm kiếm danh sách lót. Cảm ơn @ user2357112 cho điểm này.

Answer 2

Tôi gần như tích cực rằng "nước sốt ma thuật" sử dụng từ điển nằm trong thực tế là từ điển bao gồm các cặp khóa-giá trị.

trong danh sách, bạn đang xử lý các mảng, có nghĩa là vòng lặp for phải bắt đầu tại chỉ mục 0 bên trong danh sách của bạn để lặp qua từng bản ghi.

điển chỉ cần có để tìm ra Key-> cặp giá trị trong câu hỏi vào ngày đầu tiên 'go-round' và gửi lại, vì thế mà tốc độ ...

về cơ bản, thử nghiệm cho các thành viên trong một bộ chìa khóa -> cặp giá trị nhanh hơn rất nhiều so với tìm kiếm toàn bộ danh sách cho một giá trị. lớn hơn danh sách của bạn sẽ chậm hơn nó sẽ ... nhưng điều này không phải luôn luôn như vậy, có những tình huống mà một danh sách sẽ nhanh hơn ... nhưng tôi tin rằng đây có thể là câu trả lời bạn đang tìm kiếm

Answer 3

Trong Python, độ phức tạp thời gian trung bình của tra cứu khóa từ điển là O (1), vì chúng được triển khai dưới dạng bảng băm. Độ phức tạp thời gian tra cứu trong danh sách là trung bình O (n). Trong mã của bạn, điều này tạo ra sự khác biệt trong dòng if tmp not in num:, vì trong trường hợp danh sách, Python cần phải tìm kiếm trong toàn bộ danh sách để phát hiện thành viên, trong khi trong trường hợp dict nó không ngoại trừ trường hợp xấu nhất tuyệt đối.

Để biết thêm chi tiết, hãy xem TimeComplexity.

Answer 4

Nếu đó là về tốc độ, bạn không nên tạo ra bất kỳ danh sách:

n = 100000 
factors = ((frozenset(factors(i)), i) for i in range(2, n+1)) 
num = {k:v for k,v in factors if len(k)==2} 
suma = sum(num.values())