Algoritmer og Datastrukturer 1

Eksperimentelle erfaringer med Sortering

Denne side viser eksperimentelle data for forskelige sorterings algoritmer. De algoritmerne der er implementeret er:

For at optimere de rekursive sorterings algoritmer QuickSort og MergeSort, skiftes der for små problemstørrelser til InsertionSort. Nedenstående plots, threshold.pdf, viser udførselstiden (y-aksen) for MergeSort og QuickSort når problemstørrelsen hvor man skifter over til InsertSort varieres (x-aksen). Desuden vises plots for antal sammenligninger, "cache faults", og "branch mispredictions" (de sidste to er nogle hardware egenskaber der påvirker udførselstiden væsentligt). Alle eksperimenterne svarer til sorteringer af 300.000 tilfældige elementer.

Det ses på henholdsvis side 1 og 5 af threshold.pdf at for både MergeSort og QuickSort opnås den bedste udførselstid når man skifter over til InsertionSort ved problemer af størrelse 10-15 elementer. I de efterfølgende eksperimenter sker skriftet ved 10 elementer.

I nedenstående plots ses en sammenligning af udførselstiden (y-aksen) for InsertionSort, MergeSort, HeapSort, og QuickSort når problemstørrelsen vorkser (x-aksen). Desuden vises plots for antal sammenligninger, "cache faults", og "branch mispredictions" for de fire algoritmer.

Målt Med
InsertionSort
Uden
InsertionSort
Tid time5.pdf time4.pdf
Sammenligninger comps5.pdf comps4.pdf
Cache faults cache5.pdf cache4.pdf
Branch mispredictions mispred5.pdf mispred4.pdf

Af time5.pdf fremgår det klart at InsertionSort's O(n2) udførselstid gør InsertionSort meget langsommere end de øvre algoritmer der har en udførselstid på O(n log n).

Blandt algoritmerne med O(n log n) udførselstid fremgår det tydeligt af time4.pdf at HeapSort er den langsomste. MergeSort og QuickSort har ca. den samme udførselstid, selvom QuickSort udfører ca 25% flere sammenligninger end MergeSort, jvf comps4.pdf. På mispred4.pdf ses at MergeSort også medfører 60% færre branch mispredictions end QuickSort, hvilket også skulle være med til at gøre QuickSort langsommere. At QuickSort så ikke taber så meget til MergeSort, skyldes at antal cache faults for QuickSort er væsentligt lavere end for MergeSort, jvf cache4.pdf, hvilket skyldes at QuickSort ikke kopierer data mellem to arrays modsat MergeSort der flytter data mellem to arrays under fletningerne i de rekursive kald.

Eksperimenterne viser klart at InsertionSort ikke kan anvendes for store data mængder. Heapsort er en konstant faktor langsommere end MergeSort og QuickSort. MergeSort og QuickSort har begge ca. samme udførselstid - men p.g.a forskellige egenskaber ved algoritmerne.

Tak

Ovenstående eksperimenter er udført af Gabriel Moruz i februar 2006. Implementation var i C og eksperimenterne blev lavet på en Athlon 2GHz med 1Gb RAM.


Denne side vedligholdes af Gerth Stølting Brodal