verschiedene Objektlisten schnell sortieren und filtern

[stahli]

Gesetzt den Fall, ich habe mehrere Listen mit verschiedenen Objekten.
- Personenliste
- Adressliste
- Autoliste

Die Objekte verwalten dann u.a. ggf. Instanzen auf andere Objekte.
Z.B. unterhält eine Person eine Liste von Autos (real eine Liste von Id´s, die dann zur Laufzeit bei Bedarf zur Objektbeschaffung (GetAuto(Id) ) genutzt werden).

Nun möchte ich alle Listen unterschiedlich sortieren können (bzw. dies dem User ermöglichen).
Suchen und sortieren realisiere ich derzeit erst mal über BinarySearch mit einem Comparer, der sich derzeit nur auf die ID bezieht:

Delphi-Quellcode:

function TssObjectComparer.Compare(const O1, O2: TssObject): Integer;
begin
  Result := CompareStr(O1.Id, O2.Id);
end;

...

procedure TssIO_Custom.RegisterObject(ssObj: TssObject);
var
  Index: Integer;
begin
  if not Assigned(ssObj) then
    Exit;
  if not ssObjectList.BinarySearch(ssObj, Index) then
    ssObjectList.Insert(Index, ssObj);
end;

Wenn ich jetzt nach anderen Eigenschaften sortieren/suchen/filtern will (z.B. Person.FirstName(aufsteigend) UND Person.LastName(absteigend)) und beliebigen sonstigen Varianten, wie realisiert man das am besten?
Für jeden Sortierfall eine eigene Liste mit eigenem Comparer?
Man muss dann natürlich jeden Einfüge- und Löschvorgang für eine Objektmenge für mehrere Listen durchführen.
Ist das als zweckmäßig und sicher anzusehen? Der Speicherverbrauch ist natürlich auch höher.

Der umfangreichere Quelltext wäre nicht das Problem, da dieser durch einen Experten erzeugt wird.
Ich müsste dann in den Metadaten nur definieren, welche "Indizes" benötigt werden.

Alternativ könnte man eine Liste immer umsortieren, was allerdings bei größeren Listen dann etwas dauern kann.

Ein Problem ist z.B. auch, wenn ich alle Personen suchen will, deren Adressobjekt den Ort "Halle" beinhaltet.
Das ist wohl dann der Nachteil gegenüber einer SQL-Abfrage.


Grundsätzlich will ich das dann so organisieren, dass alternativ zu Objektlisten ein ORM verwendet werden kann.
In dem Fall würde die Sortierung/Filterung dann über SQL realisiert.
Für die Anwendung soll sich dann keine Änderung ergeben, egal ob die Daten in Objektlisten oder über einen ORM verwaltet werden.

[Uwe Raabe]

Du könntest unterschiedliche Comparer-Instanzen verwenden und beim Umschalten ein Sort() aufrufen. Du kannst z.B. ein Array aller Comparer verwalten, bei dem du den gerade aktuellen über einen einstellbaren Index ermittelst. Natürlich müssen alle möglichen Sortierungen im Vorfeld bekannt sein oder über Parameter gesteuert werden.

[Furtbichler]

Ein einfaches Beispiel für einen universellen Comparer. Nehmen wir an, wir hätten 3 Properties 'A', 'B' und 'C'. Für jede Property existiert eine ID (Zahl, Enum oder so). Man könnte das auch mit RTTI lösen, aber so ist es 'plain old pascal'.

Delphi-Quellcode:

Type
  TPropertyEnum = (A,B,C);
  TSortDesc = Record
    sdProperty : TPropertyEnum;
    sdDescending : Boolean;
  End;

  TSortDescArray = Array Of TSortDesc;

Function GetValue (Const V : TMyClass; property : TPropertyEnum) : Variant;
Begin
  case property of
    A : return V.A;
    B : return V.B;
    C : return V.C;
  end
end;

Function Compare (Const V1, V2 : TMyClass: SortBy : TSortDescArray) : CompareResult;
Begin
  Foreach sortDesc in SortBy do begin
    value1 := GetValue(V1, sortDesc, sdProperty);
    value2 := GetValue(V2, sortDesc, sdProperty);
    Result := CompareValue(value1, value2);
    if sortDesc.sdDescending then Result := -Result;
    if Result<>0 then break;
  end
end;

Wenn Du nun zuerst nach A aufsteigend, dann nach B absteigend sortieren willst, dann füllst Du das Array einfach mit (A,false), (B,true);

Eigentlich ganz einfach.

[stahli]

Danke Euch. In Uwes Richtung habe ich schon gedacht.
Bei der Generierung der Klassen kann ich ja automatisch unterschiedliche Comparer definieren.

Die Frage ist dann halt, ob ich durch List.Sort(aComparer) eine Liste nach Bedarf umsortiere oder persistent unterschiedliche Listen mit jeweils einem anderen Comparer parallel verwalte.
Hinzufügen und Löschen von Einträgen müsste dann entsprechend natürlich in z.B. 6 Listen parallel erfolgen.
(So ungefähr wäre das dann ja wie das Verwalten von Indizes in einer Datenbank - sehr pauschalisiert natürlich.)

Ich werde mal entsprechende Versuche machen. Bei großen Listen ist sicher die zweite Variante merklich schneller.
Das Einfügen von Einträgen unter Verwendung von BinarySearch (wie im Beispiel beschrieben) geht ja extrem fix. Umsortieren von Listen kann dagegen sicher etwas dauern.


Andere Frage:

Ich habe eine Personenliste. Jede Person kann mehrere Adressen haben (AdressId´s in einer SubListe).
Nun suche ich alle Personen, die eine Adresse in "Halle" haben.

Suchergebnis soll eine Liste von Id´s sein (StringList).

Code:

#4782-3578-2323523
#736-536-936346
#7568-374-3453465

Zur weiteren Verarbeitung werden dann die Personenobjekte mit den entsprechenden zugehörigen Id´s abgerufen.

Das Framework kann dabei
a) die Daten in Objektlisten (PersonenListe und AdressenListe) verwalten
oder
b) die Daten über einen ORM in einer Datenbank verwalten.

Die Anwendung soll von der Speichervariante grundsätzlich keine Kenntnis haben.

Ich könnte also alle Personenabjekte abrufen und dann deren Adressobjekte. Ist ein Adressobjekt mit "Halle" dabei, wird die PersonenId in die Ergebnisliste aufgenommen.

Alternativ könnte ich alle Adressdaten durchsuchen und mir die AdressId´s für "Halle" merken.

Wenn nun jede Person nur eine Adresse hätte könnte man jetzt leicht über einen Comparer nacheinander per BinarySearch alle PersonenId´s für alle vorgemerkten AdressId´s suchen. Das wäre sicher extrem schnell.

Da aber jede Person mehrere Adressobjekte haben kann, kommt man so nicht weiter. Also bleibt ein Interieren über alle Personen und Durchsuchen von deren AdressId-Liste (da diese nicht sortiert sein muss über IndexOf).

Sofern ein ORM genutzt wird bliebe natürlich noch die Möglichkeit, die PersonenId´s über ein SQL-Statement zu ermitteln. Dies würde ich aber mal als Sonderfall betrachten, der hier außen vor bleiben soll.

Ich brauche eben genau eine Lösung für die Suche in vorliegenden verschachtelten Objekten (egal ob diese über Objektlisten oder einen ORM verwaltet werden). Real sind letztlich aber nur die Id´s der Subobjekte (im Beispiel Stringliste mit AdressenId´s) im übergeordneten Objekt (hier Personenobjekt) abgelegt.


PS: Ein ORM muss die zu verwaltenden Tabellen natürlich so indizieren, dass schnelle Zugriffe auf die "Objektdaten" möglich sind und er soll auch solche Abfragen per SQL realisieren. Das Projekt selbst soll aber auf einen direkten Zugriff auf die Datenbank nicht angewiesen sein. Lediglich optional soll ein solcher Weg MÖGLICH sein.
Primeres Augenmerk liegt für mich daher erst einmal im Umgang mit reinen Objektlisten ohne Datenbank.

[stahli]

*Ich pushe mal*
(Ich bekenne, die Fragestellung ist recht unscharf aber vielleicht gibt es ja schlaue Tipps zum Suchen in Objektstrukturen.)

[Furtbichler]

Bist Du dir sicher, das es hinsichtlich der Skalierbarkeit eine kluge Idee ist, die Suche in-Memory durchzuführen?

Wenn 'JA', dann suche die Listen einfach linear durch, denn dann hast Du nicht sonderlich viele. Wenn 'NEIN', dann verlagere die Suchlogik in die DB und suche per SQL, LIKE, Volltext oder mit Spacial Indexes. Nach dem Motto: "Überlasse die Arbeit dem jeweiligen Spezialisten" ist eben die Suche in einer Datenbank am Besten aufgehoben. Du merkst ja schon, was für Klimmzüge und umständliche Überlegungen du anstellst.

Wenn Du trotzdme in Memory suchen willst, erstelle Dir für bestimmte Suchoperationen, die oft verwendet und schnell sein sollen, spezielle Suchroutinen, z.B. indem Du dir eine Dictionary über die PLZ machst, wobei in jedem Dictionary-Eintrag widerum eine Liste der Kunden mit dieser PLZ steht.

Ich kann mir aber vorstellen, das eine einfache foreach-Schleife schnell genug ist, wenn Du maximal -sagen wir- 20.000 Kunden hast.

Ich persönlich würde mir aber lieber Gedanken über ein Control/Frame machen, bei dem Du komfortable Filtereinstellungen vornehmen kannst und dieses Control liefert Dir dann die richtige 'WHERE' Klausel deines SQL-Befehls.

Alles andere wäre in meinen Augen "von hinten durch die Brust ins Auge".

[stahli]

Danke Dir.

Ich will über meinen Experten Klassen erstellen, die dann ein Rundum Sorglos Paket bieten

Man soll dann in den Metadaten angeben, welche Eigenschaften man indexieren will usw.
Wird dann eine Personenliste nach Vornamen sortiert, verwendet das Framework den automatisch erstellten Comparer.

Als Ziel für die Daten kann man Objektlisten (mit automatischer Datenserialisierung) wählen oder einen ORM (mit bestimmter Datenbank).

In der Businesslogik rufe ich dann Objekte oder Listen ab und muss mich nicht kümmern, wie die verwaltet werden. Das Ziel kann ich auch nachträglich auf Knopfdruck umstellen.

Grundsätzlich funktioniert das schon alles sehr gut. Nur die Sortierung und Filterung von Daten ist noch nicht gelöst.
Hier muss ich intern zwei Wege gehen:
- Suchen und sortieren in reinen Objektlisten und ID-Listen
- Suchen in einer Datenbank mittels SQL

Die Anwendung soll von dieser Differenzierung nichts bemerken.

Da die Units im allgemeinen automatisch generiert werden kann ich auch Funktionen wie:
function TManager.GetPersonListWhereFirstNameOrderByLastName(aFirstname): TPersonList;
generieren. Es müsste dazu in den Metadaten nur definiert werden, nach was genau gesucht werden soll.
Den Vorteil gegenüber LINQ u.ä. Lösungen ist, dass man die benötigten Funktionen gut optimieren kann (incl. Comparer z.B.).
Schreibarbeit fällt nicht an, da der Quelltext automatisch erzeugt wird.

Ob Objektlisten oder ein ORM benutzt wird, wird dann innerhalb der Funktionen unterschieden.

Ich muss darauf mal noch etwas herum denken...