Jaki jest najszybszy sposób ustalenia, czy dict zawiera klucz rozpoczynający się od określonego ciągu? Czy możemy zrobić lepiej niż liniowo? Jak możemy uzyskać operację O (1), gdy znamy tylko początek klucza?najszybszy sposób wyszukiwania python dict z częściowym słowem kluczowym
Oto obecne rozwiązanie:
for key in dict.keys():
if key.start_with(str):
return True
return False
Bez przerób dict, O(n) jest najlepiej można zrobić. To nie musi być skomplikowane, choć:
any(key.startswith(mystr) for key in mydict)
(. Nie używaj dict i str jako nazw zmiennych, to są już nazwiska dwóch built-in functions)
Jeśli może przebiegu wyprzedzającego dyktować, rozważ umieszczenie kluczy w drzewie prefiksu (aka trie). W artykule z Wikipedii jest nawet Python implementation.
Trie to O (log N), a nie O (1). Ale prawie na pewno jest to, czego chcesz tutaj. Jest to w zasadzie przypadek paradygmatu dla struktury danych. – abarnert
@abarnert Nie, chyba że podejmiesz dziwne założenie, że największa długość ciągu jest logarytmiczna w liczbie łańcuchów. Wyszukiwanie w trie jest liniowe na długości klucza, a zatem niezależnie od liczby łańcuchów w trie. – delnan
@delnan: N nie jest liczbą łańcuchów, jest liczbą różnych symboli. Jeśli masz małą i statyczną liczbę symboli (np. Z ciągami ASCII), możesz to zignorować. Jeśli masz dużą liczbę symboli (np. Dowolny kod Unicode), nie możesz tego zrobić. Albo skończysz robić liniowe wyszukiwanie na każdym poziomie gry, albo dziennik N jeden raz. (Tak, to jest również liniowe w długości strun, a ja zaniedbałem to ...) – abarnert
Można umieścić wszystkie prefiksy wstawionej klucze do dict, więc dla klucza foo byś wstawić f, fo i foo. Trzeba byłoby O (1) odnośnika, ale można spędzić czas na przerób (O (K), gdzie K jest kluczem długości) i tracić dużo pamięci:
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)
do codziennego użytku pójdę (i idę) z metodą w odpowiedzi arshajii's. I oczywiście mieć na uwadze ewentualne kolizje dla wielu krótkich przedrostków (tu: "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'}
wątpię można acheive nic lepszego jak nie można wywnioskować hash klucza z części klucza. Również pozostawia to pole do niejednoznaczności, jeśli dwa klucze zaczynają się od tego samego prefiksu. – Hyperboreus
Istnieją struktury danych, które mogą to zrobić, ale nie są one dostępne w standardowej bibliotece Python. Przykładowo lub drzewa wyszukiwania binarnego. – delnan
Ponieważ pytanie dotyczy prędkości, czuję się zobowiązany zwrócić uwagę, że 'dla klucza w dyktafonie:' jest znacznie szybsze niż 'dla klucza w dict_.keys():', ponieważ ten drugi tworzy listę kluczy. –