Python: jak sprawdzić, czy na secie jest słowo zaczynające się od, np. 'ab'?

Question

Jak w temacie: czy da się szybko (logarytmicznie) jakaś prostą metodą/operacją sprawdzić, czy na secie znajduje się słowo zaczynające się od jakiegos innego?

Wymyśliłem, żeby trzymac słowa na liscie i napisac binsearcha, ale zastanawiam się, czy moze nie ma czegos wbudowanego...

Przykład:
S = set(['abc','cbd', 'abba'])
dla 'ab' funkcja powinna zwracac True
dla 'cd' funkcja powinna zwracać False

Answer 1

W hashsecie nie da się inaczej niż O(n). Musisz przeiterować po wszystkich elementach.

Natomiast są struktury dedykowane do takiego szybkiego szukania, np. drzewo trie (prefiksowe) https://pypi.python.org/pypi/marisa-trie

from marisa_trie import Trie
trie = Trie(['abc', 'cbd', 'abba'])

trie.has_keys_with_prefix('ab') # True
trie.has_keys_with_prefix('cd') # False

Ze złożonością O(1) na wielkość kontenera.

BTW na przyszłość:

s = set(['abc','cbd', 'abba'])
s = {'abc','cbd', 'abba'} # ladniejsze

 

Comments

Uuuuu ! Dzięki bardzo :) Trie jest wbudowane? O matko, ale cudnie... dopiero ucze się pythona w LO pisałem w C++, wiec ciesze się jak odkrywam co on ma jeszcze w sobie XD

A co do tego seta, to {} nie oznacza mapy?

{'Kasia': 13131412, 'Gosia': 12431412, 'Zosia': 4124141}

Co on robi wtedy, gdy nie poda mu się klucza, czy jak się tam nazywa ten drugi element?

---

 Trie jest wbudowane?

Nie jest, trzeba doinstalować pipem (jak widać w linku wyżej)

A co do tego seta, to {} nie oznacza mapy?

{1: 2, 3: 4} # dict
{1, 2, 3, 4} # set

 

---

Faktycznie trzeba doinstalowac... za bardzo sie ucieszylem, ale i tak fajnie :P

A co do seta i dict, to tak samo to działa w pythonie 2 i 3?

---

A co do seta i dict, to tak samo to działa w pythonie 2 i 3?

Tak.

---

A jeszcze takie pytanie: jak zrobić, żeby ten moduł działał w pythonie3? Bo po zainstalowaniu działa tylko jak w terminalu odpalam program pythonem2, a dla trójki mówi: No module named 'marisa_trie'

---

Zamiast pip użyj pip3.

(a na dłuższą metę lepiej działać w virtualenvach)

---

Dzięki wielkie, jeszcze raz ! Wszytsko już śmiga :)