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

do góry

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ę"

do góry

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

do góry

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ę"

do góry

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

do góry

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ę"

do góry

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

do góry

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

do góry

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

do góry

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

do góry