Welke sort is het snelst? (sorteren News Subject: lijnen)

[lordsnow]

Ik heb al gezocht op het net, en er zijn een hele verzameling aan "sorts", alleen geen echte onderlinge vergelijkingen van deze. En ik neem aan dat de snelheid van een sort ook afhankelijk is van datgene wat gesorteerd moet zorden...

Ik was dus op zoek naar wat ideeen, suggesties, opninies.. whatever.


Ik prog in Delphi, maar source in een andere taal is geen probleem als voorbeeld. Wat ik probeer te maken is een mp3 download progsel - dus een progsel voor ALLEEN de mp3 nieuwsgroepen.

Op een gegeven moment krijg je dus een berg aan info binnen betreffende de articles in een newsgroup (article #, subject, author, date, message-id, references, byte count, line count, en Xref). Wat is volgens jullie de beste manier om dit te sorteren?

Mijn eerste idee was een soort "verdeel en heers" gebruiken: de Subject eerst sorteren op de eerste letter, en dan de afzonderlijke sets sorteren.

Mijn tweede idee was alles sorteren op datum, en dan beginnen met de eerste subject waarna alle bijpassende subjects uit de lijst gehaald wordt.

Andere ideeen zijn welkom. Opmerkingen over ervaring met sorts ook

[SchizoDuckie]

Volgens mij was een bubble sort het snelste (wat ik tenminste gezien heb aan benchmarks)

Hoe het werkt en wat het is weet deze link vast wel

[edit]

Bubble Sort
This is probably the simplest way sort an array of objects. Unfortunately it is also the slowest way!

oops ik hou mn mond wel verder

[BasieP]

ik heb gehoord dat er (al een tijdje terug) iemand een een of andere grote prijs heeft kregen voor het maken van een quicksort.
ik heb zelf ook gezocht naar die code, maar kon hem niet zo 1-2-3 vinden

[SchizoDuckie]

http://www.torry.net/sorters.htm

[BasieP]

code:

void quickSort(int numbers[], int array_size)
{
  q_sort(numbers, 0, array_size - 1);
}


void q_sort(int numbers[], int left, int right)
{
  int pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort(numbers, left, pivot-1);
  if (right > pivot)
    q_sort(numbers, pivot+1, right);
}

[Verwijderd]

Bubble sort de rapste?

Dat is een N^2 algoritme (algo wiens looptijd kwadratisch groeit met toename van de invoer). Lijkt me stug dus.

Ga voor QuickSort. Dat is een N log N algoritme. Een N log N curve loopt heel wat minder stijl dan een N^2 algoritme.

Naast QuickSort is er ook nog MergeSort. Ook een N log N algoritme. Ik weet alleen niet welke van de twee het snelst is.

[RickN]

veel sorteer algoritmes

Bubble sort de rapste?

Dat is een N^2 algoritme (algo wiens looptijd kwadratisch groeit met toename van de invoer). Lijkt me stug dus.

Ga voor QuickSort. Dat is een N log N algoritme.

Nope, quicksort is ook N^2 Maar, in de praktijk is het vaak wel het snelste sorteer algoritme.

[lordsnow]

BubbleSort en QuickSort spelen eigenlijk al een paar jaar niet echt meer mee. Tenminste, van wat ik begrepen heb van de verschillende websites die ik de afgelopen week bezocht heb.

Wat nu "in" is, is Radix sort (wat volgens mij ongeveer zoiets is als mijn "verdeel en heers" idee?), of anders gaan werken met B-Tree's of hashes.

[Verwijderd]

En er is best een vergelijking te vinden. Zie bijvoorbeeld:

http://www.cit.gu.edu.au/...ets/Sorting/example3.html

Wat wil je nog meer?

[edit]

Ik zie dat MergeSort de hele tijd net ietsjes rapper is dan QuickSort.

Ga dus toch maar voor MergeSort.

[Verwijderd]

RickN schreef op 14 november 2002 @ 14:05:
veel sorteer algoritmes


[...]


Nope, quicksort is ook N^2 Maar, in de praktijk is het vaak wel het snelste sorteer algoritme.

QuickSort is echt N log N, geloof me. (wel goeie pivot kiezen uiteraard!)

En in de praktijk is MergeSort sneller. Zie link in mijn vorige post.

[lordsnow]

BassieP: dat is die code waar je het over had? Die een prijs heeft gewonnen?

Voor de geintreseerde (en nieuwsgierige), hier een pagina met wat Java die verschillende sorts in werking laten zien: http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html

(ik zie nu dat dat dezelfde link is die RickN net gepost heeft.. oops)


btw, bedankt voor de links en snelle reacties mensen! Prachtig

[RickN]

Verwijderd schreef op 14 November 2002 @ 14:12:
[...]


QuickSort is echt N log N, geloof me. (wel goeie pivot kiezen uiteraard!)

En in de praktijk is MergeSort sneller. Zie link in mijn vorige post.

Quicksort is echt N^2, geloof me (en dat heeft niks met de pivot te maken).

En in de praktijk is quicksort sneller dan het N log N algoritme Mergesort.

edit:
Ach, laat ik het misverstand uit de wereld helpen. Quicksort is worstcase N^2 en average case N log N. Mergesort is voor beide N log N. In de praktijk en voor willekeurige, lange lijsten is een goede implementatie van quicksort het snelste.

[Verwijderd]

[b]RickN schreef op 14 november 2002 @ 14:14
[...]

Quicksort is echt N^2, geloof me.

Er bestaan manieren om in N tijd geschikte pivots te kiezen. Daarnaast kun je vooraf aan het sorteren je data randomizeren (ook al in N tijd), zodat niet alleen de expected tijd van QuickSort N log N is, maar ook de worst case tijd.

En in de praktijk is quicksort sneller dan het N log N algoritme Mergesort.

Mwoah. Laat QuickSort en MergeSort maar eens lopen naast elkaar op dat linkje uit m'n eerdere post.


[edit]
_{Ja, laat ik ook eens een misverstandje uit de wereld helpen!}

[RickN]

Randomizeren werkt aardig, maar het enige wat het doet is de kans dat je pech hebt met sorteren en het dus N^2 kost klein maken. Aan de echte worstcase complexiteit doe je niks.

En over de snelheid, ik vind die appletjes niet zo'n goede indicatie hoor, maar als we daar dan toch mee beginnen, vergelijk op de pagina die ik heb gelinkt double storage mergesort (is standaard mergesort) maar eens met fast quicksort

[Verwijderd]

RickN schreef op 14 November 2002 @ 14:22:
Randomizeren werkt aardig, maar het enige wat het doet is de kans dat je pech hebt met sorteren en het dus N^2 kost klein maken. Aan de echte worstcase complexiteit doe je niks.

Jawel. Met het randomizeren kan je kijken of je de boel wel echt door elkaar husselt zodat je niet met gesorteerde delen blijft zitten.

Dit alles in O(N) tijd.


En nu ga ik toch echt even Doom3 spelen.

[lordsnow]

Vergeet niet dat waar mijn data uit bestaat: een mp3 wordt gepost in 'stukjes' (articles) die weer aan elkaar geplakt moeten worden. De subject van elk van die stukjes als zijn hetzelfde, behalve natuurlijk het [nn/NN] gedeelte. Als er een mp3 CD wordt gepost dan zijn de subject van alle posts ook nog 's grotendeels hetzelfde.

Ik zocht dus iets wat voordeel heeft van het feit van wat ik wil sorteren een grote samenhang heeft.

[Verwijderd]

lordsnow schreef op 14 november 2002 @ 14:24:
Vergeet niet dat waar mijn data uit bestaat: een mp3 wordt gepost in 'stukjes' (articles) die weer aan elkaar geplakt moeten worden. De subject van elk van die stukjes als zijn hetzelfde, behalve natuurlijk het [nn/NN] gedeelte. Als er een mp3 CD wordt gepost dan zijn de subject van alle posts ook nog 's grotendeels hetzelfde.

Ik zocht dus iets wat voordeel heeft van het feit van wat ik wil sorteren een grote samenhang heeft.

Als je toch in Delphi werkt:

Terwijl je je subjects inleest, ze in een sorted stringlist stoppen. Dan worden ze direct gesorteerd, terwijl de zoekfunctie die een nieuwe string in de list plaatst uit een binary search algoritme bestaat.

[RickN]

Verwijderd schreef op 14 november 2002 @ 14:23:
[...]


Jawel. Met het randomizeren kan je kijken of je de boel wel echt door elkaar husselt zodat je niet met gesorteerde delen blijft zitten.

Dit alles in O(N) tijd.


En nu ga ik toch echt even Doom3 spelen.

Je hebt ongelijk. Je gebruikt quicksort, dus ontkom je niet aan een O(N^2) worstcase. Als je gaat kijken of je de boel wel goed door elkaar schud duurt jouw randomizatie al langer dan het sorteren.

Overigens hoop ik wel dat jij je pivot kiest in constante tijd, want als je daar O(N) voor nodig hebt wordt het helemaal zo traag als dikke stront door een trechter....

[Soultaker]

Ik wil hier eigenlijk twee dingen over kwijt.

Ten eerste, als je invoer al redelijk goed gesorteerd is, werkt de standaardversie van QuickSort slecht. Je moet dan handigheidjes bedenken om de worst-case complexiteit te vermeden.

Ten tweede vind ik het vreemd dat het heap sort algoritme nog niet genoemd is: dit is een robuust algoritme dat een worst-case complexiteit heeft van O(N*log(N)) (zoals het hoort), maar met een relatief hoge 'constante factor'. Het algoritme heeft in deze context echter een belangrijke eigenschap en dat is dat voor het sorteren niet alle elementen beschikbaar hoeven te zijn. Je voegt ze immers toe aan een binaire boom terwijl je ze binnen krijgt!

Bij dit probleem lijkt me een heap sort dan ook gepast, omdat je elke keer 1 headline kan inlezen, deze kan toevoegen aan je heap, en dan de volgende headline uitlezen. Dit heeft als voordeel dat de tijd waarin je normaliter op je gegevens (uit een TCP socket waarschijnlijk) zit te wachten, nu gebruikt kan worden om te sorteren, waardoor de overhead van het sorteren praktisch nihil wordt. Ook is het redelijk eenvoudig om de heap op schrijf op te slaan en er later (als het programma opnieuw wordt opgestart en er nieuwe headlines beschikbaar zijn) items aan toe te voegen! Dit is met (bijvoorbeeld) quicksort niet mogelijk; dan moeten alle items bij elkaar genomen worden en opnieuw gesorteerd.

Met mergesort zijn vergelijkbare constructies mogelijk, overigens.

[RickN]

lordsnow schreef op 14 November 2002 @ 14:24:
Vergeet niet dat waar mijn data uit bestaat: een mp3 wordt gepost in 'stukjes' (articles) die weer aan elkaar geplakt moeten worden. De subject van elk van die stukjes als zijn hetzelfde, behalve natuurlijk het [nn/NN] gedeelte. Als er een mp3 CD wordt gepost dan zijn de subject van alle posts ook nog 's grotendeels hetzelfde.

Ik zocht dus iets wat voordeel heeft van het feit van wat ik wil sorteren een grote samenhang heeft.

Als je op subject gaat sorteren en dus met vrij lange strings te maken kunt hebben zou ik iig geen radixsort nemen omdat die over elke character in je string itereert. Aan de andere kant, het sorteren van een array met enkele tienduizende elementen is met elk average case N log N algortime (quicksort, mergesort, heapsort) in een flits gebeurt, dus ik zou gewoon de eenvoudigste nemen en dat is denk ik mergesort.

edit:
Soultaker: goed punt over incremental heapsort

^O^

[Verwijderd]

Beste sort hangt af van wat/hoe je wilt sorten, hoeveel er gesort moet worden en hoe de te sorten data al is georganiseerd...

Data die al *bijna* gesorteerd is is wat anders dan totally random data.

Radixsort is fijn voor getallen, maar als je strings wilt sorteren schiet je er niet zo veel mee op.

[lordsnow]

Het spul is niet *echt* gesorteerd.. het is meer zo dat subject: lijnen die bij elkaar horen maar in een deel van de lijst voorkomen. Oftewel, alles wat bij elkaar hoort zit redelijk dicht bij elkaar, en niet verspreid over de hele lijst.

Soultaker: heap sort en merge sort zal ik 's nakijken dan ik neem aan dat het ook redelijk makkelijk is om (oude of gedownloade) items te verwijderen?

RickN: met pics nieuwsgroupen praten we over een paar honderd posts op een dag, met mp3's enkele (tien) duizenden, en multimedia en warez nieuwsgroupen tot een milioen of zo.

Led: precies - daarom gaf ik in m'n eerste post al aan waar m'n data uit bestaat. ok, radix sort is dus geschrapt.

Blijft over: quicksort (toch nog), mergesort, en heapsort.

[Soultaker]

lordsnow schreef op 14 november 2002 @ 17:06:
Soultaker: heap sort en merge sort zal ik 's nakijken dan ik neem aan dat het ook redelijk makkelijk is om (oude of gedownloade) items te verwijderen?

Het is makkelijk om items in sorteervolgorde te verwijderen; hoe goed je ze er 'halverwege' tussen uit kunt halen zonder de heap te moeten reconstrueren weet ik eigenlijk niet.

[lordsnow]

Hmm.. nieuwsgroepen zijn wel dynamisch... oude posts vervallen, en moeten dus verwijderd worden. Gedownloade posts kunnen ook verwijderd worden. Niet alles wat gesorteerd is zal worden gedownload.. etc etc.

Mischien is een "platte" sort toch handiger. Quicksort en Mergesort zijn sneller en 'plat', maar gebruiken twee keer zoveel geheugen... en dat laatste is niet zo leuk met 1000000 headers (niet alleen de Subject: lijn dus).

[esf]

lordsnow schreef op 14 november 2002 @ 21:13:
Mischien is een "platte" sort toch handiger. Quicksort en Mergesort zijn sneller en 'plat', maar gebruiken twee keer zoveel geheugen... en dat laatste is niet zo leuk met 1000000 headers (niet alleen de Subject: lijn dus).

Het efficientste lijkt me om alles in een binary tree te zetten, bijvoorbeeld in een red-black tree, maar de implementatie hiervan is vrij ingewikkeld.
Maar als je heel veel headers hebt zou ik juist een algoritme als Quicksort of Mergesort gebruiken, omdat het verschil in snelheid tussen n log n en n^2 bij grote hoeveelheden gegevens erg groot is.
Radixsort maakt volgens mij gebruik van een hash-tabel en dat is helemaal inefficient qua ruimtecomplexiteit.

[Janoz]

esf schreef op 14 november 2002 @ 21:29:
[...]


Het efficientste lijkt me om alles in een binary tree te zetten, bijvoorbeeld in een red-black tree, maar de implementatie hiervan is vrij ingewikkeld.
Maar als je heel veel headers hebt zou ik juist een algoritme als Quicksort of Mergesort gebruiken, omdat het verschil in snelheid tussen n log n en n^2 bij grote hoeveelheden gegevens erg groot is.
Radixsort maakt volgens mij gebruik van een hash-tabel en dat is helemaal inefficient qua ruimtecomplexiteit.

Ikzelf zat eigenlijk ook gelijk aan een rb tree te denken . Voordeel hiervan is dat alle operaties daarop O(log N) zijn. Een normale binaire boom kan scheef gaan groeien waardoor je effectief gewoon een linked list overhoud. een RB tree garandeerd door enkele kleine truukjes (rotate left & rotate right) dat het langste pad nooit langer is dan 2x de lengte van het kortste pad. Voor de rest werkt een RB tree hetzelfde als een binaire boom. Ik heb het algoritme nog wel ergens liggen (op papier), maar ik denk dat mijn pascal implementatie verloren is gegaan toen ik mijn acount opgeschoond heb.

[Soultaker]

Een heap kan je ook prima 'plat' representeren; het is immers een gebalanceerde binaire boom, die van links naar rechts gevuld wordt. Daarbij gebruikt alleen merge sort extra geheugen; zowel quick sort als heap sort gebruiken een constante hoeveelheid geheugen.

Nu ik er over nadenk, is het ook geen probleem om elementen uit een heap te verwijderen; dat kan ook in O(log(N)) tijd.

[lordsnow]

--sorry.. onzin reactie van mijn kant ff verwijderd--