[Algemeen] sorteeralgoritmes

[Verwijderd]

Voor mijn werk ben ik aan het programmeren aan een indexeermethode voor een databasesysteem. Deze index maakt gebruik van R-Trees. Om efficient te kunnen zoeken pas ik het STR packing algoritme toe. STR packing voert op de data recursief een aantal sorteeroperaties uit voordat de gegevens in de R-Tree geplaatst worden.

Nu had ik hiervoor eerst quick sort gebruikt. Dit werkt extreem snel, maar is enorm recursief en voor grote hoeveelheden data raak ik over de beschikbare heap space heen en dat is niet echt de bedoeling. Een ander uiterste is het bubble sort algoritme wat wel goed werkt voor grote hoeveelheden data, maar enorm inefficient en supertraag is.

M.a.w. wat voor sorteeralgoritme zouden jullie toepassen voor een enorme hoeveelheid array-data?

En om het topic algemeen te houden, welk algoritme gebruik je in welke situatie?

[silentsnow]

Is Merge Sort een optie? Het is wellicht niet zo snel als Quick Sort, maar wellicht heeft het andere voordelen.

[ Voor 194% gewijzigd door silentsnow op 19-03-2003 05:36 ]

[lordsnow]

Ik had hier een aantal maanden geleden een topic over.. ff de search gebruiken, kan je nalezen wat mensen allemaal aanrade toen

Ik denk dat Heap Sort voor jou mischien het beste is.

Heap Sort
The heap sort is the slowest of the O(n log n) sorting algorithms, but unlike the merge and quick sorts it doesn't require massive recursion or multiple arrays to work. This makes it the most attractive option for very large data sets of millions of items.

Ik heb nog wel wat links van paginas die ik toen opgezocht heb op de web:

1. overzicht pagina van verschillende Sorts

2. stap-voor-stap voorbeeld van Heap Sort

3. Erg goeie pagina met vergelijkingen van Sorts mbv applets

[Verwijderd]

Heap Sort lijkt mij inderdaad ook het beste (zowel quicksort en heapsort hebben een tijdscomplexiteit van n log (n) (= de ondergrens voor sorteren), maar quicksort is wel sneller omv. snellere voorfactoren).

Waarschijnlijk zul je het wel redden met de links van lordsnow, maar ooit heb ik heapsort aan een mede-student proberen uit te leggen tijdens een examen: http://www.clueless.be/Misc/HeapSort.cpp (disclaimer: je moet wel wat belgisch verstaan )

Heap Sort it is!

[RickN]

Check deze implementatie van quicksort maar eens uit.

Hier worden een aantal mooie optimalisaties op het standaard algoritme uitgevoerd, waaronder het zelf implementeren van de "recursie" met een eigen stack. Deze oplossing heeft dus bijna geen extern geheugen meer nodig en is daarnaast ook nog eens extreem snel.

Ik heb deze implementatie zelf ooit naar Delphi geport om de ins en outs goed te begrijpen, maar daar kan ik nu niet bij.

[ Voor 9% gewijzigd door RickN op 19-03-2003 09:22 ]

[MSalters]

Verwijderd schreef op 19 March 2003 @ 05:09:
Voor mijn werk ben ik aan het programmeren aan een indexeermethode voor een databasesysteem. Deze index maakt gebruik van R-Trees. Om efficient te kunnen zoeken pas ik het STR packing algoritme toe. STR packing voert op de data recursief een aantal sorteeroperaties uit voordat de gegevens in de R-Tree geplaatst worden.

Nu had ik hiervoor eerst quick sort gebruikt. Dit werkt extreem snel, maar is enorm recursief en voor grote hoeveelheden data raak ik over de beschikbare heap space heen en dat is niet echt de bedoeling. Een ander uiterste is het bubble sort algoritme wat wel goed werkt voor grote hoeveelheden data, maar enorm inefficient en supertraag is.

M.a.w. wat voor sorteeralgoritme zouden jullie toepassen voor een enorme hoeveelheid array-data?

En om het topic algemeen te houden, welk algoritme gebruik je in welke situatie?

Ik heb voor een grote sort ( miljoenen strings) gewoon gebruik gemaakt van de C++ std::sort, een introsort/quick sort variant. De consequentie was wel dat de machine 2 Gb geheugen nodig had. Das was evengoed goedkoper dan mijn tijd. Verder had ik mijn string class geoptimaliseerd voor deze sort, dus een snelle swap, small-string optimalisatie en een geoptimaliseerde heap manager.

[Stubby]

Heap sort is idd m.i. de beste oplossing, ik zag hier ook nog iemand mergesort opperen, dit is idd de snelste sort (tenminste, zoals ik ze toen heb gecode...) maar vergt wel O(2n) geheugen!

[alienfruit]

Waarschijnlijk offtopic; maar kijk eens naar de Opensource versie van TurboPower FlashFiler die is werkt prima en indexing is ook behoorlijk snel. Misshcien kun je daar ideen qua indexering vandaan halen ?

[SWfreak]

WinME schreef op 19 March 2003 @ 12:17:
Heap sort is idd m.i. de beste oplossing, ik zag hier ook nog iemand mergesort opperen, dit is idd de snelste sort (tenminste, zoals ik ze toen heb gecode...) maar vergt wel O(2n) geheugen!

Merge-sort kan ook in-place zoals op een van bovenstaande links wordt vertoond.

[Verwijderd]

Gewoon qsort + insertion sort. Je splits de data array op in meerdere stukken met behulp van qsort. Als het aantal items in de opgesplitste array kleiner is dan een bepaald getal(bijvoorbeeld 20) gebruik je insertion sort om de gesplitste array verder te sorteren.

in plaats van insertion sort kun je ook andere sort routines gebruiken.

[Sneak[3G]]

als je nou eens een hash gebruikt? is dat een optie? dit is het snelste van allemaal dacht ik

[ Voor 29% gewijzigd door Sneak[3G] op 19-03-2003 14:38 ]

[Soultaker]

SWfreak schreef op 19 March 2003 @ 12:22:
Merge-sort kan ook in-place zoals op een van bovenstaande links wordt vertoond.

Welke link bedoel je precies? Of zou je dit misschien toe kunnen lichten? Voor zover ik weet kan het namelijk niet; ik zou ook niet kunnen bedenken hoe.

[tomato]

Soultaker schreef op 19 March 2003 @ 17:03:
Welke link bedoel je precies? Of zou je dit misschien toe kunnen lichten? Voor zover ik weet kan het namelijk niet; ik zou ook niet kunnen bedenken hoe.

Dat kan zelfs vrij gemakkelijk en op meerdere manieren.

De twee partities van de lijst blijven in de lijst zelf staan (ze staan altijd na elkaar, bij de laatste merge zijn het de twee helften van de originele lijst). Bij het mergen van de twee (gesorteerde) partities ga je bijvoorbeeld de eerste van laag naar hoog af en kijk je of de laagste van de tweede partitie kleiner of gelijk is aan het huidige element. Als dat zo is komt die op de huidige positie en schuift de rest van de eerste partitie een stukje op en ga je verder. In het andere geval hoef je niets te doen en ga je ook verder.

Beetje gebrekkige uitleg misschien, maar er zijn vast zat voorbeelden te vinden

[RickN]

Soultaker schreef op 19 March 2003 @ 17:03:
[...]

Welke link bedoel je precies? Of zou je dit misschien toe kunnen lichten? Voor zover ik weet kan het namelijk niet; ik zou ook niet kunnen bedenken hoe.

Vergeetachtig

Soultaker schreef op 19 April 2002 @ 21:44:
[...]


Als ik me niet vergis, heeft mergesort in principe altijd O(N) extra geheugen nodig. Dat hoeft natuurlijk niet altijd een probleem te zijn, maar een efficient algoritme als mergesort is juist praktisch als je veel gegevens moet sorteren. Dan is het natuurlijk vervelend als je geheugengebruik ook verdubbelt. Daarbij kost het alloceren en initialiseren van veel geheugen natuurlijk ook tijd.

Zelf geef ik meestal de voorkeur aan heap sort, omdat dit algoritme een worst-case complexiteit van O(N*log(N)) (zoals van mergesort) combineert met een constant geheugengebruik (zoals quicksort). De verborgen constante van het algoritme is meestal echter wel een stuk groter dan in de implementaties van beide andere algoritmes.

RickN schreef op 20 April 2002 @ 00:49:
[...]


Je kunt bij mergesort nog onderscheid maken tussen external mergesort en in-place mergesort. in-place mergesort gebruikt geen extern array. Omdat het afwezig zijn van zo'n array uiteraard ten koste gaat van de efficientie kun je vraagtekens zetten bij het nut van zo'n implementatie.

Soultaker schreef op 20 April 2002 @ 12:45:
[...]


Hoe werk dat dan ongeveer? Ik heb er zelf wel eens mee zitten klooien en toen kwam ik er niet echt uit om op een handige manier te mergen zonder extra array. Uiteindelijk heb ik even in man sort gekeken en kwam ik tot de (misschien niet heel goed gefundeerde) conclusie dat 't schijnbaar niet anders kon.

Wat is de complexiteit van in-place mergesort in verschillende situaties? Als het ook om O(N^2) gaat, maar met een grotere constante, kun je natuurlijk (zoals je al zei) net zo goed quicksort gebruiken...

RickN schreef op 20 April 2002 @ 15:47:
[...]


Ik ben geen boek Maar kijk hier maar eens, staan een hele hoop voorbeelden van sorts, waaronder in-place mergesort. Google geeft ook heel veel pagina's.
[...]


Geen echt idee eigenlijk.

O, en ik heb het idee dat je een beetje negatief bent over quicksort. Je hebt wel gelijk dat quicksort in sommige gevallen heel traag is (vandaar ook O(N^2) worstcase), maar die gevallen zijn echt heel zeldzaam (B.v. een reeds gesorteerd array).

Soultaker schreef op 20 April 2002 @ 16:06:
[...]


Sorry, dat had ik zelf kunnen opzoeken natuurlijk.
[...]


Leuk die 'puzzelstukjes'...
[...]


Ik vind het gevoelsmatig een beetje vervelend dat je eigenlijk niet kan zeggen dat je code in elk geval efficient werkt. Ik ben me er echter van bewust dat quicksort in de meeste gevallen wel heel efficient werkt.

Zelfs situaties waarin de invoer al gesorteerd is, kunnen meestal wel efficient gesorteerd worden, als je je mediaan op een slimme manier kiest (bijvoorbeeld door de mediaan van het eerste, middelste en laatste element in je array).

Het fijne van de andere twee algoritmes die ik noemde, is dat je ZEKER weet dat een lijst in O(log(N)) gesorteerd wordt.

Dit alles uit dit topic

[ Voor 3% gewijzigd door RickN op 19-03-2003 18:09 ]

[Soultaker]

RickN schreef op 19 maart 2003 @ 18:06:
Vergeetachtig

Hmm, blijkbaar. Blijkbaar heb ik het belachelijke idee om een O(N^2) sorteeralgoritme te ontwerpen direct weer verworpen. Je kunt je ook afvragen of een in-place mergesort te vergelijk is met de "gewone" mergesort, die wel een fatsoenlijke tijdcomplexiteit kent (ondanks de lineaire ruimtecomplexiteit).