undefined | Better HN

0 pointsxscott4y ago0 comments

I didn't dive too far into your repo, but it looks like you're doing something similar to Finger Trees [0].

Finger Trees as described in [1] are configurable to be several different kinds of data structures, but using them as a simple list gives you:

  amortized O(1) insert, remove, update at head and tail
  O(log n) insert, remove, update, worst case
  O(log n) concatenation of two lists

And you can traverse all N elements forward or backwards in O(1) per element.

I think it's a very nice data structure.

[0] https://en.wikipedia.org/wiki/Finger_tree

[1] https://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf

0 comments

tomp4y ago

I just tested the Fingertree implementation from org.functionaljava

Conclusion: unusuably slow (which kind-of makes sense, since it looks like the common implementation is a 2-3 fingertree - compared to a branching factor of 32 for Vector).

xscottOP4y ago

There are lots of implementation details that can make some version slower or faster.

In my own, I use 2..5 branching because a sequence of appends on the front or back will tend to create a tree with 3 pointers per node (when you're about to hit 6, you split. If you get to 1, merge with a neighbor, etc...). Three is close to e, which is optimal in some sense for some operations.

I'm not a Java guy. For my use, having 32 way branching is pretty expensive because I use reference counting for each of the nodes. Since you have a true garbage collector, you don't have that cost, and it wouldn't be difficult to make a 2-32 way implementation.

Anyways, it sounds like you're not impressed and not interested. That's fine :-)

j / k navigate · click thread line to collapse