3 ms·
Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations. Modern languages like Scala's Vector type is an rrb-tree under
by proverbialbunny 7y ago
Not a benchmark but rrb-trees are pretty neat. They give an effective O(1) for all operations.
Modern languages like Scala's Vector type is an rrb-tree under the hood: https://docs.scala-lang.org/overviews/collections/performance-characteristics.html https://docs.scala-lang.org/overviews/collections/performanc...
For more fun: https://youtu.be/sPhpelUfu8Q https://youtu.be/sPhpelUfu8Q
- mruts 7y agoUnfortunately, Scala’s vector type actually sucks big time in regards to performance: http://www.lihaoyi.com/post/BenchmarkingScalaCollections.html http://www.lihaoyi.com/post/BenchmarkingScalaCollections.htm... Moreover if you want random access just use Arrays (especially now that 2.13 has immutable ones). The only use case for Vector is when you don’t know the collection size up front and need random access. Though even then it honestly might just be a better idea to build up a list and then convert it to an array.