Cách nhanh nhất để tìm kiếm python dict bằng một từ khóa

Question

Cách nhanh nhất để xác định xem một dict có chứa khóa bắt đầu bằng một chuỗi cụ thể không? Chúng ta có thể làm tốt hơn tuyến tính không? Làm thế nào chúng ta có thể đạt được một hoạt động O (1) khi chúng ta chỉ biết bắt đầu một chìa khóa?

Đây là giải pháp hiện tại:

for key in dict.keys(): 
    if key.start_with(str): 
     return True 
return False 

Answer 1

Nếu không có tiền xử lý dict, O(n) là tốt nhất bạn có thể làm. Nó không phải là phức tạp, mặc dù:

any(key.startswith(mystr) for key in mydict) 

(. Không sử dụng dict và str như tên biến, những người đã là tên của hai built-in functions)

Nếu bạn thể preprocess các dict, xem xét việc đặt các phím trong một cây tiền tố (aka trie). Thậm chí còn có Python implementation trong bài viết trên Wikipedia.

Answer 2

Bạn có thể đặt tất cả các tiền tố của các khóa được chèn vào dict, vì vậy đối với khóa foo bạn sẽ chèn f, fo và foo. Bạn sẽ có O (1) tra cứu, nhưng bạn sẽ dành nhiều thời gian trên tiền xử lý (O (k), với k là chiều dài key), và lãng phí rất nhiều bộ nhớ:

def insert_with_prefixes(key, value, dict_): 
    prefixes = (key[:i+1] for i in xrange(len(key))) 
    dict_.update((prefix, value) for prefix in prefixes) 

Đối với sử dụng hàng ngày tôi sẽ đi (và tôi đi) với phương pháp trong câu trả lời arshajii's. Và tất nhiên, có trong tâm trí có thể nhiều va chạm với tiền tố ngắn (đây: "h"):

>>> a = {} 
>>> insert_with_prefixes('hello', 'world', a) 
>>> insert_with_prefixes('homo', 'sapiens', a) 
>>> a 
{'h': 'sapiens', 'hom': 'sapiens', 'homo': 'sapiens', 'ho': 'sapiens', 
'hel': 'world', 'hell': 'world', 'hello': 'world', 'he': 'world'}