przyladajac net natknalem sie na takie zadanie
podobno zadane gdzies studentom na jakims roku

dla danego pliku tekstowego z jakas ksiazką (np
robinson crusoe) napisac program ktory wyszuka i
wypisze na ekran 10 najczesciej wystepujacych
tam słow

wygrywa jeden program tj ten ktory to zrobi
najszybciej

jak by nalezalo napisac taki program ?

do góry

W dniu środa, 27 marca 2013 19:18:28 UTC+1 użytkownik firr kenobi napisał:
> jak by nalezalo napisac taki program ?
Chyba zahaszować pary (słowo,częstość).
Pozdrawiam

do góry

Dnia 27.03.2013 firr kenobi <p...@g...com> napisał/a:
> przyladajac net natknalem sie na takie zadanie
> podobno zadane gdzies studentom na jakims roku
>
> dla danego pliku tekstowego z jakas ksiazką (np
> robinson crusoe) napisac program ktory wyszuka i
> wypisze na ekran 10 najczesciej wystepujacych
> tam słow
>
> wygrywa jeden program tj ten ktory to zrobi
> najszybciej
>
> jak by nalezalo napisac taki program ?

https://github.com/kragen/shootout/tree/master/bench
/wordfreq

do góry

W dniu 2013-03-27 19:24, M.M. pisze:
> W dniu środa, 27 marca 2013 19:18:28 UTC+1 użytkownik firr kenobi napisał:
>> jak by nalezalo napisac taki program ?
> Chyba zahaszować pary (słowo,częstość).

Ogolnie jakakolwiek mapa i powinno pójść w miarę sprawnie.

Hashowana pewnie będzie sprawniejsza. Unorderet_set
ma co najmniej iterator z inkrementacją, więc
i ze znalezieniem na koniec maksimum problemu nie będzie.

Można by się ewentualnie zastanowić nad czymś w rodzaju
drzew trie czy patricia, ale skoro nie
musimy się przejmować pamięcią, nic nie zyskujemy,
a wydajność leci.

No to stl, szybki hash i sprawny odczyt (pewnie trzebaby
wyhakować sobie własny, bo strumienie wolne;)


Statystyka dla chętnych.

Książka ma ok 65k słów.

http://www.granice.pl/kultura,zgadnijcie--ile-slow-l
iczy-przecietna-ksiazka,4550

A liczba różnych słów to parę tysiecy.

http://www.antimoon.com/forum/t14464.htm

Alice's Adventures in Wonderland: 2766
Pride and Prejudice: 6424
A Tale of Two Cities: 9877
Oliver Twist: 10419
A Connecticut Yankee in King Arthur's Court: 10312

Po polsku dzięki odmianie pewnie będzie więcej słów
rozumianych jako różne ciągi znaków.

pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 01:51:58 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-27 19:24, M.M. pisze:
>
> > W dniu środa, 27 marca 2013 19:18:28 UTC+1 użytkownik firr kenobi napisał:
>
> >> jak by nalezalo napisac taki program ?
>
> > Chyba zahaszować pary (słowo,częstość).
>
>
>
> Ogolnie jakakolwiek mapa i powinno pójść w miarę sprawnie.
>
>
>
> Hashowana pewnie będzie sprawniejsza. Unorderet_set
>
> ma co najmniej iterator z inkrementacją, więc
>
> i ze znalezieniem na koniec maksimum problemu nie będzie.
>
>
>
> Można by się ewentualnie zastanowić nad czymś w rodzaju
>
> drzew trie czy patricia, ale skoro nie
>
> musimy się przejmować pamięcią, nic nie zyskujemy,
>
> a wydajność leci.
>
>
>
> No to stl, szybki hash i sprawny odczyt (pewnie trzebaby
>
> wyhakować sobie własny, bo strumienie wolne;)
>
>
>
>
>
> Statystyka dla chętnych.
>
>
>
> Książka ma ok 65k słów.
>
>
>
> http://www.granice.pl/kultura,zgadnijcie--ile-slow-l
iczy-przecietna-ksiazka,4550
>
>
>
> A liczba różnych słów to parę tysiecy.
>
>
>
> http://www.antimoon.com/forum/t14464.htm
>
>
>
> Alice's Adventures in Wonderland: 2766
>
> Pride and Prejudice: 6424
>
> A Tale of Two Cities: 9877
>
> Oliver Twist: 10419
>
> A Connecticut Yankee in King Arthur's Court: 10312
>
>
>
> Po polsku dzięki odmianie pewnie będzie więcej słów
>
> rozumianych jako różne ciągi znaków.
>

a czym sie rozni hashowana od niehashowanej w sensie sprawnosci ? (nigdy nie uzywalem
tego
hashowania i jakos nawet specjalnie nie
przepadam za tym pojeciem poki co nigdy
nie bylo mi potrzebne) I jak realizowane
jest wstawianie/wyszukiwanie czy dany element
juz jest wstawiony? Trzyma sie posortowane
drzewo? Tak wogole to nie jestem zbytnio
przekonany czy bylaby to najszybsza metoda. ;)

do góry

Dnia Thu, 28 Mar 2013 00:55:21 -0700 (PDT), firr kenobi napisał(a):

> a czym sie rozni hashowana od niehashowanej w sensie sprawnosci ? (nigdy nie
uzywalem tego
> hashowania i jakos nawet specjalnie nie
> przepadam za tym pojeciem poki co nigdy
> nie bylo mi potrzebne) I jak realizowane
> jest wstawianie/wyszukiwanie czy dany element
> juz jest wstawiony? Trzyma sie posortowane
> drzewo? Tak wogole to nie jestem zbytnio
> przekonany czy bylaby to najszybsza metoda. ;)

Googla serwery padly??

--
pozdro
R.e.m.e.K

do góry

On 28.03.2013 01:51, bartekltg wrote:
> W dniu 2013-03-27 19:24, M.M. pisze:
>> W dniu środa, 27 marca 2013 19:18:28 UTC+1 użytkownik firr kenobi
>> napisał:
>>> jak by nalezalo napisac taki program ?
>> Chyba zahaszować pary (słowo,częstość).
>
> Ogolnie jakakolwiek mapa i powinno pójść w miarę sprawnie.
>
> Hashowana pewnie będzie sprawniejsza. Unorderet_set
> ma co najmniej iterator z inkrementacją, więc
> i ze znalezieniem na koniec maksimum problemu nie będzie.
>
> Można by się ewentualnie zastanowić nad czymś w rodzaju
> drzew trie czy patricia, ale skoro nie
> musimy się przejmować pamięcią, nic nie zyskujemy,
> a wydajność leci.
>
> No to stl, szybki hash i sprawny odczyt (pewnie trzebaby
> wyhakować sobie własny, bo strumienie wolne;)

I ty brutusie?

sync_with_stdio?? iostream jest od pewnego czasu już równie szybkie co stdio
No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
jeszcze lepiej mmap

Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w sumie).

Hash podejrzewam, że sprawdzi się w postaci:

uint_least32_t hash=0;
uint_fast16_t len=0;
for(char c:str){
hash^=c;
hash<<=1;
len++;
}
hash=(hash<<4)^len;


I szczerze mówiąc to jakby to był jakiś konkurs na zwolnienie z egzaminu
to pewnie bym w ASM wstawki rzeźbił.


--
Pozdrawiam
Michoo

do góry

W dniu czwartek, 28 marca 2013 08:55:21 UTC+1 użytkownik firr kenobi napisał:
> a czym sie rozni hashowana od niehashowanej w sensie
> sprawnosci ? (nigdy nie uzywalem tego
W ogole czy w tym zadaniu? :D

W ogole jeśli uzywamy drzewek, to mozna jeszcze (dodatkowa funkcjonalnosc
wzgledem hash-table) szybko (bez wywolywania funkcji sort) wyswietlic
posortowane dane. Mozna takze czesciej uzywane elementy przeniesc
w gore drzewka - dodatkowa optymalizacja. Mozna latwo wzbogacic standardowe
drzewa i mozna szybko wyswietlic N-ty element w kolejnosci sortowania.

W hash-table (z zalozenia - w praktyce to nie zawsze jest takie proste i
oczywiste) mozemy szybciej dodac element i sprawdzic czy wczesniej byl
dodany - nie ma zadnego sortowania. Hash-table jest prostsza w
implementacji - przynajmniej jak na moje oko :)

Hash-table ma problem gdy chcemy dodac wiecej elementow niz na poczatku
zalozylismy. Z drzewami jest problem gdy zrobi sie z nich lista - specyficzne
dane, trzeba uzyc wersji wywazaniem, a to dodatkowy narzut.

Wiecej w tej chwili nie pamietam :)

Pozdrawiam

do góry

W dniu czwartek, 28 marca 2013 11:04:28 UTC+1 użytkownik Michoo napisał:
> I szczerze mówiąc to jakby to był jakiś konkurs na zwolnienie z egzaminu
> to pewnie bym w ASM wstawki rzeźbił.
Bys musial wiedziec na jakim kompie programy beda porownywane.
Pozdrawiam

do góry

W dniu czwartek, 28 marca 2013 11:25:11 UTC+1 użytkownik M.M. napisał:
> W dniu czwartek, 28 marca 2013 08:55:21 UTC+1 użytkownik firr kenobi napisał:
>
> > a czym sie rozni hashowana od niehashowanej w sensie
>
> > sprawnosci ? (nigdy nie uzywalem tego
>
> W ogole czy w tym zadaniu? :D
>
>
>
> W ogole jeśli uzywamy drzewek, to mozna jeszcze (dodatkowa funkcjonalnosc
>
> wzgledem hash-table) szybko (bez wywolywania funkcji sort) wyswietlic
>
> posortowane dane. Mozna takze czesciej uzywane elementy przeniesc
>
> w gore drzewka - dodatkowa optymalizacja. Mozna latwo wzbogacic standardowe
>
> drzewa i mozna szybko wyswietlic N-ty element w kolejnosci sortowania.
>
>
>
> W hash-table (z zalozenia - w praktyce to nie zawsze jest takie proste i
>
> oczywiste) mozemy szybciej dodac element i sprawdzic czy wczesniej byl
>
> dodany - nie ma zadnego sortowania. Hash-table jest prostsza w
>
> implementacji - przynajmniej jak na moje oko :)
>
>
>
> Hash-table ma problem gdy chcemy dodac wiecej elementow niz na poczatku
>
> zalozylismy. Z drzewami jest problem gdy zrobi sie z nich lista - specyficzne
>
> dane, trzeba uzyc wersji wywazaniem, a to dodatkowy narzut.
>
>
>
> Wiecej w tej chwili nie pamietam :)
>
>

nigdy nie uzywalem hashowania ani nawet
o tym nie czytalem ;o (nigdy nie bylo
mi potrzebne)

prosta kwestia: o ile wstawiac te wyrazy do drzewa
to jego 'posortowanie'/upozadkowanie jest
potrzebne bo przeciez chodzi o to by szybko znalezc czy nie ma w nim juz tego
elementu ,i
jak jest to zrobic ++ na tym wyrazie

moje pytanie jest czy wstawianie do tego
drzewa (?) hashy jest szybsze i dlaczego
(zwlaszcza ze jak mi sie wydaje chyba pozniej
trzeba znalezc operacje odwrotna, tj z 10ciu najczeciej wystepujacych hashy znalezc
10
wyrazow) ? (no i rozwiazac ten problem ze taki sam hash moze dac wiecej wyrazow)

sama ta idea 'sciumpienia' dluzszych stringow
do nieduzych liczb jest fajna ale nie wiem
za bardzo jak robi sie pozniej robotę odwrotną
kiedy kilkanascie roznych encji zhaszuje sie
do jednej liczby - to przeciez chyba byloby
raczej wolne

do góry