Słownik python

Odpowiedz Nowy wątek
2018-12-04 00:26
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.

Pozostało 580 znaków

2018-12-04 00:40
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.

Pozostało 580 znaków

2018-12-04 00:44
0

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

Pozostało 580 znaków

2018-12-04 00:48
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ą.

edytowany 1x, ostatnio: jacek129, 2018-12-04 00:49

Pozostało 580 znaków

2018-12-04 00:56
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.

Pokaż pozostałe 5 komentarzy
Dla porównania, posortowanie liter w słowie i wyszukanie w słowniku po tym to coś rzędu O(c * s * log(s)), gdzie c to koszt wyszukania dla danej kombinacji liter, równy czasowi znalezienia w słowniku odpowiedniej listy (czyli niezbyt duża stała, powiedzmy rzędu ~stu operacji) razy czasowi znalezienia maksimum w podliście (która będzie krótka, bo nawet długie słowa mają niezbyt dużo anagramów, powiedzmy że tutaj pesymistycznie będzie koło ~dziesięciu operacji). - Althorion 2018-12-04 09:00
Co nam daje łącznie około (100 * 10) * 10 * log(10), czyli ~kilkadziesiąt tysięcy operacji, czyli jakieś sto tysięcy razy lepiej — a to jest przejście od milisekund do minut, więc jak najbardziej zauważalne. - Althorion 2018-12-04 09:03
Aż tak strasznie będzie? Bo, chyba, że to źle rozumiem, mi wychodzi (c - długośc słowa): 3 * c + parę operacji sprawdzenia maksimum i to wszystko razy n (długość słownika). 3 * c - to sprawdzenie czy anagramy, przy założeniu, że dla tak krótkich ciągów Python optymalizuje sortowanie do liniowego. - lion137 2018-12-04 10:57
Nie wykluczam, że źle zrozumiałem zamysł w 1), 2), ale tak jak ja to pojmuję, to autorowi chodziło o puszczenie wyszukania dla każdej permutacji liter (których jest właśnie s!). W sumie, jak teraz patrzę (już po dwóch kawach), to chyba właśnie tak było — tzn. ja się myliłem, a Ty masz rację, i chodziło o to, że w 1) jest funkcja, która sprawdza dla każdej litery w s, czy jest w k-literowym słowie z n-elementowego słownika. - Althorion 2018-12-04 11:04
A to oznacza, że 1) ma złożoność O(s * k), co nam da O(s * k * n), czyli mniej-więcej 10 * 5 * 5000, (~dziesięcioliterowe sprawdzane słowo, ~pięcioliterowe średnie słowo w słowniku, ~pięć tysięcy słów w słowniku), czyli ~kilkaset tysięcy operacji, zatem faktycznie nie ma źle. - Althorion 2018-12-04 11:07

Pozostało 580 znaków

2018-12-04 00:57
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.

edytowany 1x, ostatnio: Althorion, 2018-12-04 00:58

Pozostało 580 znaków

2018-12-04 03:17
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'.


Linux Mint
Arduino / Python 3.5.2
edytowany 2x, ostatnio: Guaz, 2018-12-04 03:42

Pozostało 580 znaków

2018-12-04 11:53
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).


Pozostało 580 znaków

2018-12-05 16:20
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?

Ja chyba nie jestem znów na czasie, a o jakimś Cpythonie tu była mowa :D? - Guaz 2018-12-05 16:52
Jeśli mówi się, że coś działa jakoś w Pythonie, to albo ma się na myśli specyfikację, albo wiodącą referencyjną implementację, t.j. CPython. - enedil 2018-12-05 16:56

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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