einem string einen Wert zuweisen (bzw. schnell suchen)

[mulcheo]

Hallo zusammen,

Folgendes: Ich habe eine größere Objectlist, in der ich Daten in Form einzelner Objekte ablege (im Grunde ist das eine Vokabelliste). Zusätzlich habe ich einen abermals recht großen Text, den ich in strings zerlege. Ich weiß, dass es zu jedem string genau ein Objekt gibt, das diesen enthält. Nun möchte ich dieses Objekt möglichst schnell finden, bzw. auf dessen übrige Daten zugreifen.

ein traditionelles Durchscannen nach Schema: for i:=0 to Count(ObjectList) usw. ist mir definitiv zu langsam, da ich die Funktion ständig brauche, so dass sich das ganze Gesuche fix aufsummiert und zu untragbaren Laufzeiten führt

Lieb wäre es mir, wenn ich einem string einmalig (idealerweise beim Laden der ObjectListe) einen Wert (nämlich den Index für die oben erwähnte Objectlist) zuweisen könnte, so dass ich später über den string direkt auf diesen Wert zugreifen kann, ohne jedesmal eine Suchroutine laufen lassen zu müssen.

Oder anders ausgedrückt: Ich suche quasi das Gegenstück zu einem 'Zeugs: array[1..999999] of string', Dort kann ich ja ohne Suche auf den string zu Wert 12345 zugreifen, indem ich bspw. 'mystring:=Zeugs[12345]' verwende... Ich will nun (möglichst ohne Suche, alternativ mit sehr schneller Suche) sowas wie i:=Zeugs[mystring] haben.

welche Optionen habe ich?

[Frank Ranis]

Hallo mulcheo ,

nimm doch tstrings.indexof.

Code: Alles auswählen

unit Unit1;

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls;

type

  { TForm1 }

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Label1: TLabel;
    Label2: TLabel;
    Label3: TLabel;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
  private

  public

  end;

var
  Form1: TForm1;

implementation

{$R *.lfm}

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);
begin
 memo1.clear;
 Memo1.lines.add('Berta');
 Memo1.lines.add('Penelopee');
 Memo1.lines.add('Klara');
 Memo1.lines.add('Otto');
 Memo1.lines.add('Kalle');
 Memo1.lines.add('Fritz');
end;

procedure TForm1.Button2Click(Sender: TObject);
var s:string;
    index:integer;
begin
 s:=edit1.text;
 index:=memo1.Lines.IndexOf(s);
 edit2.text:=inttostr(index);
end;

end.         

[mulcheo]

soweit ich es sehe, macht indexof aber auch nichts weiter als eine sequentielle Suche durch die gesamte Stringlist und das ist ja gearde der zeitfressende part, den ich vermeiden will. Wenn die Liste sortiert ist, läuft die Suche nach meiner Recherche schneller (via binary cut, glaube ich) aber dann gibt mir der Index natürlich kein sinnvolles Ergebnis mehr.

Code: Alles auswählen

var
  Liste: TStringList;
  myWert: integer;
  s,mystring: string;


Liste.AddPair(mystring,IntToStr(myWert));
// code
Liste.sort;
s:=Liste.ValueFromIndex(Liste.indexof(mystring));
myWert:=StrToInt(s);

ist ein workaround, über den ich nachgedacht habe, aber dann habe ich wieder mehrere StrToInt() bzw. IntToStr() im code, was suboptimal ist (AddPair arbeitet mit strings);

[PascalDragon]

welche Optionen habe ich?

Du könntest dir mal fgl.TFPGMapObject<,> oder Generics.Collections.TDictionary<,> anschauen (beide arbeiten mit Hashlisten des Key Typparameters):

Code: Alles auswählen

{$mode objfpc}{$H+}

type
  TVokabelInfo = class
    // was auch immer
  end;
  
  TVokabelListe = specialize TFPGMapObject<String, TVokabelInfo>;
  
var
  vl: TVokabelListe;
begin
  vl := TVokabelListe.Create;
  try
    vl.Add('Foobar', TVokabelInfo.Create);
    vl.Add('Blubb', TVokabelInfo.Create);
    
    Writeln(vl.IndexOf('Blubb'));
    Writeln(vl.IndexOf('Whatever'));
    
    v := vl['Foobar'];
    // was auch immer
  finally
    vl.Free;
  end;
end.

[theo]

@PascalDragon: Danke für das Beispiel, das kann ich bestimmt auch mal gebrauchen.
Ist wahrscheinlich eine optimale Lösung für das Problem.

Code: Alles auswählen

uses fgl;

braucht es noch.

[fliegermichl]

Zu erwähnen wäre auch noch, daß vl.sorted auf true gesetzt werden sollte, da ansonsten auch sequenziell gesucht wird.

[fliegermichl]

Ich schätze, daß ich dieses specialize noch nicht so ganz durchschaut habe.
Kann ich nach der Zuweisung von v := vl['foobar'] auf den String 'foobar' zugreifen?

[theo]

Ich schätze, daß ich dieses specialize noch nicht so ganz durchschaut habe.
Kann ich nach der Zuweisung von v := vl['foobar'] auf den String 'foobar' zugreifen?

Auf das Objekt: Ja.
Sowas geht:

Code: Alles auswählen

 Caption:=vl['Foobar'].fTest;          

Wobei testweise

Code: Alles auswählen

type
  TVokabelInfo = class
    public
      fTest:String;
  end;    

[theo]

@PascalDragon: Bist du sicher, dass TFPGMapObject Hashlisten hält?
In Unit fgl finde ich keinen Hinweis darauf.
in Generics.Collections ist viel von "Hash" die Rede.

[fliegermichl]

Das ist klar, dann muß der String aber doppelt gespeichert werden. 'foobar' muß dann ja an v.fTest zugewiesen werden.
Ich dachte eher an so etwas wie writeln(vl[v].Key);

[theo]

Das ist klar, dann muß der String aber doppelt gespeichert werden. 'foobar' muß dann ja an v.fTest zugewiesen werden.
Ich dachte eher an so etwas wie writeln(vl[v].Key);

Ich weiss es auch nicht und es würde mich auch interessieren.
Es hängt aber mMn mit der Hash Frage zusammen.
Wenn der String nur als Identifikator herhalten muss, kann man ihn auch in einen Hash umwandeln und muss ihn als String gar nicht speichern.
Wie gesagt, ich verstehe davon nicht viel, aber das wäre für mich logisch und speicher-effizient.

An sich macht es ja wenig Sinn, den String, den ich schon habe noch mal von vl zurückzubekommen.

[PascalDragon]

Code: Alles auswählen

uses fgl;

braucht es noch.

Stimmt...

Zu erwähnen wäre auch noch, daß vl.sorted auf true gesetzt werden sollte, da ansonsten auch sequenziell gesucht wird.

Stimmt auch

@PascalDragon: Bist du sicher, dass TFPGMapObject Hashlisten hält?
In Unit fgl finde ich keinen Hinweis darauf.
in Generics.Collections ist viel von "Hash" die Rede.

Grad nochmal nachgeschaut, und ja, es TFPGMapObject<,> nutzt keine Hashes, aber durch die Sortierung kann es eine binäre Suche machen, was die Sache auch beschleunigt im Vergleich zu einer linearen Suche durch die ganze Liste.

Das ist klar, dann muß der String aber doppelt gespeichert werden. 'foobar' muß dann ja an v.fTest zugewiesen werden.
Ich dachte eher an so etwas wie writeln(vl[v].Key);

Wenn du den Index deines Wertes weißt, dann kannst du ihn mittels vl.Keys[idx] abfragen. Ein umgekehrtes Mapping gibt es nicht, da der Data-Wert mehrfach verwendet werden könnte. Aber wenn du deinen Key-Wert eh schon hast, brauchst du ihn nicht nochmal abfragen. Du musst ihn halt dann an eventuelle Funktionen mit weiterreichen oder ihn im Objekt selbst mit abspeichern (solange du den gleichen Stringwert sowohl für den Key als auch das Feld in den Daten verwendest, ist sein Inhalt auch nicht doppelt im Speicher, da Strings ja Copy-On-Write sind; du hast also nur einen zusätzlichen Pointer als Overhead).

[theo]

Weil mich das mit der Hashlist jetzt doch noch interessiert hat und ich nicht direkt ein Beispiel für TDictionary gefunden habe, hier ein Test.
Ist das richtig angewandt?

Code: Alles auswählen

uses
...Generics.Collections;   
...

type

  { TVokabelInfo }

  TVokabelInfo = class
  private
    fTest: string;
  public
    constructor Create(ATest: string);
    property Test: string read fTest write fTest;
  end;

  TVokabelDict = class(specialize TDictionary<string, TVokabelInfo>);
.....

constructor TVokabelInfo.Create(ATest: string);
begin
  inherited Create;
  fTest := ATest;
end;

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);
var
  VokDict: TVokabelDict;
begin
  VokDict := TVokabelDict.Create;
  VokDict.Add('eins', TVokabelInfo.Create('Test_1'));
  VokDict.Add('zwei', TVokabelInfo.Create('Test_2'));
  ShowMessage(VokDict.Items['zwei'].Test);
  VokDict.Free;
end;    

Gibt es noch einen Trick, wie man die Objekte freigibt? Mit "doOwnsValues" bin ich nicht schlau geworden.

[theo]

Habe mittlerweile einen Weg gefunden, die Objekte freizugeben.
Scheint mir aber etwas umständlich und ist für mich ein Blindflug.
Immerhin ist heaptrace so zufrieden.
Gibt es andere Möglichkeiten? Gibt es Beispiele für TDictionary?

Code: Alles auswählen

uses ..., Generics.Collections;

...
type

  { TVokabelInfo }

  TVokabelInfo = class
  private
    fTest: string;
  public
    constructor Create(ATest: string);
    property Test: string read fTest write fTest;
  end;

  TMyPair = specialize TPair<string, TVokabelInfo>;

  TVokabelDict = class(specialize TDictionary<string, TVokabelInfo>);

...
{ TVokabelInfo }

constructor TVokabelInfo.Create(ATest: string);
begin
  inherited Create;
  fTest := ATest;
end;

{ TForm1 }

procedure TForm1.Button1Click(Sender: TObject);
var
  VokDict: TVokabelDict;
  Vi: TMyPair;
begin
  VokDict := TVokabelDict.Create;
  VokDict.Add('eins', TVokabelInfo.Create('Test_1'));
  VokDict.Add('zwei', TVokabelInfo.Create('Test_2'));
  ShowMessage(VokDict.Items['zwei'].Test);
  for Vi in VokDict do Vi.Value.Free; //Freigabe
  VokDict.Free;
end; 

[PascalDragon]

Gibt es noch einen Trick, wie man die Objekte freigibt? Mit "doOwnsValues" bin ich nicht schlau geworden.

Du musst ein TObjectDictionary<,>, statt nur TDictionary<,> verwenden und dann im Konstruktor [doOwnsValues] als Parameter übergeben.