Wie festes Dictionary vordefinieren?

Für Fragen zur Programmiersprache auf welcher Lazarus aufbaut
Benutzeravatar
photor
Beiträge: 209
Registriert: Mo 24. Jan 2011, 21:38
OS, Lazarus, FPC: Arch Linux (L 2.0.10 FPC 3.2.0)
CPU-Target: 64Bit

Wie festes Dictionary vordefinieren?

Beitrag von 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
Beiträge: 348
Registriert: Sa 22. Okt 2016, 23:12
OS, Lazarus, FPC: OS: Windows 10 | Lazarus: 2.0.8 + Fixes + Trunk 32bit
CPU-Target: 32Bit
Wohnort: Dresden

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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
LG Maik

Benutzeravatar
photor
Beiträge: 209
Registriert: Mo 24. Jan 2011, 21:38
OS, Lazarus, FPC: Arch Linux (L 2.0.10 FPC 3.2.0)
CPU-Target: 64Bit

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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
Beiträge: 394
Registriert: Mo 2. Mär 2009, 16:45
OS, Lazarus, FPC: Laz2.06, fpc 3.04
CPU-Target: 64Bit
Wohnort: Fast Dänemark

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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

Benutzeravatar
af0815
Lazarusforum e. V.
Beiträge: 4256
Registriert: So 7. Jan 2007, 10:20
OS, Lazarus, FPC: FPC fixes Lazarus fixes per fpcupdeluxe (win,linux,raspi)
CPU-Target: 32Bit (64Bit)
Wohnort: Niederösterreich
Kontaktdaten:

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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.
Blöd kann man ruhig sein, nur zu Helfen muss man sich wissen (oder nachsehen in LazInfos/LazSnippets).

Benutzeravatar
six1
Beiträge: 216
Registriert: Do 1. Jul 2010, 19:01

Re: Wie festes Dictionary vordefinieren?

Beitrag von six1 »

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

Edit: geht nicht, sind ja keine fortlaufenden Nummern...
Zuletzt geändert von six1 am Fr 17. Apr 2020, 12:53, insgesamt 1-mal geändert.
Gruß, Michael

sstvmaster
Beiträge: 348
Registriert: Sa 22. Okt 2016, 23:12
OS, Lazarus, FPC: OS: Windows 10 | Lazarus: 2.0.8 + Fixes + Trunk 32bit
CPU-Target: 32Bit
Wohnort: Dresden

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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
 
LG Maik

Benutzeravatar
fliegermichl
Lazarusforum e. V.
Beiträge: 642
Registriert: Do 9. Jun 2011, 09:42
OS, Lazarus, FPC: Winux (L 2.0.7 FPC 3.04)
CPU-Target: 32/64Bit
Wohnort: Echzell

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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
Beiträge: 1487
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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.

Benutzeravatar
theo
Beiträge: 8452
Registriert: Mo 11. Sep 2006, 19:01

Re: Wie festes Dictionary vordefinieren?

Beitrag von theo »

fliegermichl hat geschrieben: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.

Benutzeravatar
fliegermichl
Lazarusforum e. V.
Beiträge: 642
Registriert: Do 9. Jun 2011, 09:42
OS, Lazarus, FPC: Winux (L 2.0.7 FPC 3.04)
CPU-Target: 32/64Bit
Wohnort: Echzell

Re: Wie festes Dictionary vordefinieren?

Beitrag von fliegermichl »

Ah, Danke, das hatte ich übersehen.

Benutzeravatar
fliegermichl
Lazarusforum e. V.
Beiträge: 642
Registriert: Do 9. Jun 2011, 09:42
OS, Lazarus, FPC: Winux (L 2.0.7 FPC 3.04)
CPU-Target: 32/64Bit
Wohnort: Echzell

Re: Wie festes Dictionary vordefinieren?

Beitrag von 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
Beiträge: 348
Registriert: Sa 22. Okt 2016, 23:12
OS, Lazarus, FPC: OS: Windows 10 | Lazarus: 2.0.8 + Fixes + Trunk 32bit
CPU-Target: 32Bit
Wohnort: Dresden

Re: Wie festes Dictionary vordefinieren?

Beitrag von sstvmaster »

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

Warf
Beiträge: 1487
Registriert: Di 23. Sep 2014, 17:46
OS, Lazarus, FPC: MacOS | Win 10 | Linux
CPU-Target: x86_64
Wohnort: Aachen

Re: Wie festes Dictionary vordefinieren?

Beitrag von Warf »

fliegermichl hat geschrieben: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.

Benutzeravatar
fliegermichl
Lazarusforum e. V.
Beiträge: 642
Registriert: Do 9. Jun 2011, 09:42
OS, Lazarus, FPC: Winux (L 2.0.7 FPC 3.04)
CPU-Target: 32/64Bit
Wohnort: Echzell

Re: Wie festes Dictionary vordefinieren?

Beitrag von fliegermichl »

Warf hat geschrieben: 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.

Antworten