AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Win32/Win64 API (native code) Delphi Sortierte TObjectList - Einträge richtig einfügen
Thema durchsuchen
Ansicht
Themen-Optionen

Sortierte TObjectList - Einträge richtig einfügen

Ein Thema von Benmik · begonnen am 17. Jul 2015 · letzter Beitrag vom 24. Sep 2015
Antwort Antwort
Seite 1 von 5  1 23     Letzte »    
Benmik

Registriert seit: 11. Apr 2009
560 Beiträge
 
Delphi 12 Athens
 
#1

Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 13:48
Ich habe eine sortierte TObjectList in einer eigenen Klasse. Ich muss nun feststellen, ob ein bestimmtes Element bereits in der Liste vorhanden ist und - wenn nicht - es an der richtigen Stelle einfügen.

Ich habe mir dazu eine quasi aufgebohrte Version von IndexOf mit einer binären Suche gebastelt, die mir bei Nichtfinden in p die richtige Einfügeposition zurückmeldet:
Delphi-Quellcode:
type
  TZiel = class(TObject)
    WERT1 : Word;
    WERT2 : Word;
    WERT3 : String;
    WERT4 : String;
    WERT5 : Cardinal;
    WERT6 : Int64;
    WERT7 : Int64;
  end;
  TZielListe = class(TObjectList)

function TZielListe.WertGefunden(Wert:string;var WertPos:Integer):Boolean;
var p, Anz, MWert: Integer;
begin
  // WertPos ist entweder die Position des gefundenen Wertes oder die Einfügeposition in die sortierte Liste, falls nicht gefunden
  WertPos := 0;
  If Self.Count = 0 then
    exit(False);
  p := 0;
  Anz := Self.Count;
  while p < Anz do
    begin
    MWert := p + (Anz - p) div 2;
    if Self[MWert].Wert3 = Wert then
    begin
      WertPos := MWert;
      Exit(True);
    end;
    if AnsiCompareText(Wert,Self[MWert].Wert3) = -1 then
       Anz := MWert
     else
       p := MWert + 1;
  end;
  If (p = Anz) or (AnsiCompareText(Wert,Self[p].Wert3) > 0) then
    WertPos := p
  else
    WertPos := Max(0,p - 1);
  Result := False;
end;
Jetzt hätte ich dazu einige Fragen:
  1. Kann ich mich darauf verlassen, dass p bei Nichtfinden immer die richtige Einfügeposition zurückliefert oder kann p (abhängig von gerader oder ungerader Gesamtmenge) um einen Eintrag falsch liegen? Ich habe vorsichtshalber eine Korrektur eingebaut (If AnsiCompareText... , ist die nötig / wirksam?
  2. Die Liste hat eine Größenordnung von ca. 10.000 Einträgen. Ab welcher Größe ungefähr ist ein Neusortieren deutlich langsamer als ein Einfügen?
  3. Geht eigentlich ein Neusortieren deutlich schneller, wenn die Liste bis auf einen Eintrag bereits richtig sortiert ist?
  4. Ich muss TZiel nach verschiedenen Werten (Text,Zahl) finden / einsortieren. Wie mache ich das am besten? Mehrere Listen erzeugen, die nach dem gewünschten Wert sortieren und neue Einträge in jede Liste an der jeweils richtigen Position einfügen (klingt irgendwie alles schon nicht so gut)?

Danke!

Geändert von Benmik (17. Jul 2015 um 14:41 Uhr) Grund: Code verbessert
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 14:48
Welche Delphi-Version nutzt Du denn?
(Solltest Du mal in Deinem Profil einstellen.)

Wenn es eine aktuelle mit Generics und einem TComparer ist dann wird das Ganze vielleicht etwas einfacher zu lösen sein.
Ein Bsp. mal hier: http://www.delphipraxis.net/1231518-post34.html
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benmik

Registriert seit: 11. Apr 2009
560 Beiträge
 
Delphi 12 Athens
 
#3

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:00
Ja, wollt ich schon immer mal einstellen, ist hiermit geschehen. D2009. Generics gibts also, aber BinarySearch und TComparer offenbar noch nicht.
  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
 
#4

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:05
Doch in der Unit Generics.Defaults
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
Benmik

Registriert seit: 11. Apr 2009
560 Beiträge
 
Delphi 12 Athens
 
#5

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:14
In der Tat!

Aber ach, Generics... ! MUSS DAS SEIN? Ich weiß natürlich, für die meisten hier sind das Pheromone...
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:18
Muss nicht sein.
Aber gerade für typisierte Listen ist das ganz komfortabel.

Die ganzen anderen Schweinereien mit generischen Klassen usw. vermeide ich auch lieber. Aber generische Listen sind schon nett (und unkompliziert).
Lediglich das schrittweise debuggen ist dann etwas seltsam (m.E.).
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)
  Mit Zitat antworten Zitat
Benmik

Registriert seit: 11. Apr 2009
560 Beiträge
 
Delphi 12 Athens
 
#7

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:31
Auf der anderen Seite liefert BinarySearch so ziemlich genau das, was ich will:
Zitat:
The method returns true if it finds the element and false otherwise. If found, Index contains the zero-based index of Item. If not found, Index contains the index of the first entry larger than Item.
Perfekt wär's, wenn das auch noch wär (was es aber nicht ist):
Zitat:
If there is more than one element in the list equal to Item, the index of the first match is returned in Index. This is the index of any of the matching items, not necessarily the first.
Aber sonst ziemlich genau das, was ich nachgebaut habe. Muss doch wohl meine erste generische Liste in Angriff nehmen.

Vielleicht noch eine Idee zu den anderen Fragen?
  Mit Zitat antworten Zitat
Benutzerbild von stahli
stahli

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

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:48
Gute Entscheidung.
Generische Listen werden Dir hier helfen.

Du musst nur einen TComparer definieren, der Dir kleiner, gleich oder größer zu Deinen Items zurück liefert. Den Rest kannst Du der Binärsuchfunktion überlassen.

Eine Neusortierung musst Du eigentlich gar nicht machen, da Du jeden Eintrag direkt an die passende Stelle einsortieren kannst.
(Im Nachhinein bin ich nur nicht sicher, ob Extract aus meinem Beispiel vorhin die binäre Suche benutzt. Sonst müsste man eben explizit binär suchen und den Eintrag an dem gefundenen Index entfernen.)


Für unterschiedliche Sortierungen (nach Eigenschaft A oder B) habe ich keine Lösung parat.
Man könnte den Comparer unterschiedlich steuern (case ... of) und müsste die Liste dann aber bei einer Umschaltung komplett umsortieren.
Oder man verwaltet mehrere Listen mit Objektreferenzen und sortiert die binär verschieden. Muss man halt immer alle synchron halten und Einträge immer in allen einfügen bzw. entfernen.
Die beste Lösung hängt sicher vom Einzelfall ab. Wenn man sich eine Factory baut, die das Einfügen und Entfernen zentral übernimmt, kann die das synchronisieren der Listen natürlich schön automatisieren.

Ganz nützlich kann auch ein Dictionary sein, was idR. noch schneller als eine binäre Liste funktioniert.


Zu Listentypen will ich gleich nochmal auf meinen kürzlichen Link zu Video2Brain verweisen ... hierin: http://www.delphipraxis.net/1308861-post28.html
Die Trainerin fasst das m.E. ganz gut zusammen.
Stahli
http://www.StahliSoft.de
---
"Jetzt muss ich seh´n, dass ich kein Denkfehler mach...!?" Dittsche (2004)

Geändert von stahli (17. Jul 2015 um 15:50 Uhr)
  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
 
#9

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:49
Delphi-Quellcode:
uses
  Generics.Collections,
  Generics.Defaults;

type
  TZiel = class(TObject)
    WERT1 : Word;
    WERT2 : Word;
    WERT3 : String;
    WERT4 : String;
    WERT5 : Cardinal;
    WERT6 : Int64;
    WERT7 : Int64;
  end;

  TZielListe = class( TObjectList<TZiel> )
  private
    function Compare( const L,R: TZiel) : Integer;
  public
    constructor Create( OwnsObjects: Boolean = true );
  end;

function TZielListe.Compare( const L,R: TZiel) : Integer;
begin
  Result := TComparer<string>.Default.Compare( L.Wert3, R.Wert3 );
end;

constructor TZielListe.Create( OwnsObjects: Boolean );
begin
  inherited Create( TComparer<TZiel>.Construct( Compare ), OwnsObjects );
end;
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
Benmik

Registriert seit: 11. Apr 2009
560 Beiträge
 
Delphi 12 Athens
 
#10

AW: Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 15:57
Danke euch beiden! Sensationell.

Schließe mich dem an: Kaum macht man's richtig - schon funktioniert's.
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 5  1 23     Letzte »    

 

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 10:38 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