Show HN: Array with Constant Time Access and Fast Insertion and Deletion

Re:Show HN: Array with Constant Time Access and Fast Inserti... by kccqzy on Wednesday September 04, 2019 @01:14AM (#20874191)

Doesn't really seem much better than just a balanced size-tagged binary tree. You get O(log n) access, insertion, and deletion. Yes access is slower but insertion and deletion is much faster. Remember that for even one billion the logarithm is merely 30. That's hardly anything. Whereas the square root is more than 30 thousand.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by igushev on Wednesday September 04, 2019 @01:31AM (#20874279)

That sounds like trees are silver bullets but they're not and that's why we have variety of basic data structures.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by kccqzy on Wednesday September 04, 2019 @01:38AM (#20874316)

I'm not saying they are a silver bullet but personally from experience I think they are a good choice in the majority of scenarios that programmers encounter. Of course our experiences could differ.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by snovv_crash on Wednesday September 04, 2019 @06:02AM (#20875595)

Really depends on your dataset size, right? You give 1 billion as an example, that is 8GB of RAM in a single data structure just in overhead if you have a pointer for each tree leaf.

This data structure makes more sense in the 10k-1M size, where chasing pointers is expensive and the scaling doesn't dominate.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by proverbialbunny on Wednesday September 04, 2019 @10:41AM (#20877592)

Right, or an rrb-tree which is effectively O(1) for everything. It's a tree of arrays where the arrays are usually 32 or 64 elements. Though, there's a bit more to it than that.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by anarazel on Wednesday September 04, 2019 @03:08AM (#20874691)

This type of data structure ought to have much better cache and branch prediction behaviour than most tree implementations.

[ Parent | on HN ]

Re:Show HN: Array with Constant Time Access and Fast Inserti... by saagarjha on Wednesday September 04, 2019 @01:24AM (#20874239)

I wonder if you can save a bit in the constant by only having to chase one pointer instead of log(n) of them.

[ Parent | on HN ]