rklaehn/radixtree

Adding new elements

Opened this issue · 3 comments

pragmaxim commented

Hi,

just out of curiosity, why you haven't implemented adding new elements to an existing instance?
As it does not seem to be too challenging or am I missing something?

rklaehn commented

The general philosophy is to focus on tree/tree ops and implement tree/element ops in terms of tree/tree ops and a singleton tree.

So sure, you could do a helper fn that adds a single element and implement that as union with a single element tree. No reason I didn't do it except that I want to gently guide people to much more efficient bulk ops.

Also, I haven't worked on this or in scala for years and am doing mostly rust these days.

  • 👍1
pragmaxim commented

I got actually confused by the internal representation, as classic radixTree has r=2 however this one looks as if r is basically driven by cardinality of the keys so it is actually not a Radix Tree :)

Also, I haven't worked on this or in scala for years and am doing mostly rust these days.

Yeah I was doing some benchmark comparison with https://github.com/michaelsproul/rust_radix_trie and this implementation is quite impressive 👍

pragmaxim commented

Please one last thing, the interning of keys/values/nodes using AnyRefMap, what makes it 200x/5x (Longs, Strings) more space-efficient?