Dynamisches Array of Integer sortieren: welches Sortierverfahren???

[romber]

Hallo!

Ich habe da ein Array of Integer, das in der Regel nicht mehr als 20-25 Zahlen drin hat. Die Zahlenwete liegen immer zwischen 1 und 128.

Nun möchte ich die Zahlen in diesem Array sortieren. Da bin ich auf eine Reihe von Sortiertutorials (hier) von Daniel gestossen. Welche der dort präsentierten Methoden ist in meinem Fall wirklich die schnellste? Klar, bei derart kleinen Datenmengen wird der Unterschied kaum bemerkbar sein. Trodzdem gibt es immer eine Methode, die schneller ist.

Danke!

[himitsu]

Kommt es hier wirklich auf jede kleine Microsekunde an?
Wie oft wird denn sortiert?

Nja, ich würde einfach ein Bubble-Sort implementieren und fertig.
Schön einfach und bestimmt ausreichend.

Bei den paar "klitzekleinen" Integer könnte schon alleine das Selection-Sort langsamer oder zumindestens gleich schnell sein,
so daß sich der Aufand einfach nicht lohnt.

[jfheins]

Bucketsort sollte die Aufgabe recht zügig bewältigen ;)

Ansonsten: Diese Datenmenge ist ein Witz für jeden anständigen Algo. Alles außer Slowsort und Bogosort sollte den Job im Nu getan bekommen.

[Uwe Raabe]

Ich würde hier gar nichts implementieren sondern einfach folgendes aufrufen:

Delphi-Quellcode:

var
  MyArray: array of Integer;
...
  TArray.Sort<Integer>(MyArray);

Vorausgesetzt natürlich, man setzt keine veraltete Delphi-Version ein :wink: (Ich sehe gerade, daß dies der Fall ist)

Wenn's denn wirklich an der Performance drückt, kann man die Implementierung immer noch verbessern. Aber jede zusätzliche (und in diesem Fall völlig überflüssige) Implementierung ist eine zusätzliche Fehlerquelle.

[romber]

Vielen Dank für schnelle Raktionen!

Zitat:

Zitat von Uwe Raabe (Beitrag 1047653)

Ich würde hier gar nichts implementieren sondern einfach folgendes aufrufen:

Delphi-Quellcode:

  TArray.Sort<Integer>(MyArray);

Ob diese Methode auch die schnellste ist? Mir geht's wirklich um Performance. Ich erhalte über eine Schnittstelle sehr viele serialisierte Daten, die ich mittels Lookup-Funktionen in lesbare Form konvertieren muss. Manchmal sind es über 200 Datensätze pro Sekunde. Deswegen mache ich mir Sorgen um Performance.

Ich arbeite mittlerweise mit Delphi 2010, muss also klappen. Was muss ich für TArray in uses deklarieren?

[daywalker9]

Delphi-Quellcode:

uses Generics.Collections;

[Hawkeye219]

Hallo romber,

bei kleinen Zahlenmengen werden die herkömmlichen Sortierverfahren wahrscheinlich schnell genug sein. Der folgende Code beschreibt einen anderen Ansatz für nahezu beliebig große Zahlenmengen mit beschränktem Wertebereich:

Delphi-Quellcode:

procedure Sort (var A: array of Integer);
const
  MINVALUE = 1;
  MAXVALUE = 128;
  ERRVALUE = 255;
var
  i, j, k: Integer;
  Counter: array [MINVALUE..MAXVALUE] of Integer;
begin
  FillChar (Counter, SizeOf(Counter), 0);

  for i in A do
    if (i >= MINVALUE) and (i <= MAXVALUE) then
      Inc (Counter[i]);

  k := 0;
  for i := Low(Counter) to High(Counter) do
    for j := 1 to Counter[i] do
      begin
        A[k] := i;
        Inc (k);
      end;

  for j := k to High(A) do
    A[j] := ERRVALUE;
end;

Gruß Hawkeye

[rollstuhlfahrer]

also generell das allerschnellste Sortierverfahren, das es zur Zeit gibt und mir bekannt ist, ist QuickSort.
Delphi bringt auch Demos mit. Da ist eine Thread-Sortier-Demo dabei. Da könntest du mal schauen.
Da QuickSort rekursiv arbeitet, wird es etwas Performance schlucken. Wenn du den Stack nicht allzu stark belasten darfst, könnte MinSort (welches schneller ist als BubbleSort) auch zu gebrauchen sein.

Bernhard

EDIT: Noch was zur Performance:

Delphi-Quellcode:

Array of Byte

bei Zahlen unter 256 belegt 3 Byte weniger Speicherplatz pro Element

[Luckie]

Warum müssen die Daten in "Echtzeit" verarbeitet werden? Für so was eignet sich ein Threadpool, dann kann die Abarbeitung auch mal länger dauern, ohne dass du Probleme bekommst, wenn wieder Daten eintreffen.

[Uwe Raabe]

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1047684)

also generell das allerschnellste Sortierverfahren, das es zur Zeit gibt und mir bekannt ist, ist QuickSort.

TArray.Sort benutzt QuickSort.

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1047684)

Noch was zur Performance:

Delphi-Quellcode:

Array of Byte

bei Zahlen unter 256 belegt 3 Byte weniger Speicherplatz pro Element

Ist aber durch die 32-Bit Prozessor-Architektur langsamer im Zugriff als array of Integer.

[Aphton]

Zitat:

Zitat von rollstuhlfahrer (Beitrag 1047684)

also generell das allerschnellste Sortierverfahren, das es zur Zeit gibt und mir bekannt ist, ist QuickSort.
Delphi bringt auch Demos mit. Da ist eine Thread-Sortier-Demo dabei. Da könntest du mal schauen.
Da QuickSort rekursiv arbeitet, wird es etwas Performance schlucken. Wenn du den Stack nicht allzu stark belasten darfst, könnte MinSort (welches schneller ist als BubbleSort) auch zu gebrauchen sein.

Bernhard

EDIT: Noch was zur Performance:

Delphi-Quellcode:

Array of Byte

bei Zahlen unter 256 belegt 3 Byte weniger Speicherplatz pro Element

Häh :?
Was ist dann mit ShellSort? Ich dachte mir, dass ShellSort die schnellste Methode zum Sortieren ist! Ist sie dir bekannt?

MfG

[Satty67]

Also meines Wissens ist ShellSort deutlich langsamer als QuickSort.

Bei langsamen Zugriff auf die Elemente (z.B. direktes sortieren einer Datei) ist MergeSort oder InsertionQuickSort besser.

Noch einen Hauch besser als QuickSort soll RadixSort sein (das ich aber nie verstanden habe). Ich glaube Alzaimar hat sowas mit der SkipList umgesetzt (habe ich aber auch nie ganz verstanden).


PS: Anlage ein altes Vergleichsprogramm, nicht schön aber war mir ganz hilfreich...

PPS: Wo das alte Programm so schön ins Clipboard kopiert:

3692 ms für 10000 String-Elemente mit Bubble-Sort
1086 ms für 10000 String-Elemente mit Selection-Sort
947 ms für 10000 String-Elemente mit Insertion-Sort
16 ms für 10000 String-Elemente mit Intro-Sort
11 ms für 10000 String-Elemente mit ShellSort
5 ms für 10000 String-Elemente mit Quick-Sort (rekursiv, kompakt)

[Medium]

Dat Dingen ist, dass QuickSort im ganz allgemeinen Fall zu den schnellsten gehört, bzw. im Mittel die untere Grenze darstellt. Sobald man aber im Vorfeld Annahmen treffen kann, sind andere Verfahren ggf. im Vorteil. Dabei wäre zu beachten: Ungefähre Verteilung der Sortierkriterien im Array, Art und Stärken/Schwächen der Speicherung, Anzahl der Elemente, möglicherweise (Teil-)Vorsortierte Bereiche, etc. pp.
Es gibt für viele Spezialfälle in denen Annahmen zutreffen Verfahren, die Quicksort alt aussehen lassen, im komplett "ungewissen" Fall ist es im Mittel aber nach wie vor eine prima Sache. So lange du also keine konkreteren Eingrenzungen machen kannst, ist das bereits in Delphi implementierte Sortieren schon ziemlich gut.

[MStoll]

Hi,

wie Medium gesagt hat: es kommt auf Annahmen an, die du zu deinen Daten treffen kannst. QuickSort gilt allgemeinhin als das schnellste, vergleichsbasierte (!) (Einzel-)Verfahren mit einer Laufzeitkomplexität von O(nlogn). Wenn du einen diskreten Wertebereich hast (z.B. Ganzzahlen in festen Grenzen), dann kannst du andere, nicht vergleichsbasierte Verfahren verwenden, die dann in linearer Zeit arbeiten.

Einen Ansatz QuickSort zu verbessern, ist, bei der Rekursion und kleinen Teilmengen der Daten auf ein anderes, "einfacheres" Verfahren zu wechseln, da ein solches oft bei kleinen Datenmengen effizienter ist. In vielen Texten über Algorithmen wird Insertion-Sort vorgeschlagen, mein persönlicher Favorit in diesem Fall ist ShellSort. Dazu könnte man noch Heapsort oder MergeSort als Fallback für den Worst-Case von QuickSort, nämlich O(n^2), implementieren, aber das geht jetzt wohl zu weit von deinem Problem weg.

In deinem Fall, da die Werte zwischen 1 und 128 liegen, solltest du dir Radixsort oder Abwandlungen davon anschauen und einfach mal exemplarisch bestimmen, ob das oder ein vergleichsbasiertes Verfahren schneller ist. Denn bei solch kleinen Datenmengen sagt die asymptotische Laufzeitkomplexität nur wenig über die tatsächlichen Geschwindigkeitsunterschiede aus.

Gruß
Michael

[Satty67]

Zitat:

Zitat von romber (Beitrag 1047637)

Ich habe da ein Array of Integer, das in der Regel nicht mehr als 20-25 Zahlen drin hat. Die Zahlenwete liegen immer zwischen 1 und 128.

Eine Möglichkeit wäre ein Array[1..128] of Integer mit 0 initialisiert.

Beim sammeln der Werte entsprechendes Array-Element incrementieren, also bei 64 einfach Array[64] +1.

Ob hinterher das Durchlaufen des 128 Elemente großen Arrays langsamer ist, als 25 Zahlen in einem 25 Elemente großen Array zu sortieren, müsste man testen.

[Medium]

Also quasi ein Histogramm! Schöne Idee, gerade bei so wenigen möglichen Zuständen verbrät man ja kaum Speicher dadurch! :thumb: Ich kann mir zumindest gut vorstellen, dass das trotz 128 Elemente ablatschen schneller kommt.

[Amateurprofi]

Zitat:

Zitat von Satty67 (Beitrag 1047699)

Also meines Wissens ist ShellSort deutlich langsamer als QuickSort.

Bei langsamen Zugriff auf die Elemente (z.B. direktes sortieren einer Datei) ist MergeSort oder InsertionQuickSort besser.

Noch einen Hauch besser als QuickSort soll RadixSort sein (das ich aber nie verstanden habe). Ich glaube Alzaimar hat sowas mit der SkipList umgesetzt (habe ich aber auch nie ganz verstanden).


PS: Anlage ein altes Vergleichsprogramm, nicht schön aber war mir ganz hilfreich...

PPS: Wo das alte Programm so schön ins Clipboard kopiert:

3692 ms für 10000 String-Elemente mit Bubble-Sort
1086 ms für 10000 String-Elemente mit Selection-Sort
947 ms für 10000 String-Elemente mit Insertion-Sort
16 ms für 10000 String-Elemente mit Intro-Sort
11 ms für 10000 String-Elemente mit ShellSort
5 ms für 10000 String-Elemente mit Quick-Sort (rekursiv, kompakt)

Ja, bei 10000 String-Elementen dürfte Quick-Sort das, mit Abstand, schnellste Verfahren sein.

Aber romber fragte nicht nach einem Algo für 10000 Elemente sondern für 20 bis 25 und er will auch nicht Strings sortieren sondern Integer-Werte.
Und da sieht Quicksort nicht mehr so deutlich besser sondern gelegentlich deutlich schlechter, als zum Beispiel Bubblesort (hängt davon ab, wie die Daten bisher sortiert sind).
Wie himitsu schon andeutete : Ein simples Bubblesort dürfte am sinnvollsten sein.

[alzaimar]

Zitat:

Zitat von Hawkeye219 (Beitrag 1047683)

Der folgende Code beschreibt einen anderen Ansatz für nahezu beliebig große Zahlenmengen mit beschränktem Wertebereich:...

Zitat:

Zitat von Satty67 (Beitrag 1047703)

..
Eine Möglichkeit wäre ein Array[1..128] of Integer mit 0 initialisiert.
...
Beim sammeln der Werte entsprechendes Array-Element incrementieren, also bei 64 einfach Array[64] +1.

Genau so funktioniert der Code von Hawkeye219.

[Satty67]

Ups, da hatte ich den Code zwar gesehen, aber wie immer nicht nicht erkannt wie er arbeitet.

Sorry.

[alzaimar]

Zitat:

Zitat von Satty67 (Beitrag 1047720)

Ups, da hatte ich den Code zwar gesehen, aber wie immer nicht nicht erkannt wie er arbeitet.

Ich auch nicht, bis Du es erklärt hast.:stupid: