Re: Tablica int i usuwanie duplikatów

From	bartekltg <bartekltg@gmail.com>
Newsgroups	pl.comp.programming
Subject	Re: Tablica int i usuwanie duplikatów
Date	2015-09-19 20:44 +0200
Organization	ATMAN - ATM S.A.
Message-ID	<mtkaer$sng$1@node2.news.atman.pl> (permalink)
References	(18 earlier) <1amtzmln34a1o$.kdovd8ebh5p5$.dlg@40tude.net> <mticic$1e6$1@node2.news.atman.pl> <6d350592-2efd-448d-ba48-66154113be54@googlegroups.com> <mtk1ej$581$1@node1.news.atman.pl> <06313417-a986-4d9a-a5aa-1eb3f65d4dbe@googlegroups.com>

Show all headers | View raw

On 19.09.2015 18:58, M.M. wrote:
> On Saturday, September 19, 2015 at 6:10:59 PM UTC+2, bartekltg wrote:
>> Przecież tablica była losowana, dlaczego miałaby być posorotwana?
>>
>>       random_device rd;
>>       mt19937 gen(rd());
>> ....
>>           generate(tab.begin(), tab.end(), gen);
>>
>> Przez każdym pojedyńczym pomiarem.
> Tutaj miałem te obawy:
> for (int i=0; i<100000/size+1;i++)
>      tab.erase( f( tab.begin(),tab.end() ), tab.end()  );

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.


>
>
>>> Lekko zmieniłem Twój kod i dodałem moją samoróbkę. Moją
>>> samoróbkę można jeszcze ze dwa razy przyspieszyć przez:
>>> 1) lepszą kompilację
>>> 2) profilowanie
>>> 3) lepszą funkcję hash
>>
>>
>> Napisać to w c++, nie C ;->
> Etam :)
>
>
>>> 4) lepsze rozwiązanie if( zero )
>>
>> No tak, zero to całkiem poprawna wartość inta;>
>> Dorzuć kilka zer do testowej tablicy, nie działa.

> To się gdzieś rypłem, ale na wydajność to zbytnio nie
> wpływa.


>
>
>> 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. TEraz tylko osobny kubełek dla zer i mamy
szybką hastablicę (bez usuwania).

>
>
>> po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
>> razy szybsze. No to śledztwo:
>>
>> Tochę porównujemy jakbłka z gruszkami.
> No ale jaka wygoda w programowaniu :D
>
>
>> OK, to ja też mogę wpisać:
>> iter stable_unique_1 ( iter first, iter last )
>> {
>>       unordered_set<int> temp; //zbiór użytych
>>       temp.rehash ( distance(first, last)*5/2+2 );  // alokuje wstępnie
>> nieco pamieci.
>>
>> 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, 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.

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


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


> U mnie samoróbka (po zmianie funkcji hash i poprawieniu zer) działa
> około 3 razy szybciej niż sortowanie i uniq.

Bardzo ładny wynik.


>> *) Domyślnie unordered set ma load_factor 1!
>> Po zmianie go na przyzwoitszy:
>> temp.max_load_factor(2.0/5.0);
>> czas spadł do 4.5 sekund z hakiem. Z grubsza 2 razy więcej
>> niż z przygotowaną tablicą (tyle się należy spodziewać).
>> Wiekszosć zwolnienia poprzednio było więc z podowu dużej
>> liczby kolizji.
> Możne domyślnie ma też kiepską funkcje hash? QT ma bardzo
> kiepską. std - nie wiem.

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

pzdr
bartekltg

Back to pl.comp.programming | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-14 21:56 +0200
  Re: Tablica int i usuwanie duplikatów Adam Klobukowski <adamklobukowski@gmail.com> - 2015-09-14 13:50 -0700
  Re: Tablica int i usuwanie duplikatów witek <witek7205@gazeta.pl.invalid> - 2015-09-14 20:23 -0500
    Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
  Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 04:10 +0200
    Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 09:32 +0200
      Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 10:50 +0200
        Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-15 12:01 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-15 14:53 +0200
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-15 14:16 +0200
      Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 07:21 +0200
        Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 07:38 +0200
          Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-16 10:57 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:34 +0200
              Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 03:31 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 12:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 05:03 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 16:49 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 17:31 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 17:58 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 18:25 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 18:28 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:41 -0700
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 19:57 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 22:46 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 23:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 00:23 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-17 05:37 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 00:18 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-18 09:07 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 18:20 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 20:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 20:47 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 21:01 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 21:36 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-18 22:50 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 03:08 +0200
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 11:34 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:52 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:35 -0700
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 04:57 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 14:43 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 05:50 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:08 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 06:23 -0700
                Re: Tablica int i usuwanie duplikatów szemrany <szemrany@offline.off> - 2015-09-19 15:44 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:20 +0200
                Re: Tablica int i usuwanie duplikatów Tomasz Kaczanowski <kaczus@dowyciecia_poczta.onet.pl> - 2015-09-21 08:09 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:13 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 18:10 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-19 09:58 -0700
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 20:44 +0200
                Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-22 04:43 -0700
              Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-17 08:12 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-17 15:14 +0200
                Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-17 16:37 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-18 07:22 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-18 15:15 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-19 20:45 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-19 21:01 +0200
                Re: Tablica int i usuwanie duplikatów slawek <fake@fakeemail.com> - 2015-09-20 16:27 +0200
                Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-20 17:14 +0200
          Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 11:05 +0200
            Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 11:40 +0200
              Re: Tablica int i usuwanie duplikatów "AK" <nobody@nowhere.com> - 2015-09-16 12:05 +0200
  Re: Tablica int i usuwanie duplikatów Sebastian Biały <heby@poczta.onet.pl> - 2015-09-16 19:11 +0200
    Re: Tablica int i usuwanie duplikatów "M.M." <mmarszik@gmail.com> - 2015-09-16 10:46 -0700
      Re: Tablica int i usuwanie duplikatów bartekltg <bartekltg@gmail.com> - 2015-09-16 19:55 +0200

csiph-web