Wie festes Dictionary vordefinieren?

[BeniBela]

Cooler Benchmark, aber man muss natürlich auch beachten das TFPDataHashTable und TFPHashList nur pointer als value erlauben. Klar kann man unter x86_64 CPUs auch integer rein schieben, ist aber nicht portable, wirft ne warning und ist, wenn ich das mal so sagen darf, kein sauberer Stil. Um also was anderes als TObjects reinzuschieben, muss man indirection verwenden, was bei TFPGMap oder gHashMap.THashMap nicht der Fall ist. Das kann die benchmarks natürlich beinflussen.

Ja, TFPDataHashTable und TFPHashList sind nur in spezifischen Situationen nützlich, aber dann ist TFPHashList gut.

Die nicht generischen haben aber auch den Vorteil, dass das Programm klein bleibt, statt für jeden Typ den Mapcode neuzugenerieren. Letztendlich unterscheiden sich die Values nur nach Größe und Referenzcounting. Wenn FPC nun schlau kompiliert, könnte es alle 8-Byte Werte (pointer/TObject/int64/...) zusammenmergen und den Assemblercode für die alle nur einmal ausgeben. Ich bezweifel, dass FPC so schlau ist, deshalb verwende ich eine generic-pointer-generic Konstruktion. Ausgehend von einer generischen Map, wird die dann mit pointer Value specialized, und dann kommt eine generische Wrappermapklasse darum, die den Wert zu pointer cast. Das geht selbst mit string, da wird der string zu pointer gecastet und nur die Wrapperklasse aktualisert den Referenzzähler beim Einfügen/Löschen. Das hilft auch bei schlecht programmierten Maps, die womöglich intern Kopien von den Werten machen. Wenn die bei String den Referenzzähler ändert würden, macht das die Performance kaputt

Das nächste ist das keys natürlich mehr als strings sein können. Einen nicht string erst mal zu string serialisieren um dann den lookup zu machen beeinflusst natürlich auch die Zugriffszeit, besonders bei komplexeren datentypen wie records.

Ja das geht auch bei den meisten Maps. Nur muss man sich dann vermutlich noch eine eigene Hashfunktion bauen.

Das macht bei der Implementierung auch Probleme. Da hatte ich eine Map, die nicht funktioniert hat, weil die String/Nicht-String Unterscheidung falsch implementiert war. Und die avk Maps verwenden für die Unterscheidung eine Funktion, die es nur ab FPC 3.2 gibt.

Dann könnte man auch Typen mischen, zum Beispiel String einfügen und als pchar mit Länge auslesen.

Und natürlich ist es auch eine frage was man damit macht. Z.b. wäre es auch interessant wie hoch die geschwindigkeit beim löschen von elementen und drüber iterieren ist. Ich würde vermuten das das drüber iterieren bei TFPGMap deutlich schneller sein sollte als bei den HashMap counterparts.

Das wäre interessant. Sollte mal jemand messen (mein benchmark ist auch open-source), aber dafür habe ich keine Zeit mehr. Das ist auch mehr Aufwand als einfügen/auslesen, weil sich das bei den Maps mehr unterscheidet.

Hashmaps können aber auch schnell iterieren, das hängt davon ab, wie die implementiert sind. Ich habe lange Zeit Bero's FLRE Map verwendet (weil ich sein FLRE sowieso schon für reguläre Ausdrücken verwende und dann keine zusätzliche Library brauche), die speichert alle Key/Wert Daten ganz normal hintereinander in einem Array. Die Hashmap ist dann ein zusätzliches Array, dass für den Hashcode lediglich den Index im Array speichert. Da ist das iterieren optimal.
Zumindest solange nichts gelöscht wird. Löschen ist da ganz blöd, die verwendet ein drittes Array, um zu speichern welche Indizes gelöscht wurden. Die gelöschten Indizes werden dann im Key/Wert-Array nicht mehr verwendet, bis zum nächsten Rehashing.
Das klingt nach einer schlechten Implementierung, doch es läuft schneller als jede FPC Map.

Das gesagt ist so eine übersicht natürlich schon cool. Vor allem weil du auch nicht standard bibliotheken drin hast. Denn TFPDataHashTable und TFPHashList wegen der "string-pointer" zuweisung m.M.n. keine wirkliche alternative darstellt (allein die tatsache das man das Memory-Management für die daten übernhemen muss), sehen die alternativen in den Standardbibliotheken eher mau aus. TFPGMap, gmap.TMap und ghashmap.THashMap sind so wie ich das sehe da die einzigen Optionen die standardmäßig verfügbar sind.

rtl generics sind auch Standardbibliotheken. Vielleicht sogar die einzigen, die echte Pascal Standardbibliotheken sind, weil sie auch Delphi kompatibel sein sollen.

[photor]

Hallo Forum,

meine Anfrage hat sich ja ein bisschen verselbstständigt - gut so

Trotzdem noch eine kurze Rückmeldung meinerseits: so richtig elegant fand ich jetzt keine Lösung für einen festen Zusammenhang zwischen einen Key (einer Zahl) und dem zugehörigen Namen, der einmal zu Beginn des Programms festgelegt werden kann.

Deshalb bin ich letztendlich bei traditionellem Pascal und einer einfachen Funktion mit einem case gelandet; auch nicht elegant, macht aber auch, was es soll. Also etwa sowas in einer Unit, die eh aufgerufen wird:

Code: Alles auswählen

 
function MentatResultPostcode(pcid: integer) : string;
var
  Name : string;
begin
  case pcid of
  1:    Name := '1st Component of strain';
  2:    Name := '2nd Component of strain';
  3:    Name := '3rd Component of strain';
  4:    Name := '4th Component of strain';
  5:    Name := '5th Component of strain';
  6:    Name := '6th Component of strain';
  7:    Name := 'Equivalent plastic strain';
  8:    Name := 'Equivalent creep strain (integral of equivalent creep strain rate)';
  9:    Name := 'Total temperature';
  10:   Name := 'Increment of temperature';
  11:   Name := '1st Component of stress';
  // ... etliche mehr
  421:  Name := 'Elastic strain in global coordinate system';
  431:  Name := 'Plastic strain in global coordinate system';
  441:  Name := 'Creep strain in global coordinate system';
  451:  Name := 'Velocity strains (for fluids)';
  461:  Name := 'Elastic strain in preferred direction';
  else
    Name := '*** illegal postcode ***';
  end;
  Result := Name;
end;
 

Eigentlich wäre ein Dictionary die "richtige" Datenstruktur gewesen - aber wie es aussieht, schlecht im vorhinein zu initialisieren. Und wenn ich dann eh eine Funktion aufrufen muss; und es werden nicht sooo viele Aufrufe sein, dass es zeitkritrisch wird.

Ciao,
Photor

[Winni]

Hi!

Wenn Du mehr klaren Zusammenhang zwischen Key und String haben willst, dann benutze doch ein konstantes array of string.

Etwa so:

Code: Alles auswählen

function MentatResultPostcode(pcid: integer) : string;
const Name : array[1..461] of string = (
                                           '1st Component of strain',
                                           '2nd Component of strain',
                                           '3rd Component of strain',
                                           ......
                                          'Velocity strains (for fluids)',  
                                          'Elastic strain in preferred direction'
                                           );
 
begin
if (pcid >=1) and (pcid<=461) then result := name[pcid] else result := '*** illegal postcode ***';
end;  
 

Ich weiß (immer noch) nicht, wie case intern organisiert ist, aber so hast Du auf jeden Fall direkten Zugriff auf ein array-Element.

Das Wichtige bei diesem Konstrukt ist, dass man Buchführung macht - also quasi das case label als Kommentar dahinter schreibt. Zumindest bei jedem 10.
Der Compiler meckert zwar, wenn nicht die Richtige Anzahl an Konstanten vorhanden ist, aber ohne Buchführung ist das Sklaven-Arbeit!

Winni

[Warf]

Eigentlich wäre ein Dictionary die "richtige" Datenstruktur gewesen - aber wie es aussieht, schlecht im vorhinein zu initialisieren. Und wenn ich dann eh eine Funktion aufrufen muss; und es werden nicht sooo viele Aufrufe sein, dass es zeitkritrisch wird.

Ciao,
Photor

Switch case auf einer mehr oder weniger kontinuierlichen Ordinalen skala (also zahlen von 0-n mit wenigen lücken) sollte sogar sehr effizient sein, da es letzendlich zu einem Array reduziert werden sollte.

Das gesagt kannst du auch einfach bei einer map die daten im konstruktor initialisieren:

Code: Alles auswählen

type
  TMyMap = class(specialized TFPGMap<Integer, String>)
  public
    constructor Create;
  end;
...
 
constructor TMyMap.Create;
begin
  inherited Create;
  sorted := True
  Add(1, 'String 1');
  Add(2, 'String 2');
  ...
end;

und dann wird bei TMyMap.create automatisch die daten rein geladen.

Das gesagt, scheinst du ja grundsätzlich kontinuerliche zahlen zu haben. Da lohnt es sich einfach wirklich einen array zu machen. Was ich z.b. auch gerne mache für solche "Brainless" aufgaben ist es einen code generator zu schreiben, der dann die daten aus einer CSV datei oder so einliest und daraus dann den array (oder auch ein solches switch case) generiert. Diesen array/case kannst du dann in eine .inc datei schreiben und die einfach via {$Include} einbinden.

Vor dem kompilieren dann einfach deinen Generator laufen lassen und zack du hast deinen Code mit minimalem verwaltungsaufwand

[sstvmaster]

so richtig elegant fand ich jetzt keine Lösung für einen festen Zusammenhang zwischen einen Key (einer Zahl) und dem zugehörigen Namen, der einmal zu Beginn des Programms festgelegt werden kann.

In einem Python-Script (das ähnliches tut) habe ich das als Dictionary gelöst:

Und wie hast du das dann mit Phyton gemacht? Dort sind die Daten von alleine im Dictionary gelandet?

[Winni]

Hi!

Eigentlich wollte ich mich nie wieder mit Python beschäftigen.
Nun gut - wenn er das "magische" Python Dictionary immer wieder ins Spiel bringt.

W3 weiss mehr:

https://www.w3schools.com/python/python ... naries.asp

Ein Dictionary ist

is a collection which is unordered, changeable and indexed.

Also ein Sauhaufen, der indiziert wird. Also irgendeine Art von Stringlist mit einem Index.
Das gibt es meines Wissens in Lazarus nicht.

Nun stellt sich die Frage nach den Zugriffsziten.

Falls die unkritsch sind, kann man dann auch Folgendes bauen:
Man baut eine stringlist aus dem Key mit führenden Nullen, einem Leerzeichen und dem String.
Die Stringlist kann man auf sorted setzen, so dass man alles auch unsortiert einlesen kann.

Dann kann man zum Suchen gucken, ob der gesuchte Key als string größer, kleiner oder Teil des verglichenen Strings in der Liste ist.

Dasss muss man nicht sequentiell machen, sondern nach dem binären "Teile und finde" Muster erledigen.

Und photor hat den key und die meldung in einem string. Das hatte er doch immer gesucht.

Winni

[Warf]

Also ein Sauhaufen, der indiziert wird. Also irgendeine Art von Stringlist mit einem Index.
Das gibt es meines Wissens in Lazarus nicht.

Ein dictionary ist in python nicht viel weiter spezifiziert als das man über keys auf values zugreifen kann, und die Operationen eine average case laufzeit von O(1) haben sollen und über eine robuste Hash funktion verfügen sollen (https://wiki.python.org/moin/TimeComplexity). Für Implementationsdetails kann man sich CPython auf GitHub anschauen, die haben für Dicts sogar eine eigene ReadMe: https://github.com/zpoint/CPython-Inter ... ct/dict.md
Dazu sei gesagt das natürlich andere Python implementation das anders machen können, doch ich denke in den aller meisten fällen wird es eine Hashmap sein.

Und hashmaps kann Lazarus/FPC, siehe die Benchmarks von BeniBela. Ein nachteil von Pascal hier ist, man muss seine eigene Hash-Funktion bauen. Python stellt von haus aus eine bereit (wie z.b. auch Java). Für Integer ist das einfach, da kann man einfach den Integer selbst als hash benutzen, und für Komposite typen (Klassen, Records) kann man einfach die Hash kombination aus den Hashen aller Felder benutzen, kombiniert mit einer Magic-Number (primzahlen für robustheit).

Beispiel zum robusten kombinieren:

Code: Alles auswählen

function HashCombine(h1: IntPtr; h2 IntPtr): IntPtr; inline
begin
  Result := ((h1 shl 5) Or (h1 shr (sizeof(h1) * 8 - 5)))
        XOr ((h2 shl 7) Or (h2 shr (sizeof(h2) * 8 - 7)));
end;

Beispiel für einen simplen record wäre dann:

Code: Alles auswählen

TTestRec = record
  Feld1: Integer;
  Feld2: Integer;
  Feld3: Integer;
end;
 
function TestRecHash(const r: TTestRec): IntPtr; inline;
begin
  Result := 883; // Random prime
  Result := HashCombine(Result, r.Feld1);
  Result := HashCombine(Result, r.Feld2);
  Result := HashCombine(Result, r.Feld3);
end;

Und schon kann man diesen Record mit einer HashMap benutzen

[photor]

Wenn Du mehr klaren Zusammenhang zwischen Key und String haben willst, dann benutze doch ein konstantes array of string.

Etwa so:
[...]
Winni

Klappt gut, wenn die Nummern (der Key) keine Löcher hat. Iss aber leider so. Deshalb fällt das leider aus

Und wie hast du das dann mit Phyton gemacht? Dort sind die Daten von alleine im Dictionary gelandet?

In Python kann man das direkt bei der Definition angeben (sehr elegant). Fairerweise: dort war es als Klasse definiert. Darüber will ich nochmal nachsinnen.

Ciao,
Photor

[photor]

Switch case auf einer mehr oder weniger kontinuierlichen Ordinalen skala (also zahlen von 0-n mit wenigen lücken) sollte sogar sehr effizient sein, da es letzendlich zu einem Array reduziert werden sollte.

Das case schien mir erstmal die unkomplizierteste Möglichkeit. Über die Geschwindigkeit und Größe habe ich mir nur wenig Gedanken gemacht.

Das gesagt kannst du auch einfach bei einer map die daten im konstruktor initialisieren:

Code: Alles auswählen

type
  TMyMap = class(specialized TFPGMap<Integer, String>)
  public
    constructor Create;
  end;
...
 
constructor TMyMap.Create;
begin
  inherited Create;
  sorted := True
  Add(1, 'String 1');
  Add(2, 'String 2');
  ...
end;

und dann wird bei TMyMap.create automatisch die daten rein geladen.

TMap kommt dem auch sehr nahe. Und der Definition als Klasse, womit (wie im Python ) das ganze im Konstruktor definiert werden kann. Ja, das gefällt mir. Solange eben auch sowas geht:

Code: Alles auswählen

 
constructor TMyMap.Create;
begin
  inherited Create;
  sorted := True
  Add(1, 'String 1');
  Add(2, 'String 2');
  Add(4, 'String 4');
  Add(25, 'String25');
  ...
end;

Das gesagt, scheinst du ja grundsätzlich kontinuerliche zahlen zu haben. Da lohnt es sich einfach wirklich einen array zu machen. Was ich z.b. auch gerne mache für solche "Brainless" aufgaben ist es einen code generator zu schreiben, der dann die daten aus einer CSV datei oder so einliest und daraus dann den array (oder auch ein solches switch case) generiert. Diesen array/case kannst du dann in eine .inc datei schreiben und die einfach via {$Include} einbinden.

Wie schon erwähnt, sind die Zahlen nicht kontinuierlich (es gibt Löcher und ob die jemals geschlossen werden - oder vielleicht sogar niemals verwendete Paare wieder rausfliegen - die könnte man einfach drin lassen - kann man nicht sagen)

Vor dem kompilieren dann einfach deinen Generator laufen lassen und zack du hast deinen Code mit minimalem verwaltungsaufwand

Dafür, dass das wahrscheinlich alle Jubeljahre mal angepasst werden muss, wäre mir das zuviel Aufwand.

Ciao,
Photor

[Winni]

Hi!

Keine fortlaufende Zählung ist kein Argument:

Code: Alles auswählen

 
const name : array[1..666] of string = (
                                             'eins',
                                             '',
                                             '',
                                             'vier',
                                            'fünf',
                                          .........

Das hab ich bei bei den Fehlermeldungen von BASS.dll genau so gemacht.


Winni

[Warf]

Da stimme ich Winni nur zu, daher meinte ich auch du kannst einen generator dafür benutzen der automatisch das Array erzeugt und in alle fehlenden indices war reinschreibt. Solang jetzt nicht 90% der indizes leer sind sollte das so super funktionieren.
Du könntest z.b. in jeden freien index eine zeile von Goehtes Zaubberlehrling rein stecken, wenn du so viele lücken hast das die nicht mehr ausreichen dann kannst du überlegen dir ne Map zu machen. Außerdem bringts einen immer zum schmunzeln wenn ein Kunde sich meldet weil er einen Bug gefunden hat und dann fragt was die Fehlermeldung "Walle, walle manche Strecke" bedeutet