-
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 20:44:42 +0200
Organization: ATMAN - ATM S.A.
Lines: 134
Message-ID: <mtkaer$sng$1@node2.news.atman.pl>
References: <q1dqtorkbx55$.vtwhsmj03gkt$.dlg@40tude.net>
<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>
<mtk1ej$581$1@node1.news.atman.pl>
<0...@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: node2.news.atman.pl 1442688283 29424 89.73.81.145 (19 Sep 2015 18:44:43 GMT)
X-Complaints-To: u...@a...pl
NNTP-Posting-Date: Sat, 19 Sep 2015 18:44:43 +0000 (UTC)
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:38.0) Gecko/20100101
Thunderbird/38.2.0
In-Reply-To: <0...@g...com>
Xref: news-archive.icm.edu.pl pl.comp.programming:208370
[ ukryj nagłówki ]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
Następne wpisy z tego wątku
- 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
- Popr. 14. Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- Arch. Prog. Nieuprzywilejowanych w pełnej wer. na nowej s. WWW energokod.pl
- 7. Raport Totaliztyczny: Sprawa Qt Group wer. 424
- TCL - problem z escape ostatniego \ w nawiasach {}
- Nauka i Praca Programisty C++ w III Rzeczy (pospolitej)
- testy-wyd-sort - Podsumowanie
- Tworzenie Programów Nieuprzywilejowanych Opartych Na Wtyczkach
- 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
Najnowsze wątki
- 2025-02-01 "Nie kupujcie samochodów elektrycznych
- 2025-02-01 jakie małe auto duże w środku :-)
- 2025-02-01 Re: pytanie do oponiarzy lub szybkojeżdzących (opony Hankook Ventus Prime, S1 Evo, alternatywy)
- 2025-02-01 T-1000 was here
- 2025-02-01 Warszawa => DevOps Engineer <=
- 2025-02-01 Katowice => Administrator IT - Operating Systems and Virtualization <=
- 2025-02-01 Warszawa => Spedytor międzynarodowy <=
- 2025-02-01 Śmierć mózgu a narządy do pobrania
- 2025-01-31 A niektórym to naprawdę zależy na ekologi w miastach LPG POWRACA ;-)
- 2025-01-31 Lublin => Programista Delphi <=
- 2025-01-31 Łódź => Programista NodeJS <=
- 2025-01-31 Wrocław => Senior SAP Support Consultant (SD) <=
- 2025-01-31 Warszawa => Full Stack web developer (obszar .Net Core, Angular6+) <=
- 2025-01-31 Gdańsk => iOS Developer (Swift experience) <=
- 2025-01-31 Kraków => UX Designer <=