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

[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 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

[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 inherited; gefolgt vom Sort; und natürlich, während des inherited, die Sortierung vom Notify deaktivieren.


Und vergiß nicht, beim Aufruf von 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).