On Saturday, September 19, 2015 at 8:44:44 PM UTC+2, bartekltg wrote:
> Aj!
> Racja.
> Na szczęśćie dla wyników, na które patrzyłem, czyli najdłuższych,
> i tak była jedna pętla, te wyniki wiec się nie znieniły.
Tak

> >> Nagmatwałeś troche z różną ilośćią zer;-)
> > Był błąd, powinno być tak:
> > for( int i=0 ; i<size ; i++ ) {
> > if( t[i] != 0 ) {
> > if( ! exist_mm( t[i] , u , s2) )
> > t[size2++] = t[i];
> > } else if( !zero ) {
> > t[size2++] = 0;
> > zero = true;
> > }
> > }
>
> Tak, teraz działą.
>
> Hackerstwo ;-)
> Ale ładne.
Dziękuję :)


> TEraz tylko osobny kubełek dla zer i mamy
> szybką hastablicę (bez usuwania).
To jest tylko głupia hash-table, a ile można usprawnień i wersji
zaimplementować. Do konkretnych danych można lepiej funkcję hash
dopasować. Do losowych faktycznie nie ma sensu. Można wyzbyć się
operacji modulo, na rzecz bitowego and. Można testować na 64
pozycje w przód w jednym ifie lub jednej pętli.



> >> i wtedy nie musimy co chwila robić realokacji i rehashowania,
> >> gotowa hashmapa jest 2.5 raza wolniejsza. I to jest spodziewany
> >> wynik,
> > Hmmm ja bym się spodziewał się max 1.5 raza.
>
> Pamiętaj, żę nie napisałeś ogolnej tablicy hashującej,
Mimo to powinno być 1.5 raza. Nie mam czasu na zabawę, ale
coś czuję, żebym napisał ogólną ze współczynnikiem 1.5.


> tylko
> uży<=eś jednej specyficznej wartości do oznaczenia pustego pola
> w tablicy (i jakbyś tworzył pełną tablicę hashującą, miałbyś
> osobny kubełek na zera) Zrobienie tego w ogolności (dla dowolnego typu)
> jest dość trudne.
> Nie masz usuwania z tablicy - dopisane w tej wersji byłoby
> kosztowne.
Jest jeszcze jedna sztuczka, czasami się opłaca. Zamiast kubełka na
wartość zero, robi się tablicę bitów z info o zajętych pozycjach.
W trakcie dodawania, zliczasz ile maksymalnie było przeskoczonych
zapełnionych pozycji. Potem, w trakcie usuwania i wyszukiwania, tyle
samo wykonujesz iteracji. Ilość iteracji może wzrosnąć do
dużej wartości przy złym rozproszeniu i małym zapełnieniu. Ale można
takich wartości zapamiętać wiele, np. jedna dla każdych 1-10tys
entry point w hash-table... niby to tylko głupia hash-table ;-)



> Jak się buduje pałną talicę hashującą, aż takiej poprawy nie ma:
> http://incise.org/hash-table-benchmarks.html
>
> Googlowa jest neicałe 2 razy szybsza od unordered set.
>
> I teraz pytanie, na ile użycie własnej konstrukcji opłaca się
> w strosunku do gotowca. Przyszpieszenie ejst bardzo wyraźne, ale
> musiałeś to napsiać i jeszczer błąd się wkradł.
Cóż, albo bierzemy gotowca, albo rzeźbimy sami, narażając się na
błędy i stratę czasu. Każdy wyboru musi dokonać sam.


> >> bo tamta hashmapa rozwiązuje kolizje tworząc listę,
> >> a Twoja stosuje sztuczkę z wartośćią specjalną . Jeśli informację
> >> o zajętości będziesz trzymał w osobnej tablicy, różnica ciut spadnie.
> > Nie wiem co jest bardziej kosztowne. Ciągły if(zero), czy dodatkowa
> > tablica bitów. Z tablicą bitów, w przypadku mocno zapełnionej
> > tablicy, można przeskoczyć 64 zapełnienia w jednym ifie.
>
> W przypadku hashmapy bardzon ważne jest cache. Jak masz dwie tablice,
> to masz dwa razy więcej dostępów.
Teoretycznie tak, ponieważ są dwa strzały w losowe miejsce RAM. Jednak z
tego co pamiętam z pomiarów własnych, to nie spowalniało wyraźnie.


> Stadndard nie precyzuje, gcc implementuje... identyczność ;-)
> Tu nie będzie miało to znaczenia, bo dane sa losowe.
Racja.

Pozdrawiam