AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Delphi Ich habe eine Liste, und die soll bitte immer sortiert sein
Thema durchsuchen
Ansicht
Themen-Optionen

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

Ein Thema von Der schöne Günther · begonnen am 14. Jan 2014 · letzter Beitrag vom 11. Dez 2015
Antwort Antwort
Seite 2 von 3     12 3      
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.343 Beiträge
 
Delphi 11 Alexandria
 
#11

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

  Alt 20. Jan 2014, 00:16
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.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Namenloser

Registriert seit: 7. Jun 2006
Ort: Karlsruhe
3.724 Beiträge
 
FreePascal / Lazarus
 
#12

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

  Alt 20. Jan 2014, 01:29
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.

Geändert von Namenloser (20. Jan 2014 um 01:35 Uhr)
  Mit Zitat antworten Zitat
Furtbichler
(Gast)

n/a Beiträge
 
#13

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

  Alt 20. Jan 2014, 07:14
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?

Geändert von Furtbichler (20. Jan 2014 um 07:26 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.343 Beiträge
 
Delphi 11 Alexandria
 
#14

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

  Alt 10. Dez 2015, 13:24
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).
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benutzerbild von Sir Rufo
Sir Rufo

Registriert seit: 5. Jan 2005
Ort: Stadthagen
9.454 Beiträge
 
Delphi 10 Seattle Enterprise
 
#15

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

  Alt 10. Dez 2015, 15:17
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.
Kaum macht man's richtig - schon funktioniert's
Zertifikat: Sir Rufo (Fingerprint: ‎ea 0a 4c 14 0d b6 3a a4 c1 c5 b9 dc 90 9d f0 e9 de 13 da 60)
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.343 Beiträge
 
Delphi 11 Alexandria
 
#16

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

  Alt 10. Dez 2015, 15:30
... 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?
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
mm1256

Registriert seit: 10. Feb 2014
Ort: Wackersdorf, Bayern
642 Beiträge
 
Delphi 10.1 Berlin Professional
 
#17

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

  Alt 10. Dez 2015, 18:25
...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.
Gruss Otto PS: Sorry wenn ich manchmal banale Fragen stelle. Ich bin Hobby-Programmierer und nicht zu faul die SuFu zu benutzen
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.343 Beiträge
 
Delphi 11 Alexandria
 
#18

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

  Alt 10. Dez 2015, 18:33
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.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benutzerbild von Stevie
Stevie

Registriert seit: 12. Aug 2003
Ort: Soest
4.027 Beiträge
 
Delphi 10.1 Berlin Enterprise
 
#19

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

  Alt 10. Dez 2015, 18:36
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.
Stefan
“Simplicity, carried to the extreme, becomes elegance.” Jon Franklin

Delphi Sorcery - DSharp - Spring4D - TestInsight
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

Registriert seit: 26. Nov 2003
Ort: Halle/Saale
4.343 Beiträge
 
Delphi 11 Alexandria
 
#20

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

  Alt 10. Dez 2015, 18:54
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.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 2 von 3     12 3      

 

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 12:00 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz