Sehr schnelle Sortierung

Wow, der Code ist echt Scheiße!

Bitte schau dir doch mal Sortieralgorithmen an, z. B. Quick Sort, das Internet ist voll mit Implementierungen davon, und wahrscheinlich enhält die C# Klassenbibliothek ausreichend gute Implementierungen davon.

Zitat von -Gaston-

Hallo,

ich bin gerade dabei ein Programm zu erstellen und beim Testen fand ich raus, dass die Sortierung sehr langsam ist. Zuerst verwendete ich ein Array. Da ich aber für das Sortieren jedesmal extra ein Array erstellen musste, hab ich nun folgende Lösung gemacht:

(Sprache: C#)

Code

private void Sort(int in1, int in2, int in3, int in4, int in5, out int out1, out int out2, out int out3, out int out4, out int out5) {
  out1 = in1;
  out2 = in2;
  out3 = in3;
  out4 = in4;
  out5 = in5;
 
  int tmp;
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
  }
  if (out3 > out4) {
    tmp = out3;
    out3 = out4;
    out4 = tmp;
  }
  if (out4 > out5) {
    tmp = out4;
    out4 = out5;
    out5 = tmp;
  }
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
  }
  if (out3 > out4) {
    tmp = out3;
    out3 = out4;
    out4 = tmp;
  }
  if (out1 > out2) {
    tmp = out1;
    out1 = out2;
    out2 = tmp;
  }
  if (out2 > out3) {
    tmp = out2;
    out2 = out3;
    out3 = tmp;
    if (out1 > out2) {
      tmp = out1;
      out1 = out2;
      out2 = tmp;
    }
  }
}

Alles anzeigen

Dies ist zwar um ein vielfaches schneller als die vorherigen Varianten, aber das ist trotzdem noch zu langsam
Für das Sortieren gehen jetzt noch ca. 25% der Zeit drauf.
Kennt jemand eine schnellere Methode?

Edit: Mir ist klar, das ganze ist schon recht schnell gelöst, da das ganze aber ein paar 1000 Milliarden Mal sortiert wird, geht das trotzdem in die Sekunden hinein ...

Alles anzeigen

Das ganze ist definitiv nicht schnell gelöst, weils einfach eine grausliche Implementierung eines Bubblesorts ist ;).... probiers mal mit einem Quicksort.
Frage: Was möchtest du damit 1000 Milliarden mal sortieren?

edit: schau mal hier: http://en.csharp-online.net/Quick_Sort

Wenn es wirklich _sehr_ schnell gehen muss zahlt sich die überlegung radixsort eventuell auch aus, aber bei 5 zahlen ist die überlegung unnötig

Thomas

[Blockierte Grafik: http://img5.imageshack.us/img5/7608/tdmq.jpg]

An dieser Stelle ein Hoch auf Algodat1

Mach dir das Leben einfach:

var list = new List<int>();
list.add(in1);
list.add(in2);
list.add(in3);
list.add(in4);
list.add(in5);
list.sort();

Fertig.....

Was mich immer nochninteressiert: Bei welcher Aufgabenstellung muss man 1000 Milliarden mal 5 Zahlen sortieren?

Ein paar Bemerkungen:
- Bubble-Sort ist nicht schnell, ja. Allerdings sollte man hier anmerken, dass hier in diesem Fall (sortieren von 5 Elementen) weder Quicksort, noch Radixsort irgendwelche Vorteile bringen. Die bringen erst Laufzeitvorteile bei (sehr) vielen Elementen. Das liegt daran, dass die O-Notation konstante Faktoren bzw. konstante Zeiten vernachlässigt, die bei den schnelleren Sortierverfahren bei großem n nicht mehr ins Gewicht fallen und daher nur dort verwendet werden. Bei etwa 10 Elementen oder weniger sind die Klassiker ähnlich gut oder oft sogar besser.
- Das Einfügen in eine int-Liste alleine ist wahrscheinlich schon langsamer als obiger Bubble-Sort. Vom Sortieren ganz zu schweigen. Sortieren per int-List wird daher wohl eher Laufzeitnachteile bringen.
- Die Idee des Vermeidens eines Arrays ist schon ganz gut (keine Indexberechnungen und keine Range-Checks). Die Anzahl der Vergleiche (10 Stück) ist bei 5 Elementen ja schon nicht sööo schlecht, die im Schnitt 10/2 Vertauschungen (= 15 Zuweisungen) plus 5 Zuweisungen von in nach out sind jedoch vermutlich etwas mehr als notwendig.
- Auch mich täte interessieren wo man 1000 Milliarden mal 5 Zahlen sortieren muss.
- 1000 Milliarden mal sortieren "geht in die Sekunden hinein"? Bei welchem Computer bitte? Bei einer Sortierung pro Nanosekunde (unrealistisch schnell) würde man schon eine Viertelstunde dafür brauchen. Oder reden wir hier von Großrechnern mit zig-tausenden parallel arbeitenden CPUs?

Meine Vorschläge zur Optimierung:
- Wenn sonst keinerlei Informationen über die Zahlen vorliegen: Ein klassisches Sortierverfahren (dann bleibt es einfach).
- Bubblesort ist eigentlich kein Klassiker, sondern lediglich ein intuitives Verfahren für Programmieranfänger. Besser man nimmt z.B. Insertionsort oder Selectionsort, bei ähnlich vielen Vergleichen, einige Zuweisungen weniger.
- Man könnte zusätzlich noch die Zuweisung von in nach out in eine Sortierrunde einweben. z.B. bei Selectionsort. Dann hätte man die 5 Zuweisungen nicht mehr extra.
- Eine Idee noch: Sortieren der ersten beiden Zahlen (1 Vergleich, 0 oder 3 Zuweisungen), sortieren der Zahlen 3 bis 5 (2-3 Vergleiche, 0-4 Zuweisungen) und dann ein Merge auf out (2-4 Vergleiche, 5 Zuweisungen). Ergäbe insgesamt 5-8 Vergleiche und 5-12 Zuweisungen. Allerdings ohne Schleifen/Arrays wären das viele Sonderfälle (also viele ifs) und etwas unübersichtlich.
- Eventuell noch inlining.

Zitat von freiBär

Was mich immer nochninteressiert: Bei welcher Aufgabenstellung muss man 1000 Milliarden mal 5 Zahlen sortieren?

Es klingt auf jeden Fall ziemlich wichtig. Sicher ein Hacker. :////

Ich glaube, gerade bei einer solchen Aufgabenstellung, kann man keine patentzepte geben, sondern muss sehr viel herumexperementieren und schauen, was wirklich funktioniert oder nicht:
1) Besteht die Möglichkeit, das ganze in Assembler runter zu coden? (also das du in C# Assembler einbindest). Ich glaube mal, dass das ganze nicht so leicht wäre, aber kenne mich da mit C# nicht so gut aus. (wird aber ähnlich wie Java sein). Und ob das wirklich starke Verbesserungen bringt ist fragwürdig, da die meisten Compiler schon Hardwarespezielle-Instructions benutzt, welche es doch vielleicht verschnellert.

2) Das du 10 Paramenter hast ist sicher nicht gut.
Wenn du eine Funktion aufrufst, musst du ja die Rücksprungadresse (bei x86 das Extend Instruction Register EIP) auf dem Stack abspeichern, weiters den Base Pointer (EBP) und dann noch jeden Übergabeparameter. Das heißt, jedes mal wenn du deine Funktion aufrufst, musst du zusätzlich mal 10 Elemente auf den stack schreiben. Wäre es da nicht vielleicht besser, das ganze per Referenz zu übergeben, damit nur ein Pointer übergeben wird?

3) Schau dir mal die Compiler-flags an. Beispielsweise bei gcc kannst du stack-smashing-protecion ausschalten (stack-smashing-protection ist z.b. dafür dar, dass wenn du einen Bufferoverflow im code hast, es dem Hacker erschwert wird, es auszunutzen). Dabei wird bei jedem Funktionsaufruf ein Cookie auf den Stack gelegt und bei jedem return danach dieses Stack-Cookie in einer eigenen Funktion überprüft. Keine Ahnung inwieweit C# mit solchen Mechanismen arbeitet (da es ja die Speicherverwaltung übernimmt), aber vielleicht kannst du da bei optimierungen noch was rausholen

4) Funktion inlinen, falls C# das anbietet.

5) Möglicherweise ist ein Dreiecksaustausch schneller als per temporärem Element. Weil wenn du temporäre Elemente hast (auch wenn es nur eines ist), musst du das ja 10000000000 mal erstellen, wenn du 10000000000 mal das aufrufst...... Und XOR (bzw. - und +) sind ja direkt Prozessor Instructions, vielleicht gehts schneller.... musst du Testen. Ansonsten könntest du versuchen, deine Temp Variable auf den Heap zu legen (also global zu definieren), weil dann müsstest du nur einmal Platz anschaffen und nicht jedes mal extra im Stack (obwohl denke ich der Stack schneller als der Heap ist.... also einfach mal austesten) (bzw. oder generell anstatt Übergabeparameter mal global Variablen testen...)

6) Zum Verfahren: Probier einfach mal ein paar durch. Insertionsort, Selectionsort, Bucketsort (falls möglich), Radixsort (falls möglich) und Bubblesort. Und dann siehst du es eh.

7) Warum machst du anfangs die ganzen zuweisungen? Warum arbeitest du nicht mit den in-Elementen weiter bis du sicher weißt, dass eine out-Zuweisung gemacht gehört? So sparst du zuweisungen und somit auch Zeit.

Zitat von Juggl3r

1) Besteht die Möglichkeit, das ganze in Assembler runter zu coden? (also das du in C# Assembler einbindest). Ich glaube mal, dass das ganze nicht so leicht wäre, aber kenne mich da mit C# nicht so gut aus.

wtf c# assembler?

Zitat von Juggl3r

2) Das du 10 Paramenter hast ist sicher nicht gut.
Wenn du eine Funktion aufrufst, musst du ja die Rücksprungadresse (bei x86 das Extend Instruction Register EIP) auf dem Stack abspeichern, weiters den Base Pointer (EBP) und dann noch jeden Übergabeparameter. Das heißt, jedes mal wenn du deine Funktion aufrufst, musst du zusätzlich mal 10 Elemente auf den stack schreiben. Wäre es da nicht vielleicht besser, das ganze per Referenz zu übergeben, damit nur ein Pointer übergeben wird?

hebt sich mit deinem punkt 4 auch wieder auf, dynamisches allokieren von speicher ist auch langsam, wieviel da die 4 überfälligen parameter beitragen bleibt offen

Zitat von Juggl3r

3) Keine Ahnung inwieweit C# mit solchen Mechanismen arbeitet (da es ja die Speicherverwaltung übernimmt), aber vielleicht kannst du da bei optimierungen noch was rausholen

c# ist hald immer noch managed... c++ wäre dafür wohl geeigneter

wenn der zahlenbereich bekannt ist könnt er auch einfach einen bucketsort nehmen und ein 2. array daneben haben welches die zuordnung, welche zahl war in welchem datensatz war, handhabt, speicher ade (wenn das ding dann dafür auch swappen muss könnte es passieren das der bubblesort schneller wäre)

Thomas