On 28.03.2013 16:39, bartekltg wrote:
> W dniu 2013-03-28 11:04, Michoo pisze:
>> 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
>
> Wiem wiem;)
>
> BTW, czy taki printf w pętli za każdym razem parsuje ten
> swój napis typu "%d"?

W znanych mi implementacjach tak - jest automat zjadający wejście i
wypluwający wyjście (pobierając/zapisując kolejne rekordy ze stosu)
(hmmm, ciekawe, czy printf jest turing complete ;) ).

>
>> No chyba, ze extreme: jak po linuxem to można użyć czystego read albo
>> jeszcze lepiej mmap
>
> W przykładzie który widziałem (właśnie z takich konkursików)
> gość użył fgets + bufor + własne przerabianie na liczby.

Na potyczkach używałem kiedyś atoi - jest dostatecznie szybkie. fgets ma
jedną dodatkową wartwę po drodze do read.


> Tak akurat było to na zasadzie kto zrobi + limit czasu na tyle długi,
> aby czytać to odpaloną javą bit po bicie;) ale jakby to był
> wyścig 'kto szybciej', pewnie było by warto.

Kiedyś w pociągu zrobiłem jako "bonus" do sprawozdania o algorytmach
sortujących implementację heapsorta w asm byłem w sumie pozytywnie
zaskoczony wynikiem. (A wyszły w tym takie kwiatki jak np to, procesor
chyba trzymał szczyt stosu w rejestrach - operacje na [esp], [esp+4]...
były równie szybkie jak na eax,ebx...)

>
> U nas tablica mieszająca i tak pewnie zasłoniłaby swoim czasem
> działania szczegóły wczytywania.

Dla takich problemów dobra funkcja mieszająca to taka, która działa
możliwie liniowo. Zrobiłbym wektor wskaźników na funkcję do wykrywania
końca linii i lookup do robienia to_lower - w takiej konfiguracji
czytanie bajt-po-bajcie kontra czytanie blokami da duuużą różnicę.

>
>> Trzeba zrobić szybkie lower/upper (pewnie lookup table, nieduże w sumie).
>
> O zapomnialem o tym. Tablica na 256 elementów to nie problem,

O ile wejście jest 8-bit/znak - wtedy użyłbym w sumie jumptable.

> a dzieki temu za darmo mamy utożsamienie wszystkich białych
> znaków, interpunkcji etc.

256*4/8bajty na wskaźnik całkiem nieźle rezyduje w cache. O ile tylko
jumptable nie zepsuje za bardzo pipeline to powinna wymiatać.

Tak w ogóle teraz mnie deadline ścigają ale za jakieś 2 tygodnie to może
skrobnę programik - będzie można zrobić konkurs ;)

>
>>
>> Hash podejrzewam, że sprawdzi się w postaci:
>>
>> uint_least32_t hash=0;
>> uint_fast16_t len=0;
>
> Ech, piękne te typy;)

Hm? Właśnie do takich zastosowań one w końcu są.

>
>> for(char c:str){
>> hash^=c;
>> hash<<=1;
>> len++;
>> }
>> hash=(hash<<4)^len;
>
> Widzę, jak działa, ale dlaczego sądzisz, że będzie dobry?

Taki strzał - kiedyś używałem w bardzo podobnym zadanku sumy znaków i
dodanie długość bardzo poprawiło wynik - to jest lekka rozbudowa tej
koncepcji.


--
Pozdrawiam
Michoo