Immutable Maps und Sets

Zur Vorstellung von Komponenten und Units für Lazarus
Antworten
BeniBela
Beiträge: 308
Registriert: Sa 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4)
CPU-Target: 64 Bit

Immutable Maps und Sets

Beitrag von BeniBela »

Wenn jemand eine Map/Set braucht, die man in konstanter Zeit kopieren kann, baue ich gerade eine:

Code: Alles auswählen

  
type TImmutableMapStringString = specialize TImmutableMap< string, string, THAMTTypeInfo>;
var map, map2, map3: TImmutableMapStringString;
    p: TImmutableMapStringString.PPair;
begin
  map := TImmutableMapStringString.create;
  map2 := map.Insert('hello', 'world');
  map3 := map2.insert('foo', 'bar');
 
  writeln(map.get('hello', 'default')); // default
  writeln(map.get('foo', 'default')); // default
 
  writeln(map2.get('hello')); // world
  writeln(map2.get('foo', 'default')); // default
 
  writeln(map3['hello']); // world
  writeln(map3['foo']); // bar
 
  //enumerate all
  for p in map3 do
    writeln(p^.key, ': ', p^.value);
 
  map.free;
  map2.free;
  map3.free;
end

MacWomble
Lazarusforum e. V.
Beiträge: 999
Registriert: Do 17. Apr 2008, 01:59
OS, Lazarus, FPC: Mint 21.1 Cinnamon / FPC 3.2.2/Lazarus 2.2.4
CPU-Target: Intel i7-10750 64Bit
Wohnort: Freiburg

Re: Immutable Maps und Sets

Beitrag von MacWomble »

So ganz habe ich nicht verstanden wozu das benötigt wird. Ich habe auch keine verständliche Erklärung im Netz gefunden.
Alle sagten, dass es unmöglich sei - bis einer kam und es einfach gemacht hat.

Socke
Lazarusforum e. V.
Beiträge: 3158
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Immutable Maps und Sets

Beitrag von Socke »

MacWomble hat geschrieben:So ganz habe ich nicht verstanden wozu das benötigt wird. Ich habe auch keine verständliche Erklärung im Netz gefunden.

Ich habe unter http://untangled.io/immutable-js-an-int ... or-humans/ eine ganz anschauliche Erklärung gefunden, wie sich Immutable Maps verhalten. Zum Anwendungsbezug wird dort sinngemäß geschrieben:
Mike Evans hat geschrieben:Another way to think of an Immutable collection is to think of it as the state of its data at the specific point in time that the collection was created. Whenever we query that collection, we always get the state of its data that existed at its moment of creation. We might move on in time, but the collection itself never does.
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

BeniBela
Beiträge: 308
Registriert: Sa 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4)
CPU-Target: 64 Bit

Re: Immutable Maps und Sets

Beitrag von BeniBela »

Vor allem geht es mir, um das schnelle Kopieren (korrekter würde man es persistent copy-on-write statt immutable nennen)

Kopieren kennt man ja von records und statischen Arrays, wenn man eine Funktion aufruft die keinen var/const Parameter für den record/array hat wird der Parameter für die Funktion kopiert. Wenn dann die Funktion etwas am Wert ändern, hat die aufrufende Funktion trotzdem noch den alten Wert. Da das Kopieren die Voreinstellung ist statt das var/const-Verhalten, wird es wohl schon einen Nutzen bringen

Nur ist das Kopieren von records langsam, während es mit den HAMT schnell geht

Wenn man zum Beispiel dieselbe Hashmap an mehrere Threads übergibt, will man ja nicht, dass die sich gegenseitig überschreiben, wenn sie etwas ändern, aber die gesamte Map normal zu kopieren wäre auch zu langsam

Socke
Lazarusforum e. V.
Beiträge: 3158
Registriert: Di 22. Jul 2008, 19:27
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 10/Linux/Raspbian/openSUSE
CPU-Target: 32bit x86 armhf
Wohnort: Köln
Kontaktdaten:

Re: Immutable Maps und Sets

Beitrag von Socke »

BeniBela hat geschrieben:Wenn man zum Beispiel dieselbe Hashmap an mehrere Threads übergibt, will man ja nicht, dass die sich gegenseitig überschreiben, wenn sie etwas ändern, aber die gesamte Map normal zu kopieren wäre auch zu langsam

Und deine Map kann schneller kopiert werden, da due eine Baumstruktur (Trie) verwendest?
Oder muss bei einer "Kopie/Änderung" nicht die Originalliste kopiert werden, da diese sowieso nicht verändert werden darf und einfach als Vorgängerliste verwendet wird?
MfG Socke
Ein Gedicht braucht keinen Reim//Ich pack’ hier trotzdem einen rein

BeniBela
Beiträge: 308
Registriert: Sa 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4)
CPU-Target: 64 Bit

Re: Immutable Maps und Sets

Beitrag von BeniBela »

Beides, das meiste wird nicht kopiert und als Vorgänger"liste" verwendet, aber wenn doch mal was kopiert wird, kann man es im Baum effizienter machen. Zum Beispiel wenn man einen Knoten kopiert, um ihn zu überschreiben, kann man die Kinder unverändert lassen.

So im Idealfall wird nur die Wurzel kopiert, wenn man beispielsweise nur ein neues Kind an die Wurzel hängt.

Im schlimmsten Fall werden 7 Knoten kopiert (und ein Array wenn es mehrere Einträge mit demselben Hashwert gibt), weil das die Baumtiefe ist

Antworten