Tại sao chèn các phím vào thứ tự python dict nhanh hơn doint nó không có thứ tự

Question

Tôi đã tạo ra các dicts lớn (hàng triệu mục) và tôi đã nhận thấy rằng nếu tôi tạo chúng bằng các phím để nó nhanh hơn nhiều.

Tôi tưởng tượng rằng nó có liên quan đến va chạm với hàm băm, nhưng ai đó có thể giải thích tại sao nó xảy ra và nếu nó nhất quán giữa các phiên bản của python?

Ở đây bạn có một ví dụ nhân tạo:

import timeit 
import random 

def get_test_data(num, size): 
    olist, ulist = [], [] 
    for _ in range(num): 
     otest = [str(i) for i in range(size)] 
     utest = list(otest) 
     random.shuffle(utest) 
     olist.append(otest) 
     ulist.append(utest) 
    return olist, ulist 

NUM_TESTS = 20 
# Precalculate the test data so we only measure dict creation time 
ordered, unordered = get_test_data(NUM_TESTS, 1000000) 

def test_ordered(): 
    dict((k, k) for k in ordered.pop()) 

def test_unordered(): 
    dict((k, k) for k in unordered.pop()) 

print "unordered: ", 
print timeit.timeit("test_unordered()", 
        setup="from __main__ import test_unordered, test_ordered", 
        number=NUM_TESTS) 
print "ordered: ", 
print timeit.timeit("test_ordered()", 
        setup="from __main__ import test_unordered, test_ordered", 
        number=NUM_TESTS) 

Sản lượng trong máy của tôi luôn là:

(X)$ python /tmp/test.py 
unordered: 8.60760807991 
ordered: 5.1214389801 

Tôi đang sử dụng Python 2.7.3 trong Ubuntu x86_64 chính xác

Answer 1

tôi Gần như chắc chắn điều này là những gì đang xảy ra: khi bạn lần đầu tiên tạo ra otest, bạn đang lưu trữ các chuỗi trong bộ nhớ theo thứ tự. Khi bạn tạo utest, các chuỗi trỏ đến cùng một bộ đệm bộ nhớ, ngoại trừ bây giờ các vị trí đó là tất cả không đúng thứ tự. Điều này sẽ làm giảm hiệu suất bộ nhớ cache trên các trường hợp kiểm tra không có thứ tự.

Đây là bằng chứng. Tôi đã thay thế chức năng get_test_data của bạn với phiên bản này:

def get_test_data(num, size): 
    olist, ulist = [], [] 
    for _ in range(num): 
     nums = range(size) 
     random.shuffle(nums) 
     utest = [str(i) for i in nums] 
     otest = list(utest) 
     otest.sort(key=lambda x: int(x)) 
     olist.append(otest) 
     ulist.append(utest) 
    return olist, ulist 

Ý tưởng là bây giờ tôi đang xây dựng chuỗi trong ulist liên tiếp trong bộ nhớ, sau đó xây dựng olist bằng cách phân loại những chuỗi với phím thích hợp. Trên máy tính của tôi, điều này đảo ngược thời gian chạy của hai bài kiểm tra.

Answer 2

Kiểm tra source code of the python dict bạn có thể thấy các chuỗi hoặc int liên tiếp cho ít va chạm hơn. Điều này kết hợp với nhận xét @skishore về locallity cache tốt hơn có thể là câu trả lời.

Sự tinh tế chính phía trước: Hầu hết các lược đồ băm đều phụ thuộc vào hàm băm "tốt" , theo nghĩa mô phỏng tính ngẫu nhiên. Python không: hàm băm quan trọng nhất của nó (cho các chuỗi và ints) rất thường xuyên trong các trường hợp thông thường:

>>> map(hash, (0, 1, 2, 3)) 
[0, 1, 2, 3] 
>>> map(hash, ("namea", "nameb", "namec", "named")) 
[-1658398457, -1658398460, -1658398459, -1658398462] 
>>> 

này không nhất thiết phải là xấu! Ngược lại, trong một bảng có kích thước 2 ** i, lấy các bit i bậc thấp vì chỉ mục bảng ban đầu cực kỳ nhanh chóng và không có xung đột nào cho các dấu gạch ngang được lập chỉ mục bởi một phạm vi tiếp giáp của một số ints. Điều tương tự cũng đúng khi các phím là các chuỗi "liên tiếp" . Vì vậy, điều này mang lại hành vi tốt hơn so với ngẫu nhiên trong trường hợp phổ biến và điều đó rất mong muốn.