Sortieren mit minimaler Vergleichsanzahl

Flamefire · Verfasst: Di 26.10.10 18:12

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?

F34r0fTh3D4rk · Verfasst: Di 26.10.10 18:23

Kannst du näheres über die Beschaffenheit der Objekte verraten? Warum ist die Compare()-Methode so teuer?

Gausi · Verfasst: 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:

_________________
We are, we were and will not be.

F34r0fTh3D4rk · Verfasst: 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.

Martok · Verfasst: Di 26.10.10 18:36

Klingt für mich auch nach Insertionsort: nur beim Einfügen/Ändern kontrollieren wohin damit, ansonsten gar nichts weiter tun.

_________________
"The phoenix's price isn't inevitable. It's not part of some deep balance built into the universe. It's just the parts of the game where you haven't figured out yet how to cheat."

Flamefire · Verfasst: Di 26.10.10 19:01

Wird vermutlich wirklich Insertionsort.
Ok danke.

Geändert werden immer erst ALLE Elemente und dann wird sortiert.
Die CompareMethode vergleicht intern einige weitere Daten, darum ist die recht teuer.

F34r0fTh3D4rk · Verfasst: Di 26.10.10 19:13

Wenn sich jedes mal alle Elemente ändern, solltest du dir vielleicht doch mal Quicksort (oder Insertionsort in Kombination mit Binärsuche) angucken, um die Anzahl der Vergleiche zu reduzieren. Eventuell lohnt sich auch eine Fallunterscheidung, da wenn du wirklich sehr häufig nur drei Elemente sortieren musst, ein "direktes" Sortieren am schnellsten ist.

Kha · Verfasst: Di 26.10.10 19:22

Für optimales Sortieren von Daten einer festen Länge lautet das Stichwort 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 · Verfasst: Di 26.10.10 19:27

Das ist etwa das was ich mit "direktem" Sortieren meinte. Sieht nur als Code net so schön aus

Flamefire · Verfasst: Di 26.10.10 19:36

Nur habe ich keine feste Länge...
Es gibt min. 2 und max. 7 Objekte. Und für jede Anzahl nen eigenen Algo?
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.

F34r0fTh3D4rk · Verfasst: 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)

markieren

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 · Verfasst: Di 26.10.10 19:50

Jein...
Hab ein 1D Array und dann ein record als Eintrag: Objekt und ein Flag, ob es gleich dem darüber ist.

FinnO · Verfasst: Di 26.10.10 20:22

Moin,

kannst du vielleicht aus den Eigenschaften des Objekts eine "Punktzahl" errechnen? Die könnte man dann ja recht flott vergleichen..

LG

Flamefire · Verfasst: 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 · Verfasst: 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.

_________________
>λ=

Dude566 · Verfasst: Di 26.10.10 21:35

Wie oft sollen denn die Objekte neu sortiert werden, denn bei maximal 7 Objekten kann ich mir nicht vorstellen, dass es einen solchen Zeitaufwand kostet und man extra optimieren muss?

_________________
Es gibt 10 Gruppen von Menschen: diejenigen, die das Binärsystem verstehen, und die anderen.

Flamefire · Verfasst: 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:

markieren

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?

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme