Einzelnen Beitrag anzeigen

Benmik

Registriert seit: 11. Apr 2009
486 Beiträge
 
Delphi 10.4 Sydney
 
#1

Sortierte TObjectList - Einträge richtig einfügen

  Alt 17. Jul 2015, 12: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 13:41 Uhr) Grund: Code verbessert
  Mit Zitat antworten Zitat