News for hackers. Stuff that matters.

A comment on Show HN: Array with Constant Time Access and Fast Insertion and Deletion. Parent comment

Re:Show HN: Array with Constant Time Access and Fast Inserti... by detrino on Wednesday September 04, 2019 @12:25PM (#20878730)
Re benchmarking vs other data structures: Here is a B+Tree based sequence container I made: https://github.com/det/segmented_tree

Basically, it has O(log n) everything like a binary search tree you suggested but also very good constant factors.

By default, leaves hold 1024/sizeof(T) elements and branches hold 47 elements, so it can access up to 13,289,344 8 byte elements with only 4 levels.

[ Parent | on HN ]
Re:Show HN: Array with Constant Time Access and Fast Inserti... by piccolbo on Friday September 06, 2019 @11:48AM (#20896702)
How is that different from a rope data structure?
[ Parent | on HN ]
Re:Show HN: Array with Constant Time Access and Fast Inserti... by detrino on Monday September 09, 2019 @09:23PM (#20924292)
Depends what you consider a Rope.

Does it require constant time concat?

Does it require immutability?

Does it require a balancing scheme based on the fib sequence?

Does it require that the tree is binary?

My tree is an attempt to be as fast as possible with log everything operations and no pointer/reference stability.

[ Parent | on HN ]
Re:Show HN: Array with Constant Time Access and Fast Inserti... by piccolbo on Friday September 06, 2019 @11:51AM (#20896724)
Should've said a generalized rope, as ropes are generally described as a replacement for strings, but if you replace characters with other fixed size data types everything still works.
[ Parent | on HN ]