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"?

> 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.

Miało to sens (zmieniało czas) gdy cały algorytm sprowadzał się do
odczytania n cyfr i ich posumowania (do czego dochodziło się
po dłuższej matematyce:)
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.

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


W normalnym użyciu tez bym się tym zupełnie nie przejmował
i uzywał ulubionego z iostream/sdtio.

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

O zapomnialem o tym. Tablica na 256 elementów to nie problem,
a dzieki temu za darmo mamy utożsamienie wszystkich białych
znaków, interpunkcji etc.

>
> Hash podejrzewam, że sprawdzi się w postaci:
>
> uint_least32_t hash=0;
> uint_fast16_t len=0;

Ech, piękne te typy;)

> 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?
Nie mam zupełnie doświadczenia w konstruowaniu hashów.


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

:-)

Pzdr
bartekltg