-
Path: news-archive.icm.edu.pl!agh.edu.pl!news.agh.edu.pl!newsfeed2.atman.pl!newsfeed.
atman.pl!.POSTED!not-for-mail
From: bartekltg <b...@g...com>
Newsgroups: pl.comp.programming
Subject: Re: Tablica int i usuwanie duplikatów
Date: Sat, 19 Sep 2015 18:10:58 +0200
Organization: ATMAN - ATM S.A.
Lines: 159
Message-ID: <mtk1ej$581$1@node1.news.atman.pl>
References: <q1dqtorkbx55$.vtwhsmj03gkt$.dlg@40tude.net>
<a...@n...v.pl>
<mtbd2l$9d5$1@node2.news.atman.pl>
<5...@g...com>
<mtbvi8$1ro$1@node1.news.atman.pl> <mtc22e$4hh$1@node1.news.atman.pl>
<mtc3ip$vok$1@node2.news.atman.pl> <mtc56n$7m6$1@node1.news.atman.pl>
<b...@g...com>
<mtcaik$d1l$1@node1.news.atman.pl> <mtckeb$nhk$1@node1.news.atman.pl>
<mtcmsn$j1k$1@node2.news.atman.pl> <mtcq5e$tdl$1@node1.news.atman.pl>
<1...@g...com>
<mtfe8g$7cu$1@node2.news.atman.pl>
<a...@g...com>
<1...@4...net>
<mthm8f$p6g$1@node1.news.atman.pl>
<1...@4...net>
<mthp48$epf$1@node2.news.atman.pl>
<1amtzmln34a1o$.kdovd8ebh5p5$.dlg@40tude.net>
<mticic$1e6$1@node2.news.atman.pl>
<6...@g...com>
NNTP-Posting-Host: 89-73-81-145.dynamic.chello.pl
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
X-Trace: node1.news.atman.pl 1442679059 5377 89.73.81.145 (19 Sep 2015 16:10:59 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sat, 19 Sep 2015 16:10:59 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
Thunderbird/38.2.0
In-Reply-To: <6...@g...com>
Xref: news-archive.icm.edu.pl pl.comp.programming:208366
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 19.09.15 18:13 bartekltg
- 19.09.15 18:20 bartekltg
- 19.09.15 18:58 M.M.
- 19.09.15 20:44 bartekltg
- 19.09.15 20:45 slawek
- 19.09.15 20:52 bartekltg
- 19.09.15 21:01 bartekltg
- 20.09.15 16:27 slawek
- 20.09.15 17:14 bartekltg
- 21.09.15 08:09 Tomasz Kaczanowski
- 22.09.15 13:43 M.M.
Najnowsze wątki z tej grupy
- Do czego nadaje się QDockWidget z bibl. Qt?
- Bibl. Qt jest sztucznie ograniczona - jest nieprzydatna do celów komercyjnych
- Co sciaga kretynow
- AEiC 2024 - Ada-Europe conference - Deadlines Approaching
- Jakie są dobre zasady programowania programów opartych na wtyczkach?
- sprawdzanie słów kluczowych dot. zła
- Re: W czym sie teraz pisze programy??
- Re: (PDF) Surgical Pathology of Non-neoplastic Gastrointestinal Diseases by Lizhi Zhang
- CfC 28th Ada-Europe Int. Conf. Reliable Software Technologies
- Młodzi programiści i tajna policja
- Ada 2022 Language Reference Manual to be Published by Springer
- Press Release - AEiC 2023, Ada-Europe Reliable Softw. Technol.
- Ada-Europe - AEiC 2023 early registration deadline approaching
- Ada-Europe Int.Conf. Reliable Software Technologies, AEiC 2023
- Ile cykli zajmuje mnożenie liczb 64-bitowych?
Najnowsze wątki
- 2024-05-20 Fiat 125p wer. pikup - w PRL moszna było, w III Reczy [pospolitej] nie moszna
- 2024-05-19 Pożar salonu z chińskimi elektrykami
- 2024-05-18 LED
- 2024-05-19 ceny nieruchomości
- 2024-05-18 Szczecin => UX/UI Designer <=
- 2024-05-18 Warszawa => Mid PHP Developer (Laravel) <=
- 2024-05-18 Warszawa => Software .Net Developer <=
- 2024-05-18 Warszawa => Mid/Senior QA Engineer <=
- 2024-05-18 Ulm => Solution Architect (sichere Kommunikation und IoT-Loesungen <=
- 2024-05-18 Katowice => Head of Virtualization Platform Management and Operating S
- 2024-05-18 Warszawa => SAP WM Consultant / Execution <=
- 2024-05-18 Wrocław => Consultant/Implementer Comarch ERP XL <=
- 2024-05-18 Gdańsk => Head of International Freight Forwarding Department <=
- 2024-05-18 Warszawa => Account Manager (Recruitment Services) <=
- 2024-05-18 Łódź => Salesperson - CRM Systems <=