Immutable Maps und Sets

Zur Vorstellung von Komponenten und Units für Lazarus

Immutable Maps und Sets

Beitragvon BeniBela » 9. Sep 2018, 23:51 Immutable Maps und Sets

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
BeniBela
 
Beiträge: 248
Registriert: 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4) | 
CPU-Target: 64 Bit
Nach oben

Beitragvon MacWomble » 11. Sep 2018, 12:29 Re: Immutable Maps und Sets

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.
MacWomble
 
Beiträge: 607
Registriert: 17. Apr 2008, 00:59
Wohnort: Freiburg
OS, Lazarus, FPC: Mint 19 Cinnamon / CodeTyphon Generation V Plan 6.60 | 
CPU-Target: Intel i7 64/32 Bit
Nach oben

Beitragvon Socke » 11. Sep 2018, 15:21 Re: Immutable Maps und Sets

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
Socke
 
Beiträge: 2552
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon BeniBela » 11. Sep 2018, 23:00 Re: Immutable Maps und Sets

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
BeniBela
 
Beiträge: 248
Registriert: 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4) | 
CPU-Target: 64 Bit
Nach oben

Beitragvon Socke » 12. Sep 2018, 09:10 Re: Immutable Maps und Sets

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
Socke
 
Beiträge: 2552
Registriert: 22. Jul 2008, 18:27
Wohnort: Köln
OS, Lazarus, FPC: Lazarus: SVN; FPC: svn; Win 8.1/Debian GNU/Linux/Raspbian/openSUSE | 
CPU-Target: 32bit x86 armhf
Nach oben

Beitragvon BeniBela » 13. Sep 2018, 18:26 Re: Immutable Maps und Sets

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
BeniBela
 
Beiträge: 248
Registriert: 21. Mär 2009, 17:31
OS, Lazarus, FPC: Linux (Lazarus SVN, FPC 2.4) | 
CPU-Target: 64 Bit
Nach oben

• Themenende •

Zurück zu Units/Komponenten



Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste

porpoises-institution
accuracy-worried