search

wishfoundry / rrbit

An Immutable vectors/lists/arrays library using the Relaxed Radix Balancing(RRB) technique
The Unlicense
12 stars 4 forks source link

Roadmap: 'focus' #5

Closed wishfoundry closed 7 years ago

wishfoundry commented 7 years ago

The 2012 paper describes the relaxed indexing mechanism quite well, but the 2015 paper further expands on the use of a movable 'focus' where inserts occur, instead of the 'tail' we use today.

This allows of both fast appends or prepends(any inserts really) and generally expands the use cases this vector type can solve well.

Unfortunately, it does appear to be a bit of a rewrite to fully implement it, which explains why clojure/haskell don't seem to have implemented it yet. There is a scala version worth poking into though...

wishfoundry commented 7 years ago

A more recent paper describing RRB vector optimizations https://pdfs.semanticscholar.org/b26a/3dc9050f54a37197ed44711c0e42063e9b96.pdf Explanation of class RRB tree logic https://www.youtube.com/watch?v=K2NYwP90bNs