[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

pl.comp.programming

QuickSort vs RandomizedQuickSort

Michal Lipek

5/11/2007 12:21:00 AM

Witam wszystkich.

Algorytm Quicksort ka?dy z nas pewnie zna. Wersja ulosowiona ró?ni sie
tym, ?e piwot (czy te? element dziel?cy) wybierany losowo spo?ród
dostepnych.
Matematyczne rozwa?ania sk3aniaj? do wniosku, ?e wersja ulosowiona
powinna bya troszeczke bardziej wydajna. Jednak w praktyce wychodzi mi
co? innego.

Napisa3em program zarówno w C jak i w Pythonie i ci?gle wersja
tradycyjna wygrywa. Napisa3em nawet samodzielnie algorytm losuj?cy
liczby pseudolosowe. Zamiast Mersenne Twister, domy?lnego w Pythonie,
u?y3em w3asnego -- LCG (to ten prosty z jednym mno?eniem, dodawaniem,
modulo i du?? ilo?ci? brzydkich korelacji). Wynik sie poprawi3, ale
bardzo nieznacznie. W C nie zmienia3em algorytmu losuj?cego.

Wszystko wskazuje na to, ?e generowanie liczby pseudolosowej trwa zbyt
d3ugo i w konsekwencji algorytm przez to dzia3a wolniej. Danymi
wej?ciowymi by3o 10000, 100000, 1000000 liczb ca3kowitych z przedzia3u
[-MAXINT-1, MAXINT] wygenerowanych standardow? funkcj? C -- rand().

Gdybym strzela3 dlaczego tak sie dzieje powiedzia3bym, ?e problemem s?
dane. Na mój ch3opski rozum, gdy jako danych u?yje ca3kowicie losowych
liczb, losowy wybór pivotu nie przyspieszy algorytmu.

Pytania:
1. Czy doszed3em do dobrych wniosków?
2. Je?eli odpowied? na pytanie 1 jest TAK, to sk?d wzi?a dane na których
wyjdzie, ?e RandQS jest szybszy?

Dziekuje za uwage i pozdrawiam,
Micha3 Lipek

--
Micha3 Lipek
http://blog...
2 Answers

Bogus

5/11/2007 8:32:00 PM

0

Dnia 11-05-2007 o 02:20:33 MichaÅ? Lipek <renegados@interia.pl> napisaÅ?(a):

> Witam wszystkich.
>
> Algorytm Quicksort każdy z nas pewnie zna. Wersja ulosowiona różni siÄ?
> tym, że piwot (czy też element dzielÄ?cy) wybierany losowo spoÅ?ród
> dostÄ?pnych.
> Matematyczne rozważania skÅ?aniajÄ? do wniosku, że wersja ulosowiona
> powinna byÄ? troszeczkÄ? bardziej wydajna. Jednak w praktyce wychodzi mi
> coÅ? innego.
>
> NapisaÅ?em program zarówno w C jak i w Pythonie i ciÄ?gle wersja
> tradycyjna wygrywa.
[...]
>
[...]
> Danymi
> wejÅ?ciowymi byÅ?o 10000, 100000, 1000000 liczb caÅ?kowitych z przedziaÅ?u
> [-MAXINT-1, MAXINT] wygenerowanych standardowÄ? funkcjÄ? C -- rand().
>
> Gdybym strzelaÅ? dlaczego tak siÄ? dzieje powiedziaÅ?bym, że problemem sÄ?
> dane. Na mój chÅ?opski rozum, gdy jako danych użyjÄ? caÅ?kowicie losowych
> liczb, losowy wybór pivotu nie przyspieszy algorytmu.

Tak.
OIDP to dane losowe sÄ? wymarzonym wejÅ?ciem quicksorta, tak wiÄ?c wszelakie
udziwnienia algorytmu bÄ?dÄ? go tylko zwalniaÅ?y. Spróbuj przeprowadziÄ? test
na danych posortowanych, albo jeszcze lepiej takich, dla których pivot
(na pewno to siÄ? tak nazywa?) bÄ?dzie wartoÅ?ciÄ? np. minimalnÄ?.

> Pytania:
> 1. Czy doszedÅ?em do dobrych wniosków?
> 2. Jeżeli odpowiedź na pytanie 1 jest TAK, to skÄ?d wziÄ?Ä? dane na których
> wyjdzie, żÄ? RandQS jest szybszy?
>
> DziÄ?kujÄ? za uwagÄ? i pozdrawiam,
> MichaÅ? Lipek
>


--
BoguÅ?
www.google.pl <-- to nie boli
http://bogu...

Pawel Kierski

5/12/2007 12:14:00 PM

0

franek w wiadomo?ci <op.tr6jb1t48vokt5@blackstar> pisze:
[...]
> OIDP to dane losowe s? wymarzonym wej?ciem quicksorta, tak wiec wszelakie
> udziwnienia algorytmu bed? go tylko zwalnia3y. Spróbuj przeprowadzia test
> na danych posortowanych, albo jeszcze lepiej takich, dla których pivot
> (na pewno to sie tak nazywa?) bedzie warto?ci? np. minimaln?.

Takim przypadkiem bedzie np. sortowanie danych posortowanych, gdy
jako ?rodkowy element wybiera sie warto?a pierwsz? z przedzia3u
sortowanego. Wtedy zawsze podzia3 jest na 1, N-1. Dlatego te?
wybieranie elementu ze ?rodka przedzia3u zazwyczaj dzia3a lepiej - dla
danych posortowanych jest to optymalne rozwi?zanie. Oczywi?cie zawsze
dla QS jest taka sekwencja, która prowadzi do podzia3ów 1, N-1, ale
wybieraj?c ?rodkowy element trudniej na ni? trafia w rzeczywistych
sytuacjach (gdzie dane bywaj? cze?ciowo posortowane).

--
Pawe3 Kierski
news@pkierski.net
dodaj "[nomorespam]" w temacie je?li piszesz z domeny innej ni? .pl,
albo koniecznie chcesz obej?a moje filtry 8-)