Ich habe eine Liste, und die soll bitte immer sortiert sein

[stahli]

Ich verwalte eine sortierte Liste von Objekten so:

Delphi-Quellcode:

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

function TssIO_Custom.GetObject(Id: TssId): TssObject;
var
  Index: Integer;
  ssObj: TssObject;
begin
  Result := nil;
  // Objekt wird ohne Registrierung erzeugt um nach einem Objekt mit der passenden ID suchen zu können
  ssObj := TssObject.Create(nil, Id, True); 
  if ssObjectList.BinarySearch(ssObj, Index) then
    Result := ssObjectList[Index];
  FreeAndNil(ssObj);
end;

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

Geht nach meiner Einschätzung schnell und einfach. Man muss natürlich immer diese zwei Methoden nutzen.

[Namenloser]

Man sollte aber beachtet, dass das Einfügen dabei auf jeden Fall O(n) Zeit kostet.

Wenn man eine verkettete Liste verwendet, muss man durchschnittlich die Hälfte aller Items durchlaufen, bis man die richtige Einfügestelle findet, dafür geht das Einfügen dann schnell. Verwendet man stattdessen ein Array (wie TList), kann man zwar eine binäre Suche durchführen, aber dafür muss man dann beim Einfügen O(n) Items an eine andere Stelle verschieben, also auch nicht besser.

Die einzige wirklich saubere Variante für eine sortierte Liste ist ein balancierter Baum. Dort geht das Einfügen in O(log n). Ich glaube, Delphi hat von Haus aus aber leider keine Implementierung. Ich hab mal eine geschrieben, aber sie ist nicht sauber genug, um sie hier zu veröffentlichen...

Wenn man keinen Baum zur Verfügung hat, dann ist es schlauer, alle Items erst mal unsortiert einzufügen, und dann am Ende in O(n log n) zu sortieren.

Edit: Wobei mir einfällt, Heaps gibt es auch noch. Sind leichter zu implementieren als Bäume und das Einfügen geht auch in O(log n). Dafür kann man aber immer nur das „größte“ oder „kleinste“ (je nachdem) Item auslesen. Aber für eine Priority-Queue könnte das ja z.B. schon reichen.

[Furtbichler]

Eine Skiplist ist übrigens auch ganz brauchbar, nur versteht man (ich jedenfalls) nicht genau, wie es funktioniert.

Edit: Typisch, hab mal wieder nicht alles gelesen, daher ein radikales Edit.

Aber eine Frage: Wozu benötigt man eine Liste, die immer sortiert ist?

[stahli]

Ich hänge mich hier mal dran...

Ich habe eine unsortierte Personenliste. Die tatsächlichen Einträge ergeben quasi eine native Reihenfolge.

Nun möchte ich sortierte (und gefilterte - das soll hier aber nicht relevant sein) Sichten auf die originale Liste ermöglichen.

Mit MyList.CreateSortetView('Firstname') und MyList.CreateSortetView('Lastname') würde ich z.B. zwei Kopien der Liste erzeugen und dort auf die Einträge sortiert zugreifen z.B. über MyList.SortetView('FirstName').
Bei Einfügungen, Löschungen und Änderungen in der Hauptliste müssten die Einträge der sortierten Sicht angepasst werden.
Idealer Weise nicht durch eine komplette Neusortierung sondern durch direkte Änderung der bearbeiteten Einträge wie in meinem Beitrag #11 (ungelöst für mich bisher: Reaktion auf eine Vornamenänderung von einer in der Liste enthaltenen Person).

Einfügungen und Löschungen in der Hauptliste könnte ich mit einer binären Suche in den sortierten Listen wie oben angedeutet recht einfach umsetzen.

FRAGE: Lohnt sich ein höherer Aufwand in Bezug auf die zu erwartende Performance wenn man einen binären Suchbaum benutzt (wie Namenloser in #12 schreibt).
Eine Liste kann u.U. auch mal 100T Objekte oder mehr enthalten.
Würde sich ein binärer Suchbaum anbieten? Gibt es nutzbare Implementierungen (@Namenloser, Deine inzwischen?)? Oder ist eine binäre Suche in einer Liste ohnehin fast gleich schnell?

Ich muss möglichst performant entweder eine komplette sortierte Kopie einer Liste erzeugen oder Änderungen in der Originalliste parallel in den sortierten Listen nachführen.
Zur Laufzeit muss ich dann z.B. möglichst schnell die Einträge 90.000 bis 90.199 abrufen können (je nachdem aus der originalen oder alternativ aus einer sortierten Listenkopie).

[Sir Rufo]

Wenn du auf Änderungen der Liste und der enthaltenden Instanzen reagieren willst, dann brauchst du eine ObservableCollection die nur ObservableObject aufnehmen können. Soll also heissen, du musst die Liste und die Eigenschaften der Listen-Elemente überwachen.

Gibt es natürlich nicht fertig in der RTL. Bei Spring4d wirst du aber fündig.

[stahli]

... und die Grundfrage: Aufwand/Performance im Vergleich zwischen "binärer Suche in Liste" und "binärer Suchbaum".

Wieviel aufwendiger wäre ein Baum und dafür wieviel schneller als eine Liste?

Die binäre Suche in einer Liste habe ich drauf.
Würde es sich sehr lohnen, einen Baum aufzubauen?

[mm1256]

Zitat von stahli:

...Würde es sich sehr lohnen, einen Baum aufzubauen?

Ist das ein Übungs- oder Testprojekt? Wenn nicht, den Zeitaufwand bezahlt kein Mensch und darum würde ich für sowas eine Standardlösung verwenden, z.B. eine MemTable.

[stahli]

Nein, ist kein Testprojekt.
Tatsächlich sind das Interfaces, die in Listen verwaltet werden.

Mit binärer Suche in Listen werde ich das gut lösen können.
Die Frage ist, ob es eine bessere Lösung gibt. Einen Aufwand würde ich in Kauf nehmen, wenn der Effekt ausreichend groß ausfällt.

Aber ich werde das wohl erst mal mit Listen umsetzen und kann das ja später ggf. nochmal austauschen.

[Stevie]

Zitat von Sir Rufo:

Wenn du auf Änderungen der Liste und der enthaltenden Instanzen reagieren willst, dann brauchst du eine ObservableCollection die nur ObservableObject aufnehmen können. Soll also heissen, du musst die Liste und die Eigenschaften der Listen-Elemente überwachen.

Gibt es natürlich nicht fertig in der RTL. Bei Spring4d wirst du aber fündig.

Echt? Gibts in der Form nicht - klingt aber interessant.

Allerdings möchte ich in Frage stellen, ob die Liste sortiert werden muss, oder ob das nicht lieber die visuelle Komponente übernehmen sollte, an der so eine Liste hängt.

Wir benutzen in unserer Software entweder DevExpress Grid oder Virtual Treeview, die, wenn sie im Falle des Grids nicht über Datasets versorgt werden mit dem Presenter aus DSharp auf einer IObjectList arbeiten. Jegliche Sortierung, Gruppierung, Filterung o.ä. übernimmt das Control unter Zuhilfenahme der am Presenter hängenden Datatemplates.

[stahli]

Die GUI ist selbst entwickelt und hält nur die sichtbaren Daten vor.

Das Grid kennt also keine 1Mio Datensätze. Statt dessen wird der Server beauftragt, eine sortierte/gefilterte Liste bereit zu halten und das Grid ruft dann die Daten für deren z.B. Records 1000..1050 ab.

Wenn alternativ ein ORM genutzt werden soll, muss diese Sortier- und Filterfunktion an die Datenbank übertragen werden.

Aber für die Datenverwaltung in Objekten brauche ich auch eine Lösung.