Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > pl.comp.programming > #27487 > unrolled thread

Tablica int i usuwanie duplikatów

Back to article view | Back to pl.comp.programming

Contents

  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

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

#27557

On Saturday, September 19, 2015 at 1:35:59 PM UTC+2, M.M. wrote:
> On Saturday, September 19, 2015 at 3:08:29 AM UTC+2, bartekltg wrote:
> > http://pastebin.com/Bd53Qj2e
> > 
> > cztery wersje, z hashmapą, ze zbiorem na drzewie, z hashmapą,
> 
> 
> Pozdrawiam

Bym zapomniał. Co z wersją multiprocesorową tego algorytmu? 
Mergesort jest najlepszy?
Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#27558

On Sat, 19 Sep 2015 04:35:57 -0700 (PDT), M.M. wrote:

> Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do 
> sprawdzenia:
> http://pastebin.com/uRAqi8iv

W jakim kompilatorze to kompilujecie? Czy to zgodne z MS VS C++?
A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
odpalić i krokowo "zbadać"?

Pytanie drugie:

 return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;

Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
założeń czy statystycznie wyliczone?


-- 
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

[toc] | [prev] | [next] | [standalone]

#27559

On Saturday, September 19, 2015 at 2:43:47 PM UTC+2, szemrany wrote:
> W jakim kompilatorze to kompilujecie? 
Chyba dowolny C++11


> Czy to zgodne z MS VS C++?
Chyba tak.


> A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
> odpalić i krokowo "zbadać"?
Może qtcreator?



> Pytanie drugie:
>  return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;
> 
> Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
> założeń czy statystycznie wyliczone?
Wpisałem na oko :)


Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#27560

On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:

> qtcreator?

Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
sprawia dobre wrażenie:

http://www.codeblocks.org/features
http://sourceforge.net/projects/orwelldevcpp/
http://www.bloodshed.net/dev/

Dzięki

-- 
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

[toc] | [prev] | [next] | [standalone]

#27561

On Saturday, September 19, 2015 at 3:08:04 PM UTC+2, szemrany wrote:
> On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:
> 
> > qtcreator?
> 
> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
> sprawia dobre wrażenie:
> 
> http://www.codeblocks.org/features
> http://sourceforge.net/projects/orwelldevcpp/
> http://www.bloodshed.net/dev/
> 

Przepraszam, nie mogę, mam za dużo własnej roboty.
Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#27562

On Sat, 19 Sep 2015 06:23:04 -0700 (PDT), M.M. wrote:

>> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka
>> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
>> sprawia dobre wrażenie:
>> 
>> http://www.codeblocks.org/features
>> http://sourceforge.net/projects/orwelldevcpp/
>> http://www.bloodshed.net/dev/
> 
> Przepraszam, nie mogę, mam za dużo własnej roboty.
> Pozdrawiam

Oki, no problem, może ktoś inny przeczyta features list i oceni.
Dzięki za udział w wątku i modyfikacje kodu Bartka.

-- 
howgh
szemrany
"Trzeba z żywymi naprzód iść, po życie sięgać nowe,
a nie w uwiędłych laurów liść z uporem stroić głowę"

[toc] | [prev] | [next] | [standalone]

#27567

On 19.09.2015 15:08, szemrany wrote:
> On Sat, 19 Sep 2015 05:50:02 -0700 (PDT), M.M. wrote:
>
>> qtcreator?
>
> Pogooglałem i qtCreator jest ponoć wielki i ciężki, ale jest kilka

Lżejszy niż VS:)

Na razie chcesz tylko użyć kompilatora, nie ich środowiska
graficznego (new project-> non-QT project-> plain c++ project).

Jeśli coś się nie kompiluje, trzeba dodać do pliku *.pro linijkę

QMAKE_CXXFLAGS += -std=c++11

> lżejszych środowisk, jeśli możesz to rzuć okiem i oceń, które z poniższych
> sprawia dobre wrażenie:
>
> http://www.codeblocks.org/features

Podobno niezły.

> http://sourceforge.net/projects/orwelldevcpp/

Lata temu używałem (zanim zdechło a potem się odrodziło).

> http://www.bloodshed.net/dev/

Pierwsze słyszę.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#27575

W dniu 2015-09-19 18:20, bartekltg pisze:
>> http://www.bloodshed.net/dev/
>
> Pierwsze słyszę.

to devc++ - wersja bardzo leciwa, wiem, że gdzieś jest jakis fork - 
trochę uaktualniony.

-- 
Kaczus
http://kaczus.ppa.pl

[toc] | [prev] | [next] | [standalone]

#27566

On 19.09.2015 14:50, M.M. wrote:
> On Saturday, September 19, 2015 at 2:43:47 PM UTC+2, szemrany wrote:
>> W jakim kompilatorze to kompilujecie?
> Chyba dowolny C++11
>
>
>> Czy to zgodne z MS VS C++?
> Chyba tak.
>
>
>> A jest może jakieś proste IDE dla Windows, żeby można pod debugerem to
>> odpalić i krokowo "zbadać"?
> Może qtcreator?


+1


>
>
>
>> Pytanie drugie:
>>   return ( (xx*67523u + 31237u) ^ (xx*78529u + 96285u) ) % s2;
>>
>> Skąd akurat takie wartości w hashu? To wynika z jakichś matematycznych
>> założeń czy statystycznie wyliczone?
> Wpisałem na oko :)


I dzieki temu wyniki sa parzyste ;-)

pzdr
barteklt

[toc] | [prev] | [next] | [standalone]

#27565

On 19.09.2015 13:35, M.M. wrote:
> On Saturday, September 19, 2015 at 3:08:29 AM UTC+2, bartekltg wrote:
>> http://pastebin.com/Bd53Qj2e
>>
>> cztery wersje, z hashmapą, ze zbiorem na drzewie, z hashmapą,
>> ale wstepnie wypelnioną i opróżnianą, oraz wersja naiwna.
>> Do tego wersja z sortowaniem, która biła na głowę wszystko;-)
>>
>> Dalej w kodzie nie ma nic ciekawego a jest brzydki:]
>>
>> M.M jednak miał niezłą intuicję, algorytm naiwny trzyma się jako
>> tako do 1000 liczb! Przynajmniej w porównaniu do kontenerowych,
>> w stosunku do sortowania to przebija już dla 10.
> Jeśli algorytmy się przełączają na inne wersje gdy jest
> mało elementów, to moja intuicja nie ma tutaj zastosowania :)
>
>
>
>
>> Sortowanie diała tak dobrze, że dorzuciłem gdzieś wpominaną wersję,
>> gdzie kopiuję tablice, sortuję, wyszukuję w niej przetwarzanego
>> elementu i indeksu tego elementu używam na tablicy 'czy już było'.
>> Szybsze, ale nie tak jak samo sortowanie i 'unique'.
>>
>> Czy gdzieś nie ma błędów, nie wiem, specjalnie mocno nie testowałem ;-)
> Tylko nie byłem pewny, czy nie sortujesz już częściowo posortowanych
> elementów.


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.

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


> 4) lepsze rozwiązanie if( zero )

No tak, zero to całkiem poprawna wartość inta;>
Dorzuć kilka zer do testowej tablicy, nie działa.



> Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do
> sprawdzenia:
> http://pastebin.com/uRAqi8iv
>
> Wyniki:

Nagmatwałeś troche z różną ilośćią zer;-)
po odgmatwaniu widać, że ręczna hashmapa jest kilkanaście(!)*
razy szybsze. No to śledztwo:

Tochę porównujemy jakbłka z gruszkami.
"
  (unsigned int)(size/2*5+2);

     cout<<"s2 "<<s2<<endl;

     int *u = new int[s2];
"

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


samorobka
100 zajelo 3.4711e-05s
1000 zajelo 0.000145689s
10000 zajelo 0.000330489s
100000 zajelo 0.00406414s
1000000 zajelo 0.0826325s
10000000 zajelo 0.97905s

hashmapa budowana
10 zajelo 1.18089e-06s
100 zajelo 1.31643e-05s
1000 zajelo 0.000130519s
10000 zajelo 0.00139489s
100000 zajelo 0.0192994s
1000000 zajelo 0.233072s
10000000 zajelo 2.65135s

zbior budowany
10 zajelo 6.43753e-07s
100 zajelo 1.03399e-05s
1000 zajelo 0.000142441s
10000 zajelo 0.00209884s
100000 zajelo 0.0432259s
1000000 zajelo 0.777911s
10000000 zajelo 14.2428s

hashmapa usuwana
10 zajelo 1.90731e-06s
100 zajelo 1.9725e-05s
1000 zajelo 0.000195841s
10000 zajelo 0.00210182s
100000 zajelo 0.0296034s
1000000 zajelo 0.389643s
10000000 zajelo 4.44893s

sortowanie
10 zajelo 5.58256e-08s
100 zajelo 8.79121e-07s
1000 zajelo 1.12299e-05s
10000 zajelo 0.000183867s
100000 zajelo 0.00352831s
1000000 zajelo 0.0571969s
10000000 zajelo 0.732117s

sortowanie stab
10 zajelo 2.3127e-07s
100 zajelo 4.69011e-06s
1000 zajelo 8.10539e-05s
10000 zajelo 0.00110062s
100000 zajelo 0.0153352s
1000000 zajelo 0.256625s
10000000 zajelo 5.16851s



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


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#27568

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()  );


> > 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;
        }
    }



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


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

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

http://pastebin.com/bEat8KH2

samorobka
poprawność:
12 457 0 1 56 89 11 55 
100 zajelo 2.794e-06s
1000 zajelo 1.986e-05s
10000 zajelo 0.000210824s
100000 zajelo 0.00289853s
1000000 zajelo 0.0475682s
10000000 zajelo 0.460168s
100000000 zajelo 4.75097s

hashmapa budowana
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.5469e-05s
1000 zajelo 0.000191005s
10000 zajelo 0.00231907s
100000 zajelo 0.0382351s
1000000 zajelo 0.791762s
10000000 zajelo 9.07928s
zbior budowany
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.4478e-05s
1000 zajelo 0.000254404s
10000 zajelo 0.00330699s
100000 zajelo 0.0680503s
1000000 zajelo 1.4365s
10000000 zajelo 23.5209s
hashmapa usuwana 
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.6489e-05s
1000 zajelo 0.000204336s
10000 zajelo 0.00230099s
100000 zajelo 0.0386139s
1000000 zajelo 0.687652s
10000000 zajelo 7.9165s
sortowanie 
poprawność:
1 11 12 55 56 89 457 
100 zajelo 6.077e-06s
1000 zajelo 5.4831e-05s
10000 zajelo 0.000708904s
100000 zajelo 0.00844671s
1000000 zajelo 0.100287s
10000000 zajelo 1.16515s
100000000 zajelo 13.3513s

sortowanie stab
poprawność:
12 457 1 56 89 11 55 
100 zajelo 1.053e-05s
1000 zajelo 0.000133041s
10000 zajelo 0.00170499s
100000 zajelo 0.0232212s
1000000 zajelo 0.395624s
10000000 zajelo 7.17122s


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

Pozdrawiam

[toc] | [prev] | [next] | [standalone]

#27569

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

[toc] | [prev] | [next] | [standalone]

#27576

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

[toc] | [prev] | [next] | [standalone]

#27535

On Wed, 16 Sep 2015 11:34:13 +0200, bartekltg <bartekltg@gmail.com> 
wrote:
> Dlatego proponowałem (unordered_)set zamiast (...)map.

A jest set w Fortranie?

[toc] | [prev] | [next] | [standalone]

#27537

On 17.09.2015 08:12, slawek wrote:
> On Wed, 16 Sep 2015 11:34:13 +0200, bartekltg <bartekltg@gmail.com> wrote:
>> Dlatego proponowałem (unordered_)set zamiast (...)map.
>
> A jest set w Fortranie?


A w  Formula Translator jest coś poza macierzami zespolonymi? ;-)

Jak nie ma, to trzeba napisać.
Albo użyć języka, który lepiej nadaje się do naszych zadań.

pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

#27538

Użytkownik "bartekltg" <bartekltg@gmail.com> napisał:

> Jak nie ma, to trzeba napisać.

Juz dawno napisane. Np:

http://flibs.sourceforge.net/sets.html

AK 


---
Ta wiadomość została sprawdzona na obecność wirusów przez oprogramowanie antywirusowe Avast.
https://www.avast.com/antivirus

[toc] | [prev] | [next] | [standalone]

#27543

On Thu, 17 Sep 2015 15:14:54 +0200, bartekltg <bartekltg@gmail.com> 
wrote:
> A w  Formula Translator jest coś poza macierzami zespolonymi? ;-)

Są coarray.  Jest OMP i ACC.  BLAS. Jest operator potęgowania.

[toc] | [prev] | [next] | [standalone]

#27546

On 18.09.2015 07:22, slawek wrote:
> On Thu, 17 Sep 2015 15:14:54 +0200, bartekltg <bartekltg@gmail.com> wrote:
>> A w  Formula Translator jest coś poza macierzami zespolonymi? ;-)
>
> Są coarray.  Jest OMP i ACC.  BLAS. Jest operator potęgowania.

Czyli możesz mnożyć zespolone macierze równolegle i na GPU ;-)

FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej
specjalizacji. Można tworzyć tam odpowiednik wszystkich struktur STLa.
Tylko po co skoro jest to bardzo upierdliwe i niewygodne. W COBOLu też
można ;-)


pzdr
bartgekltg

[toc] | [prev] | [next] | [standalone]

#27570

On Fri, 18 Sep 2015 15:15:32 +0200, bartekltg <bartekltg@gmail.com> 
wrote:
> FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej

Do 77 nie ma wsparcia dla strukturalnego programowania. Błędna 
koncepcja I/O. Bardzo zły do przetwarzania tekstów.

[toc] | [prev] | [next] | [standalone]

#27572

On 19.09.2015 20:45, slawek wrote:
> On Fri, 18 Sep 2015 15:15:32 +0200, bartekltg <bartekltg@gmail.com> wrote:
>> FORTRAN jest bardzo dobrym językiem, ale jednek też o dość wąskiej
>
> Do 77 nie ma wsparcia dla strukturalnego programowania. Błędna koncepcja
> I/O. Bardzo zły do przetwarzania tekstów.

W 77 to już chyba nawet fizycy*) nie piszą ;-)

Do przetwarzania tesktów to i c++ się średnio nadaje (chociaż
gdzieśtam rope siedzi, regexpy są, ale nadal...)


*) Anegdota. Znajoma liczy jakieś kwanty z dużą precyzją.
"odziedziczyła" spory kod fortranowy. W tym była biblioteka
do liczb wysokiej precyzji (poczwórna i większe).
Parę lat w tym pracowała, ale w końcu postanowili powoli
przenieść się na c++. Zachęcani m.in zdanaimi jak
'będzie mniej babrania się' czyt "nawet jak będzie dwa razy
wolniej, to dasz radę napisać subtelniejszy algorytm".

Jako wersja próbna parę podstawowych klocków zostało napsianych
z użyciem mpfr (bardzo niewydajen pamięciowo jak chce się
tylko 4 cxzy 8 krotną precyzję) i eigen (bo trzeba jakoś
tabelkę tem mpfrów traktować jak macierz).

I wszyscy byli zaskoczeni, jak ta wersja liczyła grube
kilka razy szybciej. FORTRAN bardzo szybki jest, ale
bibliotekę wysokiej precyzji ktoś schrzanił.

Nie byłoby w tym nic złego, w końcu wszędzie zdarzają się
źle napisane rzeczy, to nie wina języka, ale dłużej
trzymali się FORTRANa 'bo ten jest szybszy do numeryki'.


pzdr
bartekltg

[toc] | [prev] | [next] | [standalone]

Page 3 of 4 — ← Prev page 1 2 [3] 4  Next page →

Back to top | Article view | pl.comp.programming

csiph-web