Độ phức tạp về thời gian truy cập vào Python dict

Question

Tôi đang viết một chương trình Python đơn giản.

Chương trình của tôi dường như bị truy cập tuyến tính vào từ điển, thời gian chạy của nó tăng theo cấp số nhân mặc dù thuật toán là bậc hai.
Tôi sử dụng từ điển để ghi nhớ các giá trị. Đó có vẻ là một nút cổ chai.

Các giá trị mà tôi đang băm nhỏ là số điểm. Mỗi điểm là: (x, y), 0 < = x, y < = 50
Từng phím trong từ điển là: Một bộ 2-5 điểm: ((x1, y1), (x2, y2), (x3, y3), (x4, y4))

Các phím được đọc nhiều lần thường xuyên hơn số lần viết.

Tôi có chính xác rằng các con trăn python bị thời gian truy cập tuyến tính với các đầu vào như vậy không?

Theo như tôi biết, các bộ có thời gian truy cập lôgarit được đảm bảo.
Làm thế nào tôi có thể mô phỏng dicts bằng cách sử dụng bộ (hoặc một cái gì đó tương tự) trong Python?

chỉnh sửa Theo yêu cầu, đây là một (giản thể) phiên bản của hàm memoization:

def memoize(fun): 
    memoized = {} 
    def memo(*args): 
     key = args 
     if not key in memoized: 
      memoized[key] = fun(*args) 
     return memoized[key] 
    return memo 

Answer 1

Xem Time Complexity. Các dict python là một hashmap, trường hợp xấu nhất của nó là do đó O (n) nếu hàm băm là xấu và kết quả trong rất nhiều va chạm. Tuy nhiên, đó là một trường hợp rất hiếm khi mọi mục được thêm có cùng một băm và do đó được thêm vào cùng một chuỗi mà đối với một triển khai Python chính sẽ là cực kỳ không. Thời gian trung bình phức tạp là tất nhiên O (1).

Phương pháp tốt nhất là kiểm tra và xem xét các băm của đối tượng bạn đang sử dụng. CPython Dict sử dụng int PyObject_Hash (PyObject *o) tương đương với hash(o).

Sau một kiểm tra nhanh chóng, tôi vẫn chưa được quản lý để tìm thấy hai bộ dữ liệu mà băm để cùng giá trị, mà sẽ chỉ ra rằng việc tra cứu là O (1)

l = [] 
for x in range(0, 50): 
    for y in range(0, 50): 
     if hash((x,y)) in l: 
      print "Fail: ", (x,y) 
     l.append(hash((x,y))) 
print "Test Finished" 

CodePad (Sẵn sàng cho 24 giờ)

Answer 2

Bạn đang không đúng. Truy cập dict có thể không phải là vấn đề của bạn ở đây. Đó là gần như chắc chắn O (1), trừ khi bạn có một số đầu vào rất lạ hoặc một hàm băm rất xấu. Dán một số mã mẫu từ ứng dụng của bạn để chẩn đoán tốt hơn.

Answer 3

Sẽ dễ dàng hơn khi đưa ra đề xuất nếu bạn cung cấp mã ví dụ và dữ liệu.

Truy cập từ điển không có vấn đề gì khi hoạt động đó là O(1) on average, and O(N) amortized worst case. Có thể các hàm băm được tích hợp sẵn đang gặp phải sự va chạm cho dữ liệu của bạn. Nếu bạn gặp sự cố với chức năng băm có sẵn, bạn có thể tự cung cấp.

Python thực hiện từ điển làm giảm mức độ phức tạp trung bình của tra cứu từ điển để O (1) bằng cách đòi hỏi những dữ liệu quan trọng cung cấp một "băm" chức năng .Hàm băm như vậy lấy thông tin trong đối tượng khóa và sử dụng nó để tạo số nguyên, được gọi là giá trị băm. Giá trị băm này sau đó được sử dụng để xác định "nhóm" cặp (khóa, giá trị) này cần được đặt vào.

Bạn có thể ghi đè lên các phương pháp __hash__ trong lớp học của bạn để thực hiện một chức năng tùy chỉnh băm như thế này:

def __hash__(self):  
    return hash(str(self)) 

Tùy thuộc vào những gì dữ liệu của bạn thực sự trông như thế nào, bạn có thể có thể đưa ra một nhanh hơn hàm băm có ít va chạm hơn hàm chuẩn. Tuy nhiên, điều này là không thể. Xem Python Wiki page on Dictionary Keys để biết thêm thông tin.

Answer 4

Như những người khác đã chỉ ra, việc truy cập dicts bằng Python rất nhanh. Chúng có lẽ là cấu trúc dữ liệu được bôi trơn tốt nhất trong ngôn ngữ, với vai trò trung tâm của chúng. Vấn đề nằm ở nơi khác.

Bạn ghi nhớ bao nhiêu bộ nhớ? Bạn đã xem bộ nhớ của bộ nhớ chưa? Có lẽ bạn đang dành tất cả thời gian của bạn trong bộ nhớ cấp phát hoặc bộ nhớ phân trang.

Answer 5

Chương trình của tôi dường như bị truy cập tuyến tính vào từ điển, thời gian chạy của nó tăng theo cấp số nhân mặc dù thuật toán là bậc hai.

Tôi sử dụng từ điển để ghi nhớ các giá trị. Đó có vẻ là một nút cổ chai.

Đây là bằng chứng về lỗi trong phương pháp ghi nhớ của bạn.

Answer 6

Để trả lời câu hỏi cụ thể của bạn:

Q1: "" "Tôi thích hợp mà dicts python bị lần truy cập tuyến tính với đầu vào như vậy?" ""

A1: Nếu bạn có nghĩa là thời gian tra cứu trung bình là O (N) trong đó N là số lượng mục nhập trong dict, sau đó rất có khả năng là bạn sai. Nếu bạn là chính xác, cộng đồng Python sẽ rất muốn biết trong hoàn cảnh nào bạn đúng, để vấn đề có thể được giảm thiểu hoặc ít nhất được cảnh báo. Mã "mẫu" cũng như mã "đơn giản hóa" không hữu ích. Vui lòng hiển thị mã và dữ liệu thực tế tái tạo sự cố. Mã phải được thiết kế với những thứ như số lượng mục dict và số lượng truy cập dict cho mỗi P trong đó P là số điểm trong khóa (2 < = P < = 5)

Q2: "" " Làm thế nào tôi có thể mô phỏng dicts bằng cách sử dụng bộ (hoặc một cái gì đó tương tự) trong Python? "" "

A2: Bộ có thời gian truy cập logarit được bảo đảm trong bối cảnh nào? Không có bảo đảm như vậy cho việc triển khai Python. Các phiên bản CPython gần đây trong thực tế sử dụng một thực thi dict cắt giảm (chỉ khóa, không có giá trị), vì vậy kỳ vọng là hành vi O (1) trung bình. Làm thế nào bạn có thể mô phỏng dicts với bộ hoặc một cái gì đó tương tự trong bất kỳ ngôn ngữ? Câu trả lời ngắn: với cực kỳ khó khăn, nếu bạn muốn có bất kỳ chức năng nào ngoài dict.has_key(key).