Please disregard this message; I hadn't seen Bill Myers' solution
("copy-on-write
by cloning only when reference count > 1"), which sounds like it's probably
perfect for Rust.On Wed, Dec 4, 2013 at 9:03 PM, David Piepgrass <[email protected]>wrote: > >My next goal is a persistent tree-map, probably cribbing from Haskell's > >Data.Map. > > I look forward to hearing how that goes! > > I've been meaning to make a data structure in Rust too, but it's hard to > find the time, so how's about I tell you guys about it instead. > > I call my data structure an "optionally-persistent" hashtable or hashset. > In C# I implemented this "optionally-persistent" hashtable and hashset with > mutable and immutable variants of each (the term "semi-persistent" was > already taken and means something else). I've been meaning to write an > article about this, but didn't get around to it yet. > > Optionally-persistent means that it's structured as if it were persistent, > but each node can be either mutable (locally) or immutable (recursively). > Each node has a "frozen" flag which implicitly applies recursively to all > children. Converting the tree from immutable to mutable, or mutable to > immutable takes O(1) time. Immutable to mutable is essentially a no-op (the > mutable copy has copy-on-write behavior), while mutable-to-immutable simply > requires marking the root node as frozen. > > The "hashtable" is really a tree that is up to 8 levels deep, with each > level representing 4 bits of the hashcode (not sure if this is the best > approach). Lots more details in the doc comment: > > > https://sourceforge.net/p/loyc/code/HEAD/tree/Src/Loyc.Collections/Sets/InternalSet.cs > > My benchmarks show that mutating such a set/map is dramatically faster > than immutable editing (which requires copying multiple nodes for each > change), and not that much slower than a traditional hashtable, so I think > it's "hands down" superior to a traditional persistent hash tree. > > In my version, from the end-user's perspective, there's a separate data > type for immutable and mutable versions of the data structure (MMap<T> and > MSet<T> are mutable, Map<T> and Set<T> are immutable). Both data types > encapsulate an instance of InternalSet<T> which is the "real" data > structure. InternalSet<T> manages a tree of nodes, where each node has 16 > entries and represents 4 bits of the hashcode. There's also an interesting > variation called InvertibleSet<T>; an invertible set can represent a > negative set such as "all integers except 0 and 1". > > -- > - David > http://loyc-etc.blogspot.com > > -- - David http://qism.blogspot.com
_______________________________________________ Rust-dev mailing list [email protected] https://mail.mozilla.org/listinfo/rust-dev
