Entwickler-Ecke :: Thema anzeigen - Sortieren mit minimaler Vergleichsanzahl

Flamefire - Di 26.10.10 18:12
Titel: Sortieren mit minimaler Vergleichsanzahl

Ich möchte Objekte sortieren, deren Compare() Routine recht teuer ist.
Darum soll es demzufolge eine Sortiermethode sein, die mit so wenig wie möglich vergleichen auskommt und sonst auch möglichst schnell ist.
Die Anzahl der Elemente ist zwischen 2-6 typischerweise aber 3.
Die Sortierung wird jedoch extrem oft gemacht, da sich ALLE Objekt häufig ändern und danach sortiert werden müssen (dazwischen umsortieren ist nicht möglich)

Welche Variante kann ich nehmen?

Gausi - Di 26.10.10 18:23

Bei drei Elementen ist das komplett wurscht, man braucht auf jeden Fall drei Vergleiche. Da kann man auch "Selectionsort" nehmen: Zuerst das Minimum suchen (2 Vergleiche), dann die beiden übrigen. Bei den anderen (4-6 Elemente) würde ich es mal mit Shakersort probieren, also ein Bubblesort der nicht immer in eine Richtung bubbelt, sondern abwechselnd von vorne nach hinten und zurück.

Ansonsten würde ich da einfach mal experimentieren, ob sich Quicksort, Mergesort oder Heapsort lohnt. :nixweiss:

F34r0fTh3D4rk - Di 26.10.10 18:27

Naja, wenn er sehr häufig sortiert und sich ein Element ändern, kann man davon ausgehen, dass die anderen Elemente bereits sortiert sind. Das heißt für den ersten Sortiervorgang braucht man eine gewisse Anzahl Vergleiche, danach gibt es Potenzial für Optimierungen. Bei drei Elementen wären das dann zum Beispiel ein Vergleich im Best- und zwei Vergleiche im Worstcase.

Kha - Di 26.10.10 19:22

Für optimales Sortieren von Daten einer festen Länge lautet das Stichwort Sorting Network [http://en.wikipedia.org/wiki/Sorting_network]:

Zitat:

For 1 to 8 inputs optimal sorting networks are known. They have respectively 0, 1, 3, 5, 9, 12, 16 and 19 comparators (Knuth, 1997). The optimal depths for up to 10 inputs are known and they are respectively 0, 1, 3, 3, 5, 5, 6, 6, 7, 7.

Da bist du ja gerade noch im Intervall ;) .

F34r0fTh3D4rk - Di 26.10.10 19:43

Flamefire hat folgendes geschrieben :

Nur habe ich keine feste Länge...
Es gibt min. 2 und max. 7 Objekte. Und für jede Anzahl nen eigenen Algo?

Prinzipiell: ja (oder zumindest bis zu einem bestimmten n und ab da dann einen bestimmten Algo benutzen)

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

if (n = 2) then
begin
  c := values[0].compareto(values[1]);
  if (c < 0) then
  begin
    result[0].add(values[0]);
    result[1].add(values[1]);
  end else if (c = 0) then
  begin
    result[0].add(values[0]);
    result[0].add(values[1]);
  end else 
  begin
    result[0].add(values[1]);
    result[1].add(values[0]);
  end;
end else if (n = 3) then
begin
//...
end else 
begin
  quicksort(values);
end;

Zitat:

Achso noch schlimmer: Ich muss auch gleiche Werte erkennen können...
Es geht um eine Platzierung. Und da kanns halt sein, dass 2 den 2. Platz haben.

Wie speicherst du denn die Ergebnismenge? Zweidimensionale Liste? Wird dann allerdings etwas komplizierter was das direkte Sortieren angeht.

Flamefire - Di 26.10.10 20:29

Hab ich auch schon überlegt. Und mir fällt gerade was sehr gutes dazu ein :)
Ein paar Bits schubsen und schon hab ich ne checksumme, die ich vergleichen kann :)

Obwohl...Bringt zwar im Fall größerer Mengen etwas, aber im Normalfall dürfte das langsamer sein...
Weil die Compare Methode ist so optimiert, dass nur verglichen wird, was nötig ist (early-out)
Bei ner Checksumm müsste ich trotzdem über alles drüber, dann noch einige Umwandlungen, Shifts und OR-Verknüpfungen...
Kommt auf nen Test an...

Kha - Di 26.10.10 20:35

Flamefire hat folgendes geschrieben :

Achso noch schlimmer: Ich muss auch gleiche Werte erkennen können...

Das sollte in jeden Algorithmus, auch in ein optimales Searching Network, ohne Mehraufwand einbaubar sein, indem du die Vergleichsergebnisse mitspeicherst und daraus ganz am Ende Gleichplatzierungen ableitest. Denn bei jedem vergleichsbasierten Algorithmus müssen ja Elementpaare, die am Schluss nebeneinander liegen, einmal verglichen worden sein.

Flamefire - Di 26.10.10 21:54

Je Durchlauf so ca. 1-2 Mio mal...
Darum habe ich jeden Einzelschritt so weit wie möglich optimiert ohne das OOP ganz zu verhaun...

Variante jetzt sieht so aus:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:

    SetLength(places,plct);
    with places[0] do begin
      Object:=FMyObject[0];
      index:=0;
      EqualToBelow:=false;
    end;
    for i := 1 to plct - 1 do begin
      inserted:=false;
      j:=0;
      while(j<i) do begin
        win:=places[j].Object.Compare(FMyObject[i]);
        if(win<0) then begin
          Move(places[j],places[j+1],sizeOf(places[0])*(i-j));
          with places[j] do begin
            Object:=FMyObject[i];
            index:=i;
            places[j].EqualToBelow:=false;
          end;
          inserted:=true;
          break;
        end else if(win=0) then begin
          ct:=i-j-1;
          if(ct>0) then Move(places[j+1],places[j+2],sizeOf(places[0])*ct);
          with places[j+1] do begin
            Object:=FMyObject[i];
            index:=i;
            EqualToBelow:=places[j].EqualToBelow;
          end;
          places[j].EqualToBelow:=true;
          inserted:=true;
          break;
        end else while(j<i) and (places[j].EqualToBelow) do Inc(j);
        Inc(j);
      end;
      if(not inserted) then begin
        with places[i] do begin
          Object:=FMyObject[i];
          index:=i;
          EqualToBelow:=false;
        end;
      end;
    end;
    ct:=0;
    for i := 0 to Length(places) - 1 do begin
      Inc(FScores[places[i].index*plct+ct]);
      if(not places[i].EqualToBelow) then Inc(ct);
    end;
    SetLength(places,0);

Wie kann ich das noch weiter optimieren?

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!