←back to thread

A “frozen” dictionary for Python

(lwn.net)
191 points jwilk | 1 comments | 11 Dec 25 09:51 UTC | HN request time: 0.201s | source
Show context
perrygeo ◴[11 Dec 25 15:02 UTC] No.46232229[source]▶
Python discovers immutable data, and gets it wrong. Frozendict is a blunt instrument - instead of a mutable free-for-all, it just locks the data for the entire lifecycle. Brace for the wave of code littered with deep copies, proudly proclaiming how functional it all is.

If you want real immutable data structures, not a cheap imitation, check out pyrsistent.

replies(2): >>46232356 #>>46232421 #
cylemons ◴[11 Dec 25 15:17 UTC] No.46232421[source]▶
How else would you "modify" immutable data other than by copying it?
replies(3): >>46232514 #>>46232538 #>>46238746 #
1. ndr ◴[11 Dec 25 15:24 UTC] No.46232514[source]▶
You don't have to copy everything.

Look up persistent data structures [0]

The main trick is to store everything in a tree with a large branching factor.

The elements are on your leaves. When you want to make an edit you need to create only the nodes from the root to the actual leaf. Then you return the new root. Everything else you can share.

This is a log operation, normally implemented with branch 32.

It works with vectors as well as dicts. Creating a copy is constant, it's immutable can be shared freely (especially on GC'd languages).

Insert/Delete are O(log32(n)) instead of O(n) they'd be with a full copy.

[0] https://en.wikipedia.org/wiki/Persistent_data_structure#Pers...