Entwickler-Ecke

Algorithmen, Optimierung und Assembler - Allgemeines Sortieren nach 2 Kriterien


Gausi - So 23.07.06 10:37
Titel: Allgemeines Sortieren nach 2 Kriterien
Ich habe eine Menge von Objekten mit diversen Eigenschaften. Diese Objekte sind in einer TObjectlist verwaltet. Diese Liste sortiere ich mit der mitgelieferten Sort-Funktion: Liste.Sort(Sortieren_1);, wobei

Delphi-Quelltext
1:
2:
3:
4:
function Sortieren_1(item1,item2:pointer):integer;
begin
    result := AnsiCompareText(TMyObject(item1).Prop1, TMyObject(item2).Prop1);
end;
eine entsprechende Compare-Funktion ist.
Ich habe bisher für jeder der ca. 5-10 Eigenschaften, nach denen sortiert werden kann, eine eigene kleine Compare-Funktion, die mir die Listen sortiert.

Jetzt bekomme ich das Problem, dass ich gerne nach zwei Kriterien sortieren möchte. D.h. ich habe so eine Compare-Funktion:

Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
function Sortieren_1_2(item1,item2:pointer):integer;
var tmp:integer;
begin
  tmp := AnsiCompareText(TMyObject(item1).Prop1, TMyObject(item2).Prop1);
  // Wenn Vergleich nach Eigenschaft1 keine Unterscheidung liefert,
  // Dann Eigenschaft2 für größer/kleiner nehmen
  if tmp = 0 then
      result := AnsiCompareText(TMyObject(item1).Prop2, TMyObject(item2).Prop2)
  else result:=tmp;
end;


Jetzt die Frage. Wenn ich mit dem Verfahren jede mögliche Sortierung ermöglichen will, brauche ich bei 5-10 Eigenschaften 25 bis 100 solcher Funktionen, was ich unschön zu Programmieren finde. Sowohl was Fehlersuche als auch Erweiterbarkeit angeht. Geht das einfacher zu programmieren? Und zwar so, dass das immer noch einigermaßen performant bleibt (also in O(N*logN) mit einer Konstante, die nicht viel größer ist als bei 100 gecodeten Einzel-Prozeduren).


Narses - So 23.07.06 12:10

Moin!

Ja, ich denke, das geht; schnell und einfach allerdings nur mit etwas zusätzlichem Speicheraufwand. ;)

Füge in jedes Objekt noch eine Eigenschaft ".SortHash" ein, in der du - nach den aktuellen Kriterien aufgebaut - einen Sortiertwert zur Verfügung stellst. Danach sortierst du einfach immer, und wenn du die Sortierung änderst, bildest du den SortHash neu. Für häufig verwendete Sortierungen bieten sich vielleicht ein oder zwei zusätzliche, statische SortHashes an.

Gibt sicher auch noch andere Methoden, die fiel mir als Erste ein. ;)

cu
Narses


Gausi - So 23.07.06 12:23

Ja, dieser Gedanke ist mir auch schon gekommen. Bzw. wollte ich in meiner ursprünglichen Überlegung insgesamt 4 zusätzliche Felder einführen (zwei Strings und zwei Integer) und dann 4 Compare-Funktionen. (Die zu sortierenden Eigenschaften sind Strings oder Integer.)
Zu Beginn des Sortierens würde ich dann die Liste einmal durchgehen, die Felder entsprechend der Sortierkriterien setzen, und dann die dazu passende Compare-Funktion zum Sortieren nutzen. Vier brauche ich für die vier Kombinationsmöglichkeiten von Integer und String für die beiden Sortierkriterien...

Aber das erscheint mir etwas unprofessionell :nixweiss:


Narses - So 23.07.06 12:39

Moin!

user profile iconGausi hat folgendes geschrieben:
Aber das erscheint mir etwas unprofessionell :nixweiss:

Hehe, meine Definition von "professionell" ist: wenn es funktioniert (Leitkriterium) und performant ist (wünschenswert). ;) Wie konkret du da dran kommst, das kann nicht Wesen der Professionalität sein, sondern WIE SCHNELL du das schaffst und ggfs. wieder Änderungen daran vornehmen kannst. :D

user profile iconGausi hat folgendes geschrieben:
Ja, dieser Gedanke ist mir auch schon gekommen.

Dann mach´s doch einfach mal, kann doch nicht soo aufwändig sein. ;)

user profile iconGausi hat folgendes geschrieben:
Vier brauche ich für die vier Kombinationsmöglichkeiten von Integer und String für die beiden Sortierkriterien...

Pack die Integer einfach binär mit in die SortStrings (ggfs. Längenprobleme beachten; halt die Strings auf irgendwelche signifikaten Stellen begrenzen, kann mir nicht vorstellen, das Sortierung auf tausende Stellen Sinn macht) und dann alles gleich behandeln, fertig. ;) Kann man dann zwar nicht mehr so einfach zu debugzwecken ausgeben, aber so ist das Leben.

cu
Narses


Gausi - So 23.07.06 12:55

Ich frag deswegen mal vorher nach, weil ich zur Zeit an einer Stelle statische Sortierungen nach zwei fest vorgegeben Kriterien habe, und dies gerne variabel gestalten möchte. Dazu sind leider einige Umbauten am existierenden Code notwendig (und wenns nur sinnvolle Umbenennungen der Variablen und Prozeduren sind). - Daher möchte ich gerne Designfehler im Vorfeld vermeiden. Außerdem ist der existierende Code leider etwas unübersichtlich, weil ich mit mehreren Listen hantiere, die aber zueinander passen müssen.

Ein weiteres Problem, was ich oben noch vergessen habe: Ich brauch natürlich auch schnelle Suchroutinen für die sortierten Listen. Ich muss z.B. schnell alle Objekte auflisten, die eine spezielle Eigenschaft1 haben, oder eine spezielle Eigenschaft2 oder sowohl 1 als auch 2. (Dafür brauche ich natürlich zwei Kopien der Liste, einmal 1-2 sortiert, und einmal 2-1)

Binärsuche ist da auch kein Problem, wenn ich immer nach den Hashes suche - aber ich denke, dass ich da doch die Trennung brauche...:gruebel:


Heiko - So 23.07.06 15:15

Man kann es auch ohne Hashs leicht machen, allerdings nur unter einer Bedingung: man muss eine eigene Klasse, Reocrd oder ähnliches brauchen, also man kann nicht nach meheren Eigenschaften von z.B. TFont sortieren. Ich vermute mal, es ist für dein nemp, also passt der alte Code vom MMP relativ gut ;). Und zwar kann man es folgendermaßen machen (hatten wir beim MMP vorm Umstieg auf VST so ;) ):


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:
const
  Strs  = 13//max Strs.
  Ints  =  1//max Strs.
  Bools =  1//max Strs.
  StrsTitle       =  0;
  StrsArtist      =  1;
  StrsAlbum       =  2;
  StrsGenre       =  3;
  StrsYear        =  4;
  StrsComment     =  5;
  StrsComposer    =  6;
  StrsEncoder     =  7;
  StrsCopyright   =  8;
  StrsLanguage    =  9;
  StrsLink        = 10;
  StrsFormat      = 11;
  StrsFileFolder  = 12;
  StrsFileName    = 13;

  IntsTrack       =  0;
  IntsFileSize    =  1;

  BoolsDefect     =  0;
  BoolsSelected   =  1;

type
  TMusicInfo = record
    Strs:  array[0..Strs ] of String;
    Ints:  array[0..Ints ] of Integer; //die lasse ich im Bsp. jetzt mal außen vor, da musst du im Sort array eben noch einspeichern, welcher Typ es ist
    Bools: array[0..Bools] of Boolean;
  end;


Das war da die Grundstruktur, zum schreiben des Sortieralgos waren wir noch nicht gekommen, von daher nur die Theorie (die garantiert funktioniert ;) ).
Und zwar brauchst du dann noch ein einfaches Array of integer // ich nenns hier mal Sort ;-), wobei das array so viele Elemente zulassen muss, wie es Eigenschaften gibt (müsste also 0..Strs+Ints+Booles+3 sein). In diesem Array wird dann die Sortierreihenfolge gespeichert. Also wenn z.B. nach dem Titel sortiert werden soll, ist also das erste Element (Pos. 0) im Sort-Array, wenn das 2. Sortierkriterium z.B. das Genre sein soll, ist das 2. Element im Sort-Array Genre (also Sort[1]:=StrsGenre).

Das Sortieren würde dann so hier ablaufen:


Delphi-Quelltext
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
function Sortieren_1(item1,item2:pointer):integer;
var
  i: integer;
begin
  result:=0;
  i:=0;
  while (result=0and (i<MaxPropertys) do //MaxPropertys = soviele eigenschaften wie es gibt
  begin
    result := AnsiCompareText(TMyObject(item1).Strs[Sort[i]], TMyObject(item2).Strs[Sort[i]]);
    inc(i);
  end;
end;


Ich vermute mal, dass du es so machen willst, dass wenn zu erst nach Spalte3 sortiert wurde und anschließend auf Spalte1, dass das erste Sortierkriterium Spalte1 sein soll und das 2. Kriterium Spalte3.

Also musst das OnHeaderClick-Ereignis folgendermaßen funtkionieren: Du verschiebst alle Elemente von vorne um eins nach hinten, bis zum Element, nach dem sortiert werden soll. Und dieses Element (nach dem jetzt sortiert werden soll, kommt dann an die Stelle Sort[0]).

Damit kannst du, unter einer gewissen Ordnung dir das Leben einfach gestalten, auch wenns mehr Denkarbeit erfordert ;). Das Sortarray würde ich an deiner Stelle nicht als ein Array voll Integern machen, sondern als Array von einem Record, wo einmal der Integer drin steht, dann der Typ (obs der Index aus dem Bereich Strs, Ints oder Bools kommt) und dann noch als Extra eigenschaft (nicht im Array), welche Spalte als letztes sortiert wurde und wie rum ;).

Heiko


Horst_H - So 23.07.06 15:20

Hallo,

wenn ich das recht verstehe, dann ist dies doch wie bei Excel Sortierung nach dieversen Kriterien rauf und runter.
Ich denke das funktioniert einfach mit einer Funktionsliste.
1. Erstellen der Vergleichsfunktionen fuer die verschiedenen Kriterien mit der Eigenschaft aufwaerts abwaerts(invertiert)
2. Auswaehlen der Funktionen (Spalte A rauf,Spalte C runter-> Objekt Eigenschaft 1 , Objekt Eigenschaft 3 invertiert)
3. Erstellen der entsprechende Liste von Funktionsadresse , Richtung
4. Aufrufen

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:
Es bei Item1, Item2 eine Pointer auf das Objekt uebergeben.
Die CompFunc muss sich die gewuenschten Properties kennen.(Also geht auch Objekt.Eigenschaft1 vergleichen mit Objekt2.Eigenschaft7)

type
  TCompFunc = function(Item1,Item2:Pointer):integer;
  TCompArrItem = record
                   CompFunc:TCOmpFunc;
                   inverted : integer;{=1 oder -1}
                 end;
  TCompArray = array of TCompArrItem;
{
function CompFuncEig47_11 :TCompFunc;
begin
  result := TMyObject(item1).Prop47-TMyObject(item2).Prop11;
end;

function CompFuncEig08_15 :TCompFunc;
begin
  result:= 1;
  IF NOT(TMyObject(item1).Prop08)OR TMyObject(item2).Prop15 then
     result := 0
  else
     IF NOT(TMyObject(item1).Prop08)XOR TMyObject(item2).Prop15 then
       result := -result;    
end;

function CompFuncEig2_103 :TCompFunc;
begin
  result := AnsiCompareText(TMyObject(item1).Prop2, TMyObject(item2).Prop103);
end;
}

function CompFunc_Multi(item1,item2:pointer;CompArray:TCompArray):integer;
var
  I :integer;
begin
  result := 0;//Falls Liste leer aendere nichts
  I := 0;
  while i< length(CompArray) do
    begin
    with CompArray[i] do
       result := CompFunc(item1,item2)*inverted;//*inverted ist wohl schneller als ein zusaetzlicher Vergleich
    IF result <> 0 then
      BREAK;
    inc(i);
    end;
end;


Ich hoffe es tendiert in diese Richtung.

Gruss Horst

Uups zu spaet ...


MrSaint - So 23.07.06 15:30

Hallo!

Ich hab's jetzt nicht ganz durchgelesen, wenns also schon vorkam, sorry :) Der Trick bei der Sache ist, benutze nicht die Sort Funktion von TObjectList. Diese sortiert mit dem QuickSort und dieser ist nicht stabil. Stabil ist ein Sortieralgorithmus dann, wenn er die Reihenfolge der Elemente, für welche die Compare-Methode "gleich" ausgibt im Ergebnis nicht verändert. Sprich: Du musst, wenn du dan 2 Eigenschaften sortieren willst, erst nach der sekundären sortieren, dann nach der primären. Für Elemente, welche primär gleich sind, zählt dann die Reihenfolge der sekundären Sortierung. Algorithmen dazu: http://de.wikipedia.org/wiki/Sortieralgorithmus
Ha, war mein Seminar über Sortier- und Suchalgorithmen doch zu was zu gebrauchen ;)



MrSaint


Heiko - So 23.07.06 15:39

Von der Performance her ist das aber wesentlich langsamer, da 2x sortieren von nöten ist ;).


Gausi - So 23.07.06 15:58

@MrSaint: Stabil oder nicht ist mir egal. Klar ist, dass man bei Quicksort nicht einfach zweimal sortieren kann, und dann das gewünschte Ergebnis hat. Welchen Algo benutzt du denn? Mergesort? Die Möglichkeit fällt aber generell raus, da ich sowieso zweimal sortieren muss (weil ich zwei Listen habe), und dein Vorschlag dann auf viermal rauslaufen würde. Das ist nicht mehr so schön. Wenn man fünfstellige Anzahlen hat, amcht sich das schon bemerkbar ;-)

@Heiko: Ja, das sieht ganz ok aus...Allerdings müsste ich dafür den zugrundeliegenden Datentyp umschreiben. Bisher habe ich da benannte Eigenschaften, nicht einfach drei Arrays. Was mir an dieser Lösung auch nicht unbedingt gefällt, ist die Compare-Funktion, die ja doch ein paar Schritte mehr benötigt. Da diese sehr oft ausgeführt wird, frage ich mich, ob der Vorschlag von Narses nicht vielleicht besser ist. Der ist zwar nicht so universell, etwas schwieriger zu pflegen und hat eine dem Sortieren vorgeschaltete Initialisierungsphase, aber dafür kommt die Compare-Funktion ohne weitere Zugriffe auf Arrays, Schleifen und Fallunterscheidungen aus...
Und ja, es ist für Nemp, aber nicht an der Stelle, die du vermutest - es geht um die Vorauswahl-Listen oben links, wo ich unterschiedliche Kriterien zulassen möchte. Also nicht nur Artist-Album, sondern z.B. Genre-Jahr, oder Genre-Artist, oder Artist-Jahr, oder Jahr-Album usw.


MrSaint - So 23.07.06 16:41

Als Sortierverfahren würde ich den "MSD-Radixsort" (nach Sedgewick) vorschlagen. Hier mal eine C++-Implementierung:


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:
    void radixMSD(Item a[], int iLinks,
                  int iRechts, int d) {

        int i, j, count[R];
        // maxN = Anzahl der Items in a
        Item aux[maxN];

        if (iRechts - iLinks <= M)
        {   // mit Insertionsort weitermachen
            insertion(a, iLinks, iRechts);
            return;
        }

        for (j = 0; j < R; j++)
            count[j] = 0;
        for (i = iLinks; i <= iRechts; i++)
            count[digit(a[i], d)]++;
        for(j = 1; i < R; j++)
            count[j] += count[j - 1];

        for (i = iLinks; i <= iRechts; i++)
            aux[iLinks+count[digit(a[i], d)]++] =
                a[i];

        for i = iLinks; i <= iRechts, i++)
            a[i] = aux[i];

        for (j = 0; i < R-1; j++)
            radixMSD(a, iLinks+count[j],
                     iLinks+count[j+1] - 1, d + 1);
    }


Der vergleicht 2 Strings zeichenweise. Hier mal ein paar Zahlen zum MSD-Radix im Vergleich zum Standard-Quicksort: Es werden die ersten N Worte von Moby Dick verglichen, die Werte sind "relative Zeitangaben" (habe ich so aus dem Buch Algorithmen in C++ Teil 1-4 von Robert Sedgewick, 3.Auflage):

N=12500, Standard-Quicksort: 7, MSD-Radix: 8
N=25000, 14, 15
N=50000, 34, 34
N=100000, 83, 71

Für viele zu sortierende Werte wird der MSD-Radix also besser gegenüber dem Quicksort.

Es gibt noch einen besseren Algorithmus für Strings, wenn man viele items sortieren will, der sogenannte "Dreiweg-Radix-Quicksort" (auch aus dem Buch von Sedgewick), leider ist der aber nicht stabil, dafür bei obigem Beispiel (Moby Dick) durchweg schneller als der QuickSort.


Wenn ich das nun richtig verstanden habe, willst du auf Anhieb nach zwei Eigenschaften sortieren. Also nicht so, dass der User halt zwei Header einer ListView (o.Ä.) nacheinander klickt. Wenn es nämlich so wäre, müsstest du ja so oder so zweimal sortieren, dann könntest du auch meine Version verwenden, die unter diesen Umständen dann schneller wäre (eben wegen der while-Schleife in der Compare-Funktion). Wenn du's aber auf Anhieb machen willst, sieht meine Verison wohl etwas alt aus :(



MrSaint


P.S.: Ach ja, was man vielleicht noch anmerken sollte ist, dass bei den Radix-Sorts die zu sortierenden Werte relativ zufällig sein sollten (wie bei den Wörtern von Moby-Dick eben). Ob das bei Musiktiteln jetzt gegeben ist, ist wohl streitsache. Bei den Liedtiteln wahrscheinlich schon, wenn man aber viel Musik von einer bestimmten Gruppe hat und nach der Gruppe sortiert ist etwas blöd :(


Horst_H - So 23.07.06 16:54

Hallo,

Zitat:

Was mir an dieser Lösung auch nicht unbedingt gefällt, ist die Compare-Funktion, die ja doch ein paar Schritte mehr benötigt


Das stimmt doch in den meisten Faellen nicht.
Bei n=10000 CD's mit m=20 Titeln (Anzahl aller Titel also n*m),wird beim Sortieren nach CD-Namen und Titel fuer jede CD nur ~m/n mal der Weg in die 2.te Vergleichsstufe genommen und sonst wie gewoehnlich sofort das richtige Vergleichsergebnis geliefert.
Falls das Datenschieben nichts kostet (Zeiger tauschen) dauert es also nur ca das 1+m/n mehr an Zeit, hier also nur 0,2%.

Gruss Horst


Heiko - Mo 24.07.06 11:52

Dazu kommt noch, dass du erst einmal den Hash erzeugen musst, auch wenn er später nicht mehr unbedingt verwendet wird ;).


Gausi - Mo 24.07.06 13:19

Hmmm... Zur Zeit tendiere ich wieder zu Heikos Lösung. Auch daher, weil ein wichtiger Einwand von mir flöten gegangen ist - sämtliche sinnvollen Vorauswahlkriterien sind Strings (ja, auch das Jahr). Eine Vorauswahl nach Bitrate, Länge oder Samplerate erscheint mir eher unsinnig.
Außerdem ließen sich so wahrscheinlich auch die Suchroutinen einfacher programmieren, und das Problem, dass ich die Objekte in zwei unterschiedlich sortierten Listen vorliegen habe (=> ich bräuchte die Hashwerte in zwei Versionen), habe ich dann auch nicht mehr. (Ich muss dann nur zwei kleine Arrays für die Sortierreihenfolge haben.)

Aber: Das mit der Array-Struktur und den Konstanten-Bezeichnern StrArtist etc. ist zwar schön, würde aber bedeuten, dass ich das komplette Projekt dahingehend umbauen muss. Außerdem ist an vielen Stellen eine direkter Zugriff über MyAudiofile.Artist wesentlich bequemer zu programmieren (Autovervollständigung) als ein MyAudiofile.strings[StrArtist];.
Gibt es eine Möglichkeit, Variablen so zu deklarieren, dass die 10 einzelnen Stringvariablen im Code synonym für die 10 Strings im Array verwendet werden können? Ich bin zwar über absolute gestolpert, aber das scheint mir nicht ganz das richtige zu sein, da ich das nur in der Variablendeklaration verwenden kann, aber etwas wie

Delphi-Quelltext
1:
2:
3:
// im Create des Objektes:
Str[StrArtist] absolute = Artist;
Str[StrAlbum] absolute = Album;
geht damit nicht, oder?


Heiko - Do 27.07.06 18:23

Hallo gausi,

ich habe dein Problem jetzt mal mit Pointern gelöst:


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:
  TTags = class(TObject)
    FTest: Integer;
    FArtist: AnsiString;
    FTitle : AnsiString;
  end;

  TStrAr = array[0..1of AnsiString;
  PStrAr = ^TStrAr;

var
  Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);
var
  Tags: TTags;
  test: PStrAr;
begin
  Tags:=TTags.Create;
  Tags.FTest:=4;
  Tags.FArtist:='Artist';
  Tags.FTitle:='Title';
  test:=Pointer(@Tags.FArtist);
  ShowMessage(test^[0]+' '+test^[1]);
  Tags.Free;
end;


Wie du siehst brauchst du nicht einmal deine Klasse verändern :zustimm: , aber ich weiß leider nicht, wie propertys im RAM aussehen. Wenn ich das wüsste, hätte ichs dir gleich mit propertys gemacht. Wenn du nur lesen willst ist es aber kein Problem, denn dann richteste dir einfach noch ne Property ein, die den Zeiger auf den ersten String (etc.) aus dem Privaten zürückgibt, so dass du damit arbeiten kannst ;).

PS: Ob nun die Variante, die die im DP [http://www.delphipraxis.net/topic88704,0,asc,0.html&sid=a60c5064a914170bba9cd57c2f45f0d7] gefunden haben besser ist als meine, ist geschmackssache, sobald du aber mit propertys arbeitest (lesen dürfte kein PRoblem sien, aber schreiben...), wird deren Variante besser sein ;).


Gausi - Do 27.07.06 19:06

Danke, Heiko. Aber ich glaube, ich nehme doch die DP-Varainte. Die scheint mir etwas "stabiler" zu sein, was Umbauten im Code angeht (z.B. wenn ich irgendwann die Klasse um eine Eigenschaft erweitere, oder die Reihenfolge in der Deklaration ändere), dann komme ich mit deinem Verfahren in Teufels Küche, würde ich sagen ;-).

Die Daten intern (private) in einem Array zu verwalten, und nach außen hin die Einzel-Eigenschaften und das String-Array über Getter und Setter sichtbar zu machen, halte ich da für deutlich übersichtlicher und auch eher OOP-Konform.

Den kleinen Umbau an der Klasse (das ist ja nun wirklich nicht viel) nehme ich dafür gerne in Kauf :D