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

[Der schöne Günther]

(Anmerkung: Es könnte auch in Sonstige Fragen zu Delphi passen, ich bin mir nich sicher)

Ich habe einen Datentyp, der bislang ein reiner Alias war:

Delphi-Quellcode:

TMeinDatentyp = TList<TPair<Single, Single>>

Ich möchte nun sicherstellen, dass die Liste immer nach einem bestimmten Kriterium sortiert wird (beispielsweise aufsteigend des ersten Single-Wertes). Wo muss ich in meiner zu bildenden Unterklasse ansetzen? Ich kenne das

Delphi-Quellcode:

OnNotify

-Event, aber das würde mir beim Einfügen von mehreren Einträgen gleich mehrmals feuern. Weiterhin wüsste ich nie, wann denn nun bei einem

Delphi-Quellcode:

AddRange

das letzte Notify-Event gefeuert wurde und ich nun sortieren muss. Ein

Delphi-Quellcode:

Begin/EndUpdate

scheint es für Listen ja auch nicht zu geben.

Delphi für .NET schien zweitweise ja mal die SortedList (das ist ja genau was ich will) implementiert zu haben, aber ich finde sie in meinem Win32-Delphi nicht :(

[himitsu]

Sortierte Listen brauchen kein Begin/EndUpdate, da sie das Add's direkt an der "richtigen" Stelle via Insert einfügen.

Aber das kann keine der generischen Listen.
Du kannst da nur immer am Ende TList<T>.Sort aufrufen.

Automatisch sortieren kann die nicht.
Ich kenn sowas nur von der TStringList.



Es gibt nur einige der anderen Listen, die immer sortiert sind, z.B. die Dictionaries, aber da sind die nur nach ihren Hash's sortiert.

Zitat:

Weiterhin wüsste ich nie, wann denn nun bei einem AddRange das letzte Notify-Event gefeuert wurde

Da könntest du natürlich einfach mal nachsehen.


AddRange geht auf InsertRange.

Delphi-Quellcode:

procedure TList<T>.InsertRange(Index: Integer; const Values: array of T);
begin
  ...
  for i := 0 to Length(Values) - 1 do
    Notify(Values[i], cnAdded);
end;

Alles hinzufügen und danach dann für Alle die Notify.
Da gibt es keinen "Letzten" zum erkennen.

[Der schöne Günther]

Genau. Das Dictionary hätte mir im Endeffekt nur das Gefummel mit TPair<X,Y> erspart, aber ich möchte ja jetzt explizit die Reihenfolge kontrollieren.

Ich könnte notfalls den Enumerator-Getter überschreiben so dass die Liste vorher sortiert wird. Aber indizierten Zugriff auf die Liste hätte ich damit auch nicht abgedeckt...

[Mikkey]

Du könntest von der Liste ableiten und die Einfügeoperationen selbst schreiben. Dabei musst Du sowas wie Insert unterbinden.

Ein Dictionary ist auch nicht sortiert, ermöglicht nur direkten Zugriff.

[blondervolker]

DeineTable.Sort := '[DEIN_NAME]';

[Zacherl]

Zitat:

Zitat von blondervolker (Beitrag 1243613)

DeineTable.Sort := '[DEIN_NAME]';

Das kann je nach Algorithmus zu erheblich längerer Laufzeit führen, wenn du die Liste nach jedem Einfügen komplett neu sortierst. Einfügen an der richtigen Stelle ist da schon deutlich besser. Stichwort: Binäre Suche.

[jaenicke]

Zitat:

Zitat von Der schöne Günther (Beitrag 1243601)

Ich könnte notfalls den Enumerator-Getter überschreiben so dass die Liste vorher sortiert wird

Ein Enumerator ist per Definition nicht dafür gedacht in einer bestimmten Reihenfolge durch eine Datenmenge zu gehen. Das ist zwar meistens so implementiert, aber gedacht ist das so nicht, dass man sich darauf verlässt.

Dafür sollte immer ein indexbasierter Zugriff benutzt werden.

Ich selbst habe dafür schlicht ToArray überschrieben und gebe die Einträge dort sortiert zurück, wenn eine eigene Property SortedArray gesetzt ist.

[Sir Rufo]

Da ist eine automatisch sortierende List-Klasse

Delphi-Quellcode:

unit SortedList;

interface

  uses
    System.Generics.Collections;

  type
    TSortedList<T> = class( TList<T> )
    protected
      procedure Notify( const Item : T; Action : TCollectionNotification ); override;
    end;

implementation

  { TSortedList<T> }

  procedure TSortedList<T>.Notify( const Item : T; Action : TCollectionNotification );
    begin
      inherited;
      if Action = cnAdded
      then
        Sort;
    end;

end.

Wonach sortiert wird, kann bei der Erstellung durch Angabe des

Delphi-Quellcode:

IComparer<T>

angegeben werden.

[Der schöne Günther]

Danke für all die Antworten soweit :-)

In jedem OnNotify zu sortieren wollte ich eigentlich vermeiden: Angenommen ich werfe mittels AddRange(..) oder ähnlichem eine Menge an n zusätzlichen Elementen in den Topf - Dann sortiert er n mal, obwohl er es nur einmal müsste.

Dunkel fällt mir noch die Magie von aspektorientierter Programmierung ein, damit habe ich allerdings Null Erfahrung und die Theorie mittlerweile auch wieder vergessen. Könnte man mit dem komischen TVirtualMethodInterceptor da etwas drehen? Für heute Nacht habe ich auf jeden Fall schon mal genug Lesestoff :roteyes:

[himitsu]

Delphi-Quellcode:

    procedure InsertRange(Index: Integer; const Values: array of T); overload;
    procedure InsertRange(Index: Integer; const Collection: IEnumerable<T>); overload;
    procedure InsertRange(Index: Integer; const Collection: TEnumerable<T>); overload;

Die auch noch überschreiben, da rein ein

Delphi-Quellcode:

inherited;

gefolgt vom

Delphi-Quellcode:

Sort;

und natürlich, während des inherited, die Sortierung vom Notify deaktivieren.


Und vergiß nicht, beim Aufruf von

Delphi-Quellcode:

TList<T>.Create

, den gewünschten Comparer anzugeben, wenn dir die Standardsortierung nicht gefällt.

[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

Delphi-Quellcode:

ObservableCollection

die nur

Delphi-Quellcode:

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. :nerd:
Würde es sich sehr lohnen, einen Baum aufzubauen?

[mm1256]

Zitat:

Zitat von stahli (Beitrag 1323989)

...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:

Zitat von Sir Rufo (Beitrag 1323987)

Wenn du auf Änderungen der Liste und der enthaltenden Instanzen reagieren willst, dann brauchst du eine

Delphi-Quellcode:

ObservableCollection

die nur

Delphi-Quellcode:

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.

[Namenloser]

Zitat:

Zitat von stahli (Beitrag 1323959)

Würde sich ein binärer Suchbaum anbieten? Gibt es nutzbare Implementierungen (@Namenloser, Deine inzwischen?)?

Ich habe das Projekt, wofür ich es brauchte, mehr oder weniger abgebrochen, und seitdem meine Implementierung nicht weiterverfolgt. Prinzipiell funktioniert sie, wirkt aber noch etwas unfertig. Ich wollte den Code eigentlich noch auf Generics umschreiben, wollte aber auch die Unterstützung für ältere Compiler ohne Generics nicht verlieren. Es stellte sich dann aber leider heraus, dass es selbst mit den cleversten Include-Hacks, die mir einfallen, wohl unmöglich ist, beides gleichzeitig zu supporten, ohne den Code zu duplizieren. Ungefähr da habe ich dann die Lust verloren ;)

Aber wie dem auch sei, ich schmeiße es jetzt einfach mal so wie es ist auf Github: https://github.com/Isopod/ABTrees. Wie gesagt, ich sehe es nicht als fertig an und übernehme keine Gewährleistung, aber vielleicht kann ja jemand was damit anfangen.

In src/abtrees kann man sehen, wie man sich einen eigenen Baum definiert. Wenn du Strings als Keys verwenden willst, müsstest du dann aber wohl TABKey als record definieren und den Vergleichsoperator überladen. Man kann natürlich mehrere Arten von Bäumen in einem Projekt haben, also z.B. einen, der Integers als Keys verwendet, einen, der Strings als Keys verwendet etc., man muss dann nur für jeden eine neue Unit anlegen.

Wichtig zu beachten:
- Ein Key muss eindeutig sein, er darf nicht mehrfach im Baum vorkommen. Das heißt natürlich nicht, dass nicht mehrere Leute „Hans“ mit Vornamen heißen dürfen, man muss sich nur überlegen, wie man den Key definiert. Man könnte z.B. zu dem Record noch eine eindeutige ID hinzufügen, die man vergleicht, wenn die Vornamen gleich sind.
- Seek gibt immer den Eintrag zurück, der am nächsten am gesuchten Key liegt und dessen Key kleiner oder gleich dem gesuchten Key ist. Es ist also kein "Find". Wenn die Einträge im Baum 1, 2, 3, 5, 6 lauten, dann gibt Seek(4) den Eintrag 3 zurück. Wenn man einen ganz bestimmten Eintrag sucht, muss man daher hinterher noch prüfen, ob der Key wirklich gleich ist.

Zitat:

Zitat von stahli (Beitrag 1323959)

Oder ist eine binäre Suche in einer Liste ohnehin fast gleich schnell?

Die Suche an sich ist schnell, aber wenn du viele Einträge löscht oder hinzufügst, könnte es langsam werden, da ja im Schnitt jedes mal die halbe Liste umkopiert wird.

[Dejan Vu]

Wieso speicherst Du die Daten nicht in einer DB, z.B. SQLite? Bei 100k Datensätzen wäre das zumindest eine Alternative.
Wenn Du das allerdings nicht willst, dann würde ich so vorgehen.
1. Die Liste bleibt, wie sie ist.
2. Für jede Sortieroption pflegst Du einen eigenen Index, d.h. einfach eine Liste der Referenzen, in der entsprechenden Sortierreihenfolge. Das kann ein Baum oder eine einfache Liste sein
3. Jede Operation (einfügen, ändern, löschen) bedingt (u.U.), das der Index korrigiert wird.

Dein Index benötigt also zwei Methoden: Remove und Add. Remove entfernt das Element aus dem Index, Add fügt es neu ein.

Deine Datenliste hat mindestens drei Methoden: Remove, Add und Update. Bei 'Remove' rufst Du einfach 'Remove' aller Indexe auf, bei 'Add' einfach 'Add' und bei Update erst 'Remove' und dann 'Add'. Beim Update wird klar, das Du dir den alten und den neuen Wert jeweils merken musst.
Mit dem alten Wert entfernst Du das Element aus allen Indexen und mit dem neuen Wert fügst Du das Element wieder in die Indexe ein.

Na ja, oder eben doch SQLLite, Access, Firebird etc etc etc.

PS: Kann man mit einer Memtable auch Indexe aufbauen? Geht, oder? Dann kann man sich das wirklich alles sparen.

[stahli]

@Namenloser

Danke für die Hilfe.
Ich werde aber doch erst mal eine Liste benutzen, da ich dort auch weiß, was wann wie passiert.
Wen ich es brauche und mir zutraue, schaue ich mir dann mal Deinen Baum an. Die benötigten Funktionen wären dann ja gleich/ähnlich, nur die innere Funktionalität würde dann ja anders ablaufen.

@Deja Vu

Ich habe diverse Interfaces, auf die ich auf unterschiedliche Weisen zugreife. Der Datenzugriff soll immer über Objekte erfolgen.
Ein ORM ist geplant, aber eine Datenbank soll dann auch nur über den ORM angesprochen werden. Der User soll davon letztlich nichts merken.
Kleinere Datenmengen sollen aber nur in Objekten verwaltet werden.

Deine Vorschläge 1-3 sehe ich auch so. Nur, statt Indizes in einer Liste zu sammeln, kann ich auch direkt die Pointer sammeln, sofern alle Objekte persistent im Speicher liegen.
Die gleiche Funktion unter Benutzung eines ORM müsste die Objekt-GUIDs heraus geben, da die Objekte dann anhand der GUID instanziiert werden.

Das Löschen und Einfügen von Objekten in der Hauptliste wird unproblematisch zu berücksichtigen sein. Ich muss dann halt in den angehängten Sortierlisten die Änderungen nachführen. Kein Problem.
Aber wenn ein Vor- oder Nachname eines Personenobjektes geändert wird, dann wird es schon deutlich schwieriger.
Eine Liste kann sich ja schlecht bei 1Mio Objekten als Überwacher anmelden. Dann müssten sich letztlich auch mehrere Listen bei jedem Objekt registrieren können. Ich werde wohl eine zentrale Stelle schaffen, in der sich Listen anmelden können und über Objektänderungen informiert werden. Dann können sie prüfen, ob eins ihrer Einträge von einer Änderung betroffen ist.