W dniu czwartek, 28 marca 2013 11:53:31 UTC+1 użytkownik firr kenobi napisał:

> 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
Trzeba pracowac na parach
struct {
char *nazwa;
int czestosc;
}

Algorytm wstawiania do drzewka automatycznie sortuje po nazwie,
nie trzeba nic sortowac. Na koniec trzeba przejrzec wszystkie
wyrazy i 10 najczestszych zapamietac w kolejce priorytetowej.

Mozna tez od razu przechowywac i w kolejcie i w drzewie, wtedy
na koniec nie bedzie potrzeby przegladania wszystkiego - nie
wiem co szybsze.


> moje pytanie jest czy wstawianie do tego
> drzewa (?) hashy jest szybsze i dlaczego
Dokladna analiza szybkosci nie jest taka prosta. Do tego
celu trzeba znac sredni koszt kazdej operacji i prawdopodobienstwo
ze do danej operacji dojdzie. W drzewku mamy operacje:
a1) wyszukiwaie
b1) wstawianie
c1) rownowazenie


W hash-table tez mamy:
a2) wyszukiwanie
b2) wstawianie
c2) zwiekszanie rozmiaru hash-table.

P to funkcja prawdopodobienstwa, K to funkcja kosztu. Trzeba miec
dane do takich wzorow:

drzwko = P(a1)*K(a1) + P(b1)*K(b1) + P(c1)*K(c1)
hash-table = P(a2)*K(a2) + P(b2)*K(b2) + P(c2)*K(c2)

Dla kazdej implementacji te dane sa inne, dla kazdego rozmiaru
danych tez sa inne, bo dane inaczej sie cash-uja.



Pozdrawiam

do góry

no dobra w sumie zajrzalem troche do wiki
pod haslem tablica mieszajaca i moge mw
powiedziec o co mi chodzilow tym pytaniu

chodziło mi o to ze hash, ok, mozna zrobic na
wszystkich wyrazach ale sa dwa problemy

1) co zrobic jak dwie rozne encje daja ten
sam hasz
2) jak wrocic z wartosci hasza do encji

z tego co pisze na wiki wyglada mi na to
ze byc moze nie ma na to jakichs specjalnych
rozwiazan tj chyba po prostu obok hasza
zapisuje sie liste oryginalnych encji czy tez
wskaznikow - o tyle nie jest to chyba jakies
cudowne rozwiazanie choc do pogrupowania moze
być (no chyba ze o czyms nie wiem ale jakos
nie az tak bardzo mnie te hashe obchodza)

do góry

W dniu czwartek, 28 marca 2013 12:59:33 UTC+1 użytkownik firr kenobi napisał:
> 1) co zrobic jak dwie rozne encje daja ten
To sa techniki rozwiazywania kolizji. Najprostsza
technika polega na tym, zeby zapisac w pozycji
obok, jesli wlasciwa pozycja jest zajeta. Z takiej
tablicy nie mozna usuwac (wlasciwie to mozna,
ale tylko w odwrotnej kolejnosci niz bylo wstawianie),
zyskuje sie za to lepsza wydajnosc i prostsza
implementacje - uzywam w szachach.

> 2) jak wrocic z wartosci hasza do encji
Poprzez zapamietanie par:
struct {
encja;
hash;
}

> z tego co pisze na wiki wyglada mi na to
> ze byc moze nie ma na to jakichs specjalnych
> rozwiazan tj chyba po prostu obok hasza
> zapisuje sie liste oryginalnych encji czy tez
> wskaznikow -
Tak, to w pelni funkcjonalne rozwiazanie kolizji, a to
ktore opisalem na poczatku, daje mniejsze mozliwosci.


> o tyle nie jest to chyba jakies
> cudowne rozwiazanie choc do pogrupowania moze
> być
Nie wiem czy cud czy nie cud. Duzo zalezy od organizaci
danych w konkretnym modelu obliczen. Na PC mamy dostep
swobodny. Gdy rozmiar danych znacznie przekracza rozmiar
pamieci cache, to czas dostepu jest staly - i dlatego
w praktyce hash-table moze dzialac bardzo wydajnie.


Ale kiedys moze jakis inny model obliczen stanie sie
popularny. Mozna wziac np. kule 3d, w niej upakowane dane i
biliony glowic poruszajaych sie po wytyczonych trasach ze
stala predkoscia (np. z predkascia swiatla). Jak to zadanie
rozwiazac optymalnie na takim modelu?

Pozdrawiam

do góry

On 28.03.2013 11:27, M.M. wrote:
> 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.

No shit, Captain Obvious, you Sherlock us.

--
Pozdrawiam
Michoo

do góry

W dniu 2013-03-28 08:55, firr kenobi pisze:

> a czym sie rozni hashowana od niehashowanej w sensie sprawnosci ?

Zwykła mapa [std::map] jest implementowana na drzewach,
czerwonoczarnych bodajże.
"Hashowana" [std::unodrered_set] to zwykłą tablica hashująca.

Pewne rzeczy lepiej robić na jednej, pewne na drugiej.


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

http://pl.wikipedia.org/wiki/Tablica_mieszaj%C4%85ca
google, książka do algorytmów i czytaj.

pzdr
bartekltg

do góry

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

do góry

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

pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 16:39:59 UTC+1 użytkownik bartekltg napisał:

> BTW, czy taki printf w pętli za każdym razem parsuje ten
> swój napis typu "%d"?
Gdy sprawdzalem, to sprintf/sscanf byly wyraznie wolniejsze od
innych metod konwersji.
Pozdrawiam

do góry

W dniu 2013-03-28 11:25, M.M. pisze:
> 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 :)

@prędkość. Mamy też inną złożoność:)
Przy odpowiednich założeniach o statystyce, czyli jak funkcja
mieszajaca jest dobra.

>
> Hash-table ma problem gdy chcemy dodac wiecej elementow niz na poczatku
> zalozylismy.

Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
pewnie tylko raz jeszcze musisz policzy.

> Z drzewami jest problem gdy zrobi sie z nich lista - specyficzne
> dane, trzeba uzyc wersji wywazaniem, a to dodatkowy narzut.

Inaczej, drzewa bez jekiegoś systemu równoważenia nie są
w ogole do rozpatrywania jako ogólny kontener:)

pzdr
bartekltg

do góry

W dniu czwartek, 28 marca 2013 17:15:55 UTC+1 użytkownik bartekltg napisał:
> W dniu 2013-03-28 11:25, M.M. pisze:
>
> > 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 :)
>
>
>
> @prędkość. Mamy też inną złożoność:)
>
> Przy odpowiednich założeniach o statystyce, czyli jak funkcja
>
> mieszajaca jest dobra.
>
>
>
> >
>
> > Hash-table ma problem gdy chcemy dodac wiecej elementow niz na poczatku
>
> > zalozylismy.
>
>
>
> Ojtam, realokujesz do większej. Vector robi to samo. Tutaj
>
> pewnie tylko raz jeszcze musisz policzy.
>
>
>
> > Z drzewami jest problem gdy zrobi sie z nich lista - specyficzne
>
> > dane, trzeba uzyc wersji wywazaniem, a to dodatkowy narzut.
>
>
>
> Inaczej, drzewa bez jekiegoś systemu równoważenia nie są
>
> w ogole do rozpatrywania jako ogólny kontener:)
>
>

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

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

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

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 ?

???

do góry