Forum Coders' city Strona Główna Coders' city
Nasza pasja to programowanie!
 

 PomocPomoc   SzukajSzukaj   UżytkownicyUżytkownicy   GrupyGrupy  RejestracjaRejestracja 
Archiwum starego forum + teoria    RSS & Panel/SideBar
 ProfilProfil   Zaloguj się, by sprawdzić wiadomościZaloguj się, by sprawdzić wiadomości   ZalogujZaloguj 

Potrzebuję szybkiej odpowiedzi na moje pytanie... Zasady

Bisect i polskie litery

Idź do strony Poprzedni  1, 2, 3, 4  Następny

 
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Python
Zobacz poprzedni temat :: Zobacz następny temat  
Autor Wiadomość
mazur
Gość





PostWysłany: Pon Paź 17, 2016 10:46 pm  OP    Temat postu: Odpowiedz z cytatem Pisownia

Bardzo dziękuję za tę podpowiedź - to faktycznie o wiele lepsze rozwiązanie.

Pozdrowienia
Robert
Powrót do góry
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Pon Paź 17, 2016 11:15 pm      Temat postu: Odpowiedz z cytatem Pisownia

Poprawiłem twoją metodę, nie zauważając, że jest nieprawidłowa. "Zagapiłem się" ze względu na wcześniejszy opis problemu z pełnym indeksem. Natomiast przy częściowym nic z tego nie zadziała. Popatrz na taki przypadek:
Cytat:
centrosomie
czarnowodzkich
Jaryczewskie
nieczternastokilometrowa
niedżemowych
niegalijskiej
niekawałkową
nienekrologowych
niepogórnicza
nieramkowych
niesfiksowanej
niesypiącego
niezarównywanymi
odpieczętowujże
retrieverom
rozpaćkałyby
zafałszowani
Wyszkując w tym "nieogarnięty" wylądujemy na "nieczternastokilometrowa" zamiast "nienekrologowych".

Zatem trzeba będzie przeglądać linia po linii, szukając pierwszego wpisu wyższego od szukanego i cofając się o 1 po jego znalezieniu.

_________________
Nieaktywny od 2017-04-01
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
mazur
Gość





PostWysłany: Wto Paź 18, 2016 10:10 am  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

Faktycznie, w środku nocy nie za dobrze się myśli.

W głowie mam następujący algorytm.
1. Przeszukiwać zgodnie z Twoim wcześniejszym wpisem, tj. (np. "nieogarnięty")
- pierwszą literę ("n"),
- następnie od miejsca znalezienia pierwszej litery szukać "ni"
- jw. "nie"
- jw. "nieo"
- ponieważ "nieo" nie znaleziono
- wyszukuję wszystkie wyrazy zaczynające się na "nie", tj. otrzymuję:
Cytat:
nieczternastokilometrowa
niedżemowych
niegalijskiej
niekawałkową
nienekrologowych
niepogórnicza
nieramkowych
niesfiksowanej
niesypiącego
niezarównywanymi


wybieram ostatnią literę, której nie udało się znaleźć, tu: 4-te litery z tego zbioru, tj. otrzymuję:
d, g, k, n, p, r, s, s, z


teraz muszę znaleźć w którym miejscu ma znajdować się litera "o" (4-ta z poszukiwanego słowa "nieogarnięty")

I tu znowu problem, gdyż mogą być tu znaki polskie.

Pomyślałem, by konwertować litery na cyfry:

Cytat:
a - 1
ą - 2
b - 3
c - 4
ć - 5
d - 6
e - 7
ę - 8
f - 9
g - 10
h - 11
i - 12
j - 13
k - 14
l - 15
ł - 16
m - 17
n - 18
ń - 19
o - 20
ó - 21
p - 22
r - 23
s - 24
ś - 25
t - 26
u - 27
w - 28
y - 29
z - 30
ź - 31
ż - 32


stąd mam listę liter zamienionych na liczby:
6, 10, 14, 22, 23, 24, 24, 30
w której muszę znaleźć położenie "o" (Nr = 20):

Kod:
aSlo=["nieczternastokilometrowa", "niedżemowych", "niegalijskiej", "niekawałkową", \
      "nienekrologowych", "niepogórnicza", "nieramkowych", "niesfiksowanej", \
      "niesypiącego", "niezarównywanymi"]

aLit=[]
for i in aSlo:
        aLit.append(i[3])
#aLit=["c", "d", "g", "k", "n", "p", "r", "s", "s", "z"]

aPl=["a", "ą", "b", "c", "ć", "d", "e", "ę", "f", "g", "h", "i", "j", \
     "k", "l", "ł", "m", "n", "ń", "o", "ó", "p", "r", "s", "ś", "t", \
     "u", "w", "y", "z", "ź", "ż"]

aNr=[]
for Lit in aLit:
        for i in range(len(aPl)):
                if aPl[i] == Lit:
                        aNr.append(i + 1)
                        break
#aNr = [4, 6, 10, 14, 22, 23, 24, 24, 30]

Zn = "o"
for i in range(len(aPl)):
        if aPl[i] == Zn:
                Nr = i + 1
                break
#Nr = 20

for i in range(len(aNr)):
        if aNr[i] > Nr:
                xNr = i
                print xNr
                break
# lub:
print bisect.bisect_left(aNr, Nr)


Pozdrowienia
Robert

Dodane przez moderatora (łączenie postów)

choć nie wiem, czy znowu coś z polskimi znakami się nie popsuje.
Pzdr
Robert
Powrót do góry
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Wto Paź 18, 2016 12:14 pm      Temat postu: Odpowiedz z cytatem Pisownia

jak szukasz metod przyspieszających to może pomóc segregacja (fachowo to się nazywa chyba hashowaniem), znacznie przyspiesza wyszukiwanie... mniej więcej taki kod, gdzie a, to jest lista słów:
Kod:

V={}
for elem in a:
   e3=elem[:3]
   if e3 in V.keys():
       if not elem in V[e3]:      
           V[e3].append(elem)
   else:
       V[e3]=[elem]


Wtedy aby sprawdzić czy dane słowo występuje na wyjściowej liście słów sprawdzamy czy pierwsze trzy litery słowa występują w V jako klucz, jeżeli tak, to wyszukujemy po znacznie zawężonej liście, a jeżeli nie, to mamy końcową odpowiedź...

Hashowanie to bardzo ważne pojęcie... szczególnie przy przeszukiwaniu większej ilości danych wielokrotnie... Czasem ważniejsza od algorytmu jest sama struktura danych, co często jst pomijane, szczególnie na początku drogi programowania...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Wto Paź 18, 2016 1:55 pm      Temat postu: Odpowiedz z cytatem Pisownia

mazur:
Akurat mnie lepiej pracuje się w nocy - po prostu zacząłem poprawiać twoje rozwiązanie bez zastanowienia się, czy w ogóle działa :).

Ale, z tego co widzę, w Pythonie rzecz nie będzie prosta do wykonania. Odpytałem kilku znajomych, którzy z niego korzystają, i wygląda na to, że w gołym Pythonie zadanie jest w ogóle niewykonalne w sensowny sposób*. Zatem najpierw pytanie: czy musi być koniecznie Python? Jeśli tak, to sprawa ma się następująco: Python w ogóle nie ma niczego do pełnej obsługi lokalizacji**. Z tej sytuacji można wybrnąć na dwa sposoby: używając zewnętrznych bibliotek (w tym przypadku: PyICU) lub wymagając by pliki z listą były sortowane według kodów znaków.

Z mojej perspektywy PyICU będzie lepszym rozwiązaniem, ale teraz pytanie: czy poradzisz sobie z instalacją i skonfigurowaniem tego? Jeśli tak, to:
Kod:
#!/usr/bin/env python
import icu

def mapLemmaToPage(fileName, encoding, lemma):
    with open(fileName, 'rU', encoding=encoding) as src:
        line = src.readline().rstrip()
        collator = icu.Collator.createInstance(icu.Locale(line))
        matchingPage = 0
        for line in src:
            (page, firstLemma) = line.rstrip().split(' ')
            if collator.compare(lemma, firstLemma) >= 0:
                matchingPage = page
            else:
                return matchingPage
        return matchingPage
Plik ma formę tak jak wcześniej: w każdej linii jest najpierw numer strony, potem pierwsza lemma z tej strony, oddzielone spacją. Z jedną zmianą: pierwsza linia zawiera nazwę lokalizacji, w której jest plik. Przykładowo dla polskiego:
Cytat:
pl_PL
1 długoletni
2 lakierni
3 kursantach
4 nieskalibrowaniach
5 poprószaniach
6 eutropowi
7 Januszowską
8 Żalna
9 Siemianówka
10 zabroń
Przykład użycia:
Kod:
mapLemmaToPage(nazwaPliku, kodowaniePliku, 'kurs')
Powyższe zwróci 2, bo "kurs" powinno znaleźć się na stronie 2.

Jeśli nie chcesz używać ICU, to będziesz musiał pilnować, żeby plik był zawsze posortowany nie według normalnego dla danego języka klucza, ale według kodu znaku w Unicode. W takiej sytuacji:
Kod:
#!/usr/bin/env python

def mapLemmaToPage(fileName, encoding, lemma):
    with open(fileName, 'rU', encoding=encoding) as src:
        line = src.readline()
        matchingPage = 0
        for line in src:
            (page, firstLemma) = line.rstrip().split(' ')
            if lemma >= firstLemma:
                matchingPage = page
            else:
                return matchingPage
        return matchingPage
Do tego oczywiście trzeba dopisać program, który będzie sortował zawartość pliku, żeby nadawała się do użytku.

hurgadion:
Ale problem w tym, że nie mamy listy słów. Gdybyśmy mieli, to wystarczyłoby po prostu przeszukać plik.
____
* Pisanie wszystkiego od zera albo wymaganie dodatkowych udziwnień nie jest dla mnie "sensownym sposobem".
** Moduł locale pozwala tylko na dostosowanie programu do ustawień systemowych.
*** Czyli np. podczas zmiany systemowych ustawień języka, przenoszeniu na inne komputery itd.

_________________
Nieaktywny od 2017-04-01


Ostatnio zmieniony przez marcin_an dnia Wto Paź 18, 2016 2:34 pm, w całości zmieniany 1 raz
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Wto Paź 18, 2016 2:05 pm      Temat postu: Odpowiedz z cytatem Pisownia

hmmm... listę słów można chyba utworzyć z pliku, a najlepiej to chyba od razu słownik... :)
_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Wto Paź 18, 2016 2:19 pm      Temat postu: Odpowiedz z cytatem Pisownia

Ale w pliku nie ma pełnej listy słów. Tam są tylko pierwsze lemmy z każdej strony. Gdyby był komplet, to cały kod sprowadziłby się do read i wyszukania czego trzema metodą index.
_________________
Nieaktywny od 2017-04-01
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
hurgadion



Dołączył: 06 Kwi 2011
Posty: 853
Skąd: Web :)

PostWysłany: Wto Paź 18, 2016 3:04 pm      Temat postu: Odpowiedz z cytatem Pisownia

OK,
chyba zaczynam w końcu rozumieć... :) w takim razie trzeba Twoją funkcję mapLemmaToPage odpalić chyba w pętli (chyba, że wyszukujemy tylko jedno słowo), więc trzeba te wszystkie lemmy (dlaczego taka nazwa, to jest standard ?) posortować (co napisałeś zresztą) no i warto posortować też wyszukiwane słowa, aby za każdym razem nie przechodzić całego pliku z tymi lemmami...

_________________
miasto nauki praktycznej
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość Odwiedź stronę autora Numer GG
marcin_an



Dołączył: 26 Maj 2005
Posty: 18822

PostWysłany: Wto Paź 18, 2016 3:54 pm      Temat postu: Odpowiedz z cytatem Pisownia

Hurgadion:
Lemma, bo wyszukujemy lemmę. Gdybyśmy wyszukiwali psa, nazwałbym "pies" (lub "dog").

mapLemmaToPage dokonuje jednego wyszukiwania w pliku. Jeżeli wyszukiwań byłoby dużo w trakcie działania programu i czasy wyszukiwań byłyby zbyt duży, to oczywiście warto załadować to w drzewo. Podkreślam "jeżeli", bo bez spełnienia tych warunków nie ma to sensu:
  1. Rozmiar danych autora jest malutki - zaledwie 10000 rekordów. Pełne uruchomienie Pythona, załadowanie skryptu, jego interpretacja i wykonanie zajmuje dla takich danych... 70ms. Tu nie ma nawet czego optymalizować. Na pliku zawierającym 3.7 miliona wyrazów mam czasy rzędu 8 sekund - i to jest wartość, przy której o poprawkach warto pomyśleć.
  2. Wyszukiwań musi być dostatecznie dużo, by czas zużyty na ładowanie danych i budowanie struktury został zrównoważony przez zysk z jej użycia. Przy małej liczbie wyszukiwań ten warunek nie będzie spełniony. A podejrzewam, że ten kod będzie używany jako jednorazowo odpalany skrypt, a nie chodzący w tle serwer, więc wyszukiwanie zawsze będzie pojedyncze*.
Ale nawet jeśliby te dwa warunki zostały spełnione, to wiesz, co będzie właściwym rozwiązaniem? Postawienie bazy danych, którą skrypt będzie odpytywał.
____
* Co nie uniemożliwia jeszcze optymalizacji. Można np. zmienić format pliku na lepszy.

_________________
Nieaktywny od 2017-04-01
Powrót do góry
Zobacz profil autora Wyślij prywatną wiadomość
mazur
Gość





PostWysłany: Wto Paź 18, 2016 9:52 pm  OP(?)    Temat postu: Odpowiedz z cytatem Pisownia

Cytat:
Jeśli nie chcesz używać ICU...


Podejrzewam, że gdy inaczej posortuję plik z:
nr_strony słowo

To wszystko się "rozleci", gdyż w tym pliku nie tylko słowa są posortowane, ale i numery stron.

Co jest lepszego od pythona w tym przypadku?
Za;leży mi nie na pythonie ale na prostocie, tak, by także inni tłumacze mogli skorzystać z szybszego znajdowania wyrazów w słownikach w formacie pdf czy djvu.

Pozdrowienia
Robert
Powrót do góry
Wyświetl posty z ostatnich:   
Odpowiedz do tematu    Forum Coders' city Strona Główna -> Python Wszystkie czasy w strefie CET (Europa)
Idź do strony Poprzedni  1, 2, 3, 4  Następny
Strona 2 z 4

 
Skocz do:  
Możesz pisać nowe tematy
Możesz odpowiadać w tematach
Nie możesz zmieniać swoich postów
Nie możesz usuwać swoich postów
Nie możesz głosować w ankietach
Możesz dodawać załączniki na tym forum
Możesz pobierać pliki z tego forum




Debug: strone wygenerowano w 0.12325 sekund, zapytan = 11
contact

| Darmowe programy i porady Jelcyna | Tansze zakupy w Helionie | MS Office Blog |