Re:Mapping Strings in C++
by jnordwick on Wednesday April 12, 2017 @06:58PM
(#14102540)
Reminds me of the tricks self-balancing trees do, rotating the most accessed elements towards the root.
[ Parent
| on HN ]
In particular splay trees do this by rotating elements to the top whenever they are accessed (IIRC) and while they aren't formally balanced, they tend to be "balanced enough" -- if you only ever access a few elements, they will be clustered at the top and the structure of the rest of the tree doesn't matter
We've done few variations of those for representing parts of a trading book where you often have a few price points (the inside) are hit more often and their performance is more important. Self-balancing data structures are very cool.