Słownik python

0

Hej. Mam słownik, gdzie kluczem jest słowo, a wartość to suma poszczególnych liter słowa (każda litera ma przypisaną swoją wartość). Chcę aby użytkownik podał zestaw liter, na podstawie których znajdywane jest słowo i jeśli ma największą wartość to jest wypisywane. Nie wiem tylko jak mam przeszukiwać ten słownik po literach, a konkretniej jak przeszukać te klucze po literach.

0

Za mało dokładnie tłumaczysz: co konkretnie masz na myśli, pisząc że „słowo jest znajdowane na podstawie zestawu liter”? Chodzi Ci o anagramy?

Jeśli tak, i nie popsuje Ci to logiki programu (bo, na przykład, wartość słowa zależy od kolejności liter w nim), to niech kluczem będzie posortowany ciąg znaków i szukaj tak samo, posortowanym ciągiem znaków.

A tak swoją drogą, to nie rozumiem na podstawie Twojego opisu, po co w ogóle Ci słownik.

0

Czyli chcesz sprawdzić, czy wszystkie wprowadzone przez użytkownika litery, w dowolnej kolejności znajdują się w łańcuchu znaków?

0

Mam słownik { "kot" : 4, "kto" : 3 }. Użytkownik podaje zestaw liter okt, szuka mi wyrazu z tych liter i zwraca jeden z największą wartością.

0
  1. napisz funkcję, która sprawdza, czy wszystkie literki są w kluczu.
  2. Iteruj sobie po kluczach i je sprawdzaj funkcją z 1).
  3. jeśli klucz spełnia warunek, to przystępujesz do sprawdzania maksa.
  4. jeśli nie było wcześniej maksa albo był mniejszy to przypisujesz do niego obecny klucz.
  5. po przeleceniu wszystkich kluczy w pętli masz wynik.
0

To moim pierwszym pomysłem (niekoniecznie najlepszym — jest już późno…) jest zmiana struktury danych: teraz masz Dict[str, int], a ja bym sugerował Dict[[str], Dict[str, int]] — najpierw masz klucz będący posortowanym ciągiem liter, który Cię prowadzi do słownika z wariantami punktacji za konkretne słowa.

Czyli tak: masz słownik {['k', 'o', 't']: {"kot" : 4, "kto" : 3}}, a wyszukanie robisz tak, że sortujesz litery dostarczone przez użytkownika i patrzysz po tym.

Dalej, jeśli nie potrzebujesz niczego oprócz najwyżej punktowanego słowa, to możesz to w ogóle olać i po prostu na etapie tworzenia słownika zrobić go tak, że będzie on tylko Dict[[str], (str, int], tzn. słownik z uporządkowanego ciągu liter do pary (słowo, wynik) dla najlepszego słowa.

I wreszcie, Python ma co prawda bardzo niewygodną implementację kopca, ale to też Ci się może przydać, jeśli jednak potrzebujesz na 100% tych kilku wariantów punktowych.

1

Jeśli podane przez kolegów wyżej rozwiązania nie będą wystarczająco szybkie...
Zakładając że używasz pythona3.6 lub wyżej, biorąc pod uwagę wyszukiwanie indeksów i możliwości sortowania liter w ciągu znaków. No i przede wszystkim zakładając że kolejność liter nie ma znaczenia w punktacji.

Zbuduj sobie słownik na takiej podstawie:
Dict('posortowany_ciag_znakow': najwyzsza_wartosc_int)

Zakładając że budujesz go na podstawie jakiegoś zestawu 'slowo' i funkcja_punktujaca('slowo'):

slownik = {''.join(x for x in sorted(slowo): funkcja_punktujaca(slowo) for slowo in zestaw_danych}

Następnie, dzięki prędkości dostępu do słowników w pythonie, możesz bardzo szybko się do tego odwołać:

twoj_input = (...)
szukane = ''.join(x for x in sorted(twoj_input))
wynik = slownik.get(szukane, None)
if wynik == None: #~ if not wynik:
    (costam)
print(wynik)

I dzięki takiemu zabiegowi unikniesz duplikatów.

Ale podejrzewam że zamiast budować/wczytywać odpowiedni słownik, najlepiej by było po prostu wywołać taką funkcję_punktującą, chyba że to nie człowiek ma do niej wysyłać dane, tylko maszyna w dużym tempie. Bo przy czynniku ludzkim który jest wolny, faktycznie lepiej wyliczyć z tego słowa 'do szybkiego dostępu'.

1

Tak to wygląda, najprościej, imo:

def solution(d, word):
	max = 0
	s = ""
	for key in d:
		if is_anagram(key, word):
			if d[key] >= max:
				max = d[key]
				s = key
	return s

def is_anagram(st1, st2):
	return sorted(st1) == sorted(st2)

Nie wiem, jak JIT w Pythonie optymalizuje, ale dla słownika złożonego z dziesięciu milionów słów, od trzy do dziesięcioliterowych, szukanego wyrazu dziesięcioliterowego, program liczył 18.87 sec. Wychodzi, że złożoność, dla tej sytuacji wynosi, tak jak pisaliśmy, mniej więcej O(25 * n).

0
lion137 napisał(a):

Tak to wygląda, najprościej, imo:

def solution(d, word):
	max = 0
	s = ""
	for key in d:
		if is_anagram(key, word):
			if d[key] >= max:
				max = d[key]
				s = key
	return s

def is_anagram(st1, st2):
	return sorted(st1) == sorted(st2)

Nie wiem, jak JIT w Pythonie optymalizuje, ale dla słownika złożonego z dziesięciu milionów słów, od trzy do dziesięcioliterowych, szukanego wyrazu dziesięcioliterowego, program liczył 18.87 sec. Wychodzi, że złożoność, dla tej sytuacji wynosi, tak jak pisaliśmy, mniej więcej O(25 * n).

o jakim JIT w CPythonie mówisz?

1 użytkowników online, w tym zalogowanych: 0, gości: 1