W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg napisał:

> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
> pewnie tylko raz jeszcze musisz policzy.
Nie wiem jaki jest najsprytniejszy algorytm realokacji hash-table.
Naiwny wygląda mniej/więcej tak:
1) Przydziel większą tablicę
2) Dla każdego elementu z tablicy mniejszej:
a) policz funkcję hash
b) wrzuć do większej
3) Zwolnij pamięć list
4) Zwolni mniejszą tablicę

W tym zadaniu faktycznie można dać tablicę 1.5 * ilosc_znaków i się
nie martwić. Ale w ogólnym przypadku (chyba) trochę czasu schodzi
na realokację.
Pozdrawiam

do góry

W dniu czwartek, 28 marca 2013 17:33:04 UTC+1 użytkownik firr napisał:
> robiona na zwyklej tablicy to jej rozmiar jest dosyc bolasty i jest
> odpowiedni wielkosci hasza
> np hasz 20 bitów - tablica 1 MB ???
Jeśli ilość entry-points w hash-table jest 2^N, to można zrobić
mikro-optymalizację:
hash_table[ makeKey( data ) & ((1<<N)-1) ] = data;
Jeśli rozmiar jest inny, to nie ma problemu, można tak:
hash_table[ makeKey( data ) % inny_roziar ] = data;



> 2) drugi problem - jak z danym haszem jest
> kojarzona lista sów, powiedzmy ze krzesło i hipopotam daja jednego hasza
> 777889 to chyba musza siedziec tam obok w postaci listy ?
W tym zadaniu nie są potrzebne w ogóle żadne listy.

key = makeKey( "hipopotam" );
entry = key % hash_size;
C = 1;
while( ! isEmpty( hash_table[entry] ) )
entry = (entry+C) % hash_size;
hash_table[ entry ] = "hipopotam";


Można C obliczać drugą funkcją hash:

key = makeKey( "hipopotam" );
entry = key % hash_size;
C = makeKey2( "hipopotam" );
while( ! isEmpty( hash_table[entry] ) )
entry = (entry+C) % hash_size;
hash_table[ entry ] = "hipopotam";



Pozdrawiam

do góry

W dniu 2013-03-28 19:20, M.M. pisze:
> W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg napisał:
>
>> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
>> pewnie tylko raz jeszcze musisz policzy.
> Nie wiem jaki jest najsprytniejszy algorytm realokacji hash-table.
> Naiwny wygląda mniej/więcej tak:
> 1) Przydziel większą tablicę
> 2) Dla każdego elementu z tablicy mniejszej:
> a) policz funkcję hash
> b) wrzuć do większej
> 3) Zwolnij pamięć list
> 4) Zwolni mniejszą tablicę
>
> W tym zadaniu faktycznie można dać tablicę 1.5 * ilosc_znaków i się
> nie martwić. Ale w ogólnym przypadku (chyba) trochę czasu schodzi
> na realokację.


Tak jak w każdym tego typu kontenerze. Poszacuj sobie czas
zamortyzowany. Dla czysto rosnącej tablicy i powiększania x2
wychodzi 3 razy więcej niż wklejenie elementu (dodając element
przydzielasz mu dodatkowe dwa kredyty na jego realokowanie w przyszlosci
i realokowanie elementu z pierwszej połowy tablicy).

Mała cena jak za możliwość nieprzejmowania się rozmiarem;)

pzdr
bartekltg

do góry

W dniu 2013-03-28 19:57, bartekltg pisze:
> W dniu 2013-03-28 19:20, M.M. pisze:
>> W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg
>> napisał:
>>
>>> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
>>> pewnie tylko raz jeszcze musisz policzy.
>> Nie wiem jaki jest najsprytniejszy algorytm realokacji hash-table.
>> Naiwny wygląda mniej/więcej tak:
>> 1) Przydziel większą tablicę
>> 2) Dla każdego elementu z tablicy mniejszej:
>> a) policz funkcję hash
>> b) wrzuć do większej
>> 3) Zwolnij pamięć list
>> 4) Zwolni mniejszą tablicę
>>
>> W tym zadaniu faktycznie można dać tablicę 1.5 * ilosc_znaków i się
>> nie martwić. Ale w ogólnym przypadku (chyba) trochę czasu schodzi
>> na realokację.
>
>
> Tak jak w każdym tego typu kontenerze. Poszacuj sobie czas
> zamortyzowany. Dla czysto rosnącej tablicy i powiększania x2
> wychodzi 3 razy więcej niż wklejenie elementu (dodając element
> przydzielasz mu dodatkowe dwa kredyty na jego realokowanie w przyszlosci
> i realokowanie elementu z pierwszej połowy tablicy).
>
> Mała cena jak za możliwość nieprzejmowania się rozmiarem;)

OK, może za mętnie powiedziałem, trochę rozjaśnię.

Niech naszym bazowym kosztem będzie policzenie hasha,
wstawienie do tablicy i 1/n czasu zalkokowania tej tablicy
(czy tam tablicy list...) dlugosci n.

Koszt zamortyzowany pojedyńczego wstawiania jest
mniejszy niż 3*koszt podstawowy (będzie gdzieś pomiedzy x2 i x3).

Z grubsza tak samo jak w wektorze.

pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 20:14:35 UTC+1 użytkownik bartekltg napisał:
> OK, może za mętnie powiedziałem, trochę rozjaśnię.
Nie rozumiem tylko co to są te kredyty :)
Pozdrawiam

do góry

W dniu 2013-03-28 17:33, firr pisze:


>> [dużo literek]

TNIJ CYTATY.


> no dobra ale konkretniej - powiedzmy ze ciekaw
> jestem wlasnie jak robiloby sie to przy
> pomocy tej tablicy haszujacej

Więc poczytaj;)


> 1) o ile rozumiem jak ta tablica haszujaca jest
> robiona na zwyklej tablicy to jej rozmiar jest dosyc bolasty i jest odpowiedni
wielkosci hasza

Nie musi być tak wielki. Ale wystąpią kolizje (i tak mogą
wystąpić nawet dla znacznie za dużej).

Rozwiązuje się to różnie, np poprzez trzymanie tablicy list.

> np hasz 20 bitów - tablica 1 MB ???

'Skraca' się hasha. NP ten stlowy powiększa się domyślnie dopiero,
gdy 'load factor', czyli liczba elementów/liczba kubełków("długość
tablicy") jest równa jeden.
http://www.cplusplus.com/reference/unordered_map/uno
rdered_map/load_factor/

Co ważne, można go dowolnie modyfikować i uzyskać lepszą sprawność
kosztem wiekszego zuzycia pamięci.

BTW niedawno był tu wątek o tworzeniu unikalnych hashy
za pomocą pośredniej tablicy. Też warto zerknąć.


> 2) drugi problem - jak z danym haszem jest
> kojarzona lista sów, powiedzmy ze krzesło i hipopotam daja jednego hasza 777889 to
chyba musza
> siedziec tam obok w postaci listy ?

Nie rozumiem pytania.
Proponuję jednak najpierw przeczytać artykuł na wiki,
bo przepisywanie podstaw jest męcace, a jak zmeczysz
grypowiczów, nie będą odpowiadać na nietrywialne pytania.

pzdr
bartekltg

do góry

W dniu 2013-03-28 20:18, M.M. pisze:
> W dniu czwartek, 28 marca 2013 20:14:35 UTC+1 użytkownik bartekltg napisał:
>> OK, może za mętnie powiedziałem, trochę rozjaśnię.
> Nie rozumiem tylko co to są te kredyty :)


Jedna z najprostszych metod analizy kosztu zamortyzowanego.
Taka ładna, bo się na obrazkach i monetach pokazuje;)
Rozdział 18 w Cormenie.

http://pl.wikipedia.org/wiki/Koszt_zamortyzowany

http://en.wikipedia.org/wiki/Accounting_method

Do pojedynczych operacji przypisujesz "koszt" na zapas, aby,
gdy przyjdzie pora i wykonamy jakieś wielkie sprzątanie,
koszt tego sprzątania był już 'opłacony'.

Podobna, nieco bardziej wyrafinowana jest metoda potencjału.
Tam pieniążki trzyma jeden skarbnik, nie elementy.


pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 20:31:27 UTC+1 użytkownik bartekltg napisał:
> Jedna z najprostszych metod analizy kosztu zamortyzowanego.
Ah.. ja to już wziąłem za jakiś sprytny sposób zarządzania
elementami żeby było mniej pracy przy realokacji :)

do góry

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

do góry

On 28.03.2013 16:42, bartekltg wrote:
> W dniu 2013-03-28 11:27, M.M. pisze:
>> 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
>
> Ostatnio olimpiada informatyczna i potyczki algorytmiczne
> lecą na czymś w rodzaju wirtualnego procesora x86.
>
> http://ripper.dasie.mimuw.edu.pl/~accek/homepage/wp-
content/papercite-data/pdf/acemgr09.pdf

Strona 28 - liczenie "prędkości wykonywania instrukcji" za pomocą NOPów,
które nie wychodzą poza dekoder rozkazów jest poronionym pomysłem. W
ogóle dlatego się używa benchmarki ze złożonymi operacjami (np.
dhrystone) bo procesory mają pipeline i np.
add,add,shr może się wykonać w zauważalnie innym czasie niż add,shr,add.

"Pewnym zaskoczeniem jest prawie dwukrotnie większa szybkość zapisu na
komputerze Xeon w porównaniu z Core 2 Duo mimo, że oba komputery
posiadają pamięć DDR2 666 MHz" - ech, a gdzie ilość kości pamięci? A
gdzie timingi pamięci? Autor słyszał o czymś takim jak dual channel?

Jak na mimuw to się zawiodłem...


Przy wypełnianiu tablicy - to jest zdaje się[*] kwestia nie tyle cache
co działania linuxa - strony inicjalizowane 0 są przydzielane jako CoW,
więc pierwszy zapis do tablicy w losowy sporób robi (robił?) masakrę w mmu.

[*] było to kilka lat temu, ale prosty memset przed zaczęciem obliczeń
przyspieszył program coś pod 20 razy.

--
Pozdrawiam
Michoo

do góry