Making generalized Trie type in D

[Dmitry Olshansky]

On 11.06.2012 16:11, Roman D. Boiko wrote:
> On Tuesday, 5 June 2012 at 13:27:12 UTC, Roman D. Boiko wrote:
>> maybe it is better to avoid immutability... or do bulk ins /del before
>> copy.
> Would it be difficult to introduce two optimizations:
> * have strings of all lengths above configurable threshold go to the
> same bucket (is it reasonable?)

The sample I listed did just that: for length >= 64 it goes to bucket of 
0-length strings. After all it's your prefix function, with any 
distribution you like ;)

> * have ability to store a checkpoint, then do a series of modifications,
> and store another checkpoint but reuse data which have not been affected.
>
yea, that's a rough sketch of what I want to support.

> For the second optimization a possible design would be to store internal
> state as snapshot + diffs, and apply diffs when creating another
> snapshot. Diff format should allow efficiently performing trie interface
> operations.

It may be. Diff could be a bunch of pages that are XOR-ed on top of 
snapshot. Dunno if it's worthwhile trick yet.


-- 
Dmitry Olshansky