News for hackers. Stuff that matters.
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.
Re:Mapping Strings in C++ by pacaro on Wednesday April 12, 2017 @07:28PM (#14102696)
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
Re:Mapping Strings in C++ by jnordwick on Wednesday April 12, 2017 @10:48PM (#14103736)
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.