Wie festes Dictionary vordefinieren?

[photor]

Hallo Forum,

ich habe eine Frage, welche Datenstruktur ich am besten für folgendes nehme:
Es gibt quasi eine feste Tabelle bestehend aus einer Zahl (Integer/Cardinal würde auch gehen) und einem zugeordenten Namen (String). Bei der Zahl handelt es sich um eine Code-Nummer, die einen Datenabschnitt (sogenannter Postcode) kennzeichnet; der Name ist einfach gedacht, damit der Mensch besser erkennt, mit was für Daten er es zu tun hat). Die Zuordnung passiert immer Nummer --> Name (niemals in die andere Richtung). Es gibt ca 200 solcher Paare, die sich auch während des Programmablaufs nicht ändern (sind so vorgegeben; wenn sich was ändern sollte, kann man es einfach nachpflegen); ich würde die daher gerne (eventuell als const) definieren.

In einem Python-Script (das ähnliches tut) habe ich das als Dictionary gelöst: die Nummer ist der Key über den auf den Namen zugegriffen werden kann. Bloß wie mache ich das unter Lazarus/FPC (und Delphi) am günstigsten?

• Ein Dictionary kann man natürlich als Variable definieren, muss die aber anschließend per Procedure/Function füllen (ich habe zumindest nicht gefunden, wie man das quasi vordefiniert). Aber man könnte wenigstens über den Key direkt an den Namen kommen.
• Eventuell würde auch eine Tabelle funktionieren, aber dann habe ich ein ähnliches Problem
• Array? Aber der Zugriff müsste dann dadurch erfolgen, dass man das ganze Array abklappert und den Key vergleicht - nicht sehr elegant! (gilt auch für die Tabelle).
• Eine Funktion in der direkt eine große case-Struktur den Namen als RETURN-Wert liefert.

Vielleicht hat ja noch jemand eine Idee; gibt es noch eine andere Möglichkeit? Was wäre das eleganteste/beste/schnellste (Geschwindigkeit ist aber nicht kritisch)?

Danke für jede Anregung - und bleibt gesund,
Photor

[sstvmaster]

Hi Photor,

du sagst mit Phyton machst du es so:

... die Nummer ist der Key über den auf den Namen zugegriffen werden kann.

Dann wäre ein array doch das richtige?

Code: Alles auswählen

 
...
const
  TMyDictionary: array [0..3] of string = ('Wort1', 'Wort2', 'Wort3', 'Wort4'); // array [0..199] of string = ('Wort1, ..., 'Wort200');
...
  WriteLn(TMyDictionary[0]); // Schreibt Wort1
...
 

Damit musst du doch garn nicht das ganze array durchlaufen oder willst du nach dem Wort suchen?

LG Maik

[photor]

Moin sstvmaster,

das würde funktionieren, wenn die Nummern (der Key) aus fortlaufenden Nummern bestehen würde (und damit direkt als Index für das Array dienen kann). Das ist leider nicht der Fall (habe ich im Post oben so nicht gesagt; sorry - vergessen).

Daher ja das Dictionary in Python mit der freien Zuordnung über den Key zum Namen (und eigentlich halte ich das auch in Pascal für die "richtige" Struktur; bloß, wie initialisiere ich das am elegantesten).

Ciao,
Photor

[Winni]

Hi!

Na, trivial geht das so:

Code: Alles auswählen

 
Type 
TEntry = record
               Key: integer;
               Who:  string;
              end; 
 
var
Dictionary : array[0..199] of TEntry;
 
 

Dabei musst Du natürlich das array abklappern, bis der passende Wert gefunden ist.
Aber wir haben ja schnelle Rechner.

Nicht elegant, aber einfach.

Winni

[af0815]

Siehe https://forum.lazarus.freepascal.org/in ... ic=39872.0

TMap oder TDictonary in fgl oder generics, je nach FPC Version

Die Version von Winni hat auch was für sich. Stringlist geht auch, da man den Key ja mit Boxing in einem TObject verstecken kann. Aber das durch iterieren wird dir nicht erspart bleiben.

[six1]

Eine Stringlist käme vielleicht auch in Frage. (TStrings auch in Combobox, Listbox)

Edit: geht nicht, sind ja keine fortlaufenden Nummern...

[sstvmaster]

Oder vieleicht auch das:

Code: Alles auswählen

 
unit Unit1;
 
{$mode objfpc}{$H+}
 
interface
 
uses
  Classes, SysUtils, Forms, Controls, Graphics, Dialogs;
 
type
 
  { TForm1 }
 
  TForm1 = class(TForm)
    procedure FormCreate(Sender: TObject);
  private
 
  public
 
  end;
 
var
  Form1: TForm1;
 
implementation
 
uses
  contnrs;
 
{$R *.lfm}
 
{ TForm1 }
 
procedure TForm1.FormCreate(Sender: TObject);
var
  Dictionary : TFPStringHashTable;
begin
  Dictionary := TFPStringHashTable.Create;
  try
    Dictionary.Add('key1', 'Wort1');
    Dictionary.Add('key2', 'Wort2');
    Dictionary.Add('key3', 'Wort3');
    Dictionary.Add('key4', 'Wort4');
 
    // Key based access to the strings in the hash table
    ShowMessage(Dictionary.Items['key1']);
 
  finally
    Dictionary.Free;
  end;
 
end;
 
end.  
 

[fliegermichl]

Hmm,
Projekt kompilieren, Modus: Debug_Win64, Ziel: C:\Users\michael\development\projects\project1.exe: Exit code 1, Fehler: 9
unit1.pas(33,16) Error: Identifier not found "TFPStringHashTable"
unit1.pas(33,34) Error: Error in type definition
unit1.pas(35,17) Error: Identifier not found "TFPStringHashTable"
unit1.pas(37,16) Error: Illegal qualifier
unit1.pas(38,16) Error: Illegal qualifier
unit1.pas(39,16) Error: Illegal qualifier
unit1.pas(40,16) Error: Illegal qualifier
unit1.pas(43,28) Error: Illegal qualifier
unit1.pas(46,16) Error: Illegal qualifier

[Warf]

TFPGMap<Integer, String> mit sorted auf true gesetzt hat eine lookup Laufzeit von log(n) und einen speicherverbrauch von n

Alternativ TMap aus der gmap unit implementiert das ganze soweot ich weiss über einen rbt, was etwas performanter sein kann.

[theo]

Hmm,
Projekt kompilieren, Modus: Debug_Win64, Ziel: C:\Users\michael\development\projects\project1.exe: Exit code 1, Fehler: 9
unit1.pas(33,16) Error: Identifier not found "TFPStringHashTable"

sstvmaster hat doch geschrieben

Code: Alles auswählen

uses
  contnrs;

Generell kannst du in so einem Fall mit Rechtsclick auf die Fehlermeldung gehen und dann "Suche Bezeichner" auswählen.
Dann wird dir die Unit auch angezeigt.

[fliegermichl]

Ah, Danke, das hatte ich übersehen.

[fliegermichl]

Diese Routine iteriert aber auch über alle Einträge bis es den gesuchten Wert findet. Das kann sehr lange dauern.
Ich habe mir für solche Fälle eine Klasse gebaut, die auf TList basiert. Da die Einträge nach der Nummer sortiert sind, kann man einen Algorithmus "Suchen in sortierten Listen" verwenden.

Dabei werden zwei Indizes verwendet. Einer ist "h" für den größten aktuellen Eintrag und einer "l" für den kleinsten.
l wird mit 0 initialisiert und h mit count - 1.
Eine weitere Variable "c" beinhaltet die aktuelle Position und wird genau in der Mitte initialisiert.

Dann vergleicht die Routine den Wert auf den c zeigt. Ist der gefundene Wert größer als der gesuchte, können alle größeren Einträge ignoriert werden und h wird auf c-1 gesetzt.
Ist der gefundene Eintrag kleiner als der gesuchte, werden alle kleineren Werte verworfen und l auf c+1 gesetzt.

Dieses Spiel wiederholt sich solange bis entweder der richtige Eintrag gefunden wurde oder eben nicht.

Bei dieser Methode bedarf es selbst bei mehreren Millionen Einträgen kaum mehr als 10 bis 12 Vergleiche.

[sstvmaster]

@Photor
Ist es das was du unter Python benutzt? -> https://www.w3schools.com/python/python ... naries.asp

[Warf]

Diese Routine iteriert aber auch über alle Einträge bis es den gesuchten Wert findet. Das kann sehr lange dauern.
Ich habe mir für solche Fälle eine Klasse gebaut, die auf TList basiert. Da die Einträge nach der Nummer sortiert sind, kann man einen Algorithmus "Suchen in sortierten Listen" verwenden.

Dabei werden zwei Indizes verwendet. Einer ist "h" für den größten aktuellen Eintrag und einer "l" für den kleinsten.
l wird mit 0 initialisiert und h mit count - 1.
Eine weitere Variable "c" beinhaltet die aktuelle Position und wird genau in der Mitte initialisiert.

Dann vergleicht die Routine den Wert auf den c zeigt. Ist der gefundene Wert größer als der gesuchte, können alle größeren Einträge ignoriert werden und h wird auf c-1 gesetzt.
Ist der gefundene Eintrag kleiner als der gesuchte, werden alle kleineren Werte verworfen und l auf c+1 gesetzt.

Dieses Spiel wiederholt sich solange bis entweder der richtige Eintrag gefunden wurde oder eben nicht.

Bei dieser Methode bedarf es selbst bei mehreren Millionen Einträgen kaum mehr als 10 bis 12 Vergleiche.

Kurz gesagt du hast dir im grunde ein hashset gebaut bei dem der Hash der startbuchstabe ist und die buckets sortiert sind. Gute Idee, aber damit hast du wohl das Rad neu erfunden, das gibts schon (ist aber ja nix schlechtes, ich finds immer toll zu sehen wenn andere, womöglich schlauere leute als ich, auf die selbe idee kamen, d.h. das die Idee gut ist).
Ich persönlich benutze meist entweder TStringList für strings oder TFPGMap für maps/generisches. Ist zwar "nur" sortiert, aber logaritmische laufzeit, sind bei 1 mio einträgen trozdem nur 20 Vergleiche.

[fliegermichl]

aber damit hast du wohl das Rad neu erfunden, das gibts schon

Schon möglich, ich hab das allerdings schon vor ca. 25 Jahren gemacht. Keine Ahnung, ob es sowas damals schon gab. Erfunden hatte ich den Algorithmus nicht. Das hatte ich aus einem Buch. Ich hab's eben nur praktisch umgesetzt.