Re: Tablica int i usuwanie duplikatów

Newsgroups	pl.comp.programming
Date	2015-09-19 04:35 -0700
References	(18 earlier) <mthm8f$p6g$1@node1.news.atman.pl> <13goui39dxzb2.1kw5grc7j0y14.dlg@40tude.net> <mthp48$epf$1@node2.news.atman.pl> <1amtzmln34a1o$.kdovd8ebh5p5$.dlg@40tude.net> <mticic$1e6$1@node2.news.atman.pl>
Message-ID	<6d350592-2efd-448d-ba48-66154113be54@googlegroups.com> (permalink)
Subject	Re: Tablica int i usuwanie duplikatów
From	"M.M." <mmarszik@gmail.com>

Show all headers | View raw

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. 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
4) lepsze rozwiązanie if( zero )
Rzecz jasna, też nie wiem czy nic nie spartoliłem, macie kod do 
sprawdzenia:
http://pastebin.com/uRAqi8iv

Wyniki:

samorobka
poprawność:
12 457 1 56 89 11 55 
100 zajelo 4.551e-06s
1000 zajelo 2.9805e-05s
10000 zajelo 0.000306844s
100000 zajelo 0.004824s
1000000 zajelo 0.050433s
10000000 zajelo 0.564702s
100000000 zajelo 6.84356s // najlepszy wynik

hashmapa budowana
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.5173e-05s
1000 zajelo 0.000193544s
10000 zajelo 0.00218883s
100000 zajelo 0.0375231s
1000000 zajelo 0.797666s
10000000 zajelo 9.25089s
zbior budowany
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.7255e-05s
1000 zajelo 0.000254757s
10000 zajelo 0.00330752s
100000 zajelo 0.0667916s
1000000 zajelo 1.46435s
10000000 zajelo 23.8021s
hashmapa usuwana 
poprawność:
12 457 1 56 89 11 55 
100 zajelo 2.0964e-05s
1000 zajelo 0.000203064s
10000 zajelo 0.002271s
100000 zajelo 0.0400408s
1000000 zajelo 0.68298s
10000000 zajelo 7.91133s
sortowanie 
poprawność:
1 11 12 55 56 89 457 
100 zajelo 4.154e-06s
1000 zajelo 5.4322e-05s
10000 zajelo 0.00068978s
100000 zajelo 0.00846882s
1000000 zajelo 0.100396s
10000000 zajelo 1.16484s
100000000 zajelo 13.3129s

sortowanie stab
poprawność:
12 457 1 56 89 11 55 
100 zajelo 1.2285e-05s
1000 zajelo 0.000156857s
10000 zajelo 0.00193924s
100000 zajelo 0.023655s
1000000 zajelo 0.394504s
10000000 zajelo 7.24644s


> hashmapa budowana
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 1.206e-06s
> 100 zajelo 2.12195e-05s
> 1000 zajelo 0.00019574s
> 10000 zajelo 0.00224614s
> 100000 zajelo 0.0319085s
> 1000000 zajelo 0.447895s
> 10000000 zajelo 7.09252s
> 
> zbior budowany
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 6.55151e-07s
> 100 zajelo 1.02252e-05s
> 1000 zajelo 0.000142235s
> 10000 zajelo 0.00210293s
> 100000 zajelo 0.0458803s
> 1000000 zajelo 0.809938s
> 10000000 zajelo 14.873s
> 
> hashmapa usuwana
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 1.7566e-06s
> 100 zajelo 2.02052e-05s
> 1000 zajelo 0.000217613s
> 10000 zajelo 0.00229402s
> 100000 zajelo 0.0311955s
> 1000000 zajelo 0.484313s
> 10000000 zajelo 5.8356s
> 
> sortowanie
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 1 11 12 55 56 89 457
> szybkość
> 10 zajelo 5.79164e-08s
> 100 zajelo 8.72629e-07s
> 1000 zajelo 1.14487e-05s
> 10000 zajelo 0.000183957s
> 100000 zajelo 0.00351675s
> 1000000 zajelo 0.0574259s
> 10000000 zajelo 0.73433s
> 
> sortowanie stab
> poprawność:
> 12 457 12 457 1 56 89 12 11 11 55 11 11 1 457
> 12 457 1 56 89 11 55
> szybkość
> 10 zajelo 2.14358e-07s
> 100 zajelo 3.83037e-06s
> 1000 zajelo 7.91519e-05s
> 10000 zajelo 0.00108764s
> 100000 zajelo 0.0153062s
> 1000000 zajelo 0.267471s
> 10000000 zajelo 5.37913s


Pozdrawiam

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