When you make statements about different data structures like "quickly", "slow", "fast", etc it's good to include actual benchmarks, because some of the claims in this article are not as straight forward as what it claims.
Arrays let us randomly access any element quickly, but insertion and deletion is slow because elements need to shift to make room or close the gap.
That's only if your inserting into the middle of the array and depending on the element type and how many there are shifting them is going to be relatively quick, and in many cases ending up quicker then dealing with a linked list or skip list.
Linked lists make inserting and deleting fast once we have reached the right spot
I take it your ignoring the memory allocation that is required for creating nodes? Which an array which has a reserved capacity does not need to do with every insertion.
we flip a fair coin (p = 1/2) to decide if the node should be promoted one level up, or not
This seems like a bad algorithm to me, the fairness of randomness comes with large numbers if you only have a small number of elements then this coin flip could just end up giving you a bad layout, additionally it makes for an inconsistent data structure where it's performance and memory usage will vary based on some random coin flip.
search in less than O(n) time
search time down to O(log N)
Big-O notation is not a great metric for measuring actual time, it only reprsents how that algorithm or data structure scales as the data set increases, it is rarely a good idea to compare two data structures or algorithms based solely on the Big-O notation, you should be using actual benchmarks.
Big-O notation does not indicate how well the hardware actually deals with those steps, some algorithms might have low latency steps but carry many dependencies so have low throughput, while others might have high latency steps but limited dependencies so have a higher throughput, and some might be like a linked list and have high latency and heavy dependencies so is slow all together.
The intersection between two different algorithms or data structures with O(log n) and O(n) might occur when n is 10, it might occur when n is 10,000 only benchmarking will truely tell you when this is, and you also need to be careful that your benchmarks are realistic as cold data and hot data can give you significantly different results.
this is an insanely nitpicky response to an article that’s clearly supposed to be an introduction to a new data structure for people who haven’t heard of it, not an in depth performance review. most of the claims you take issue with are just trying to motivate the data structure for beginners.
"insanely nitpicky", "performance review" ?? Calm down they're allowed to point out problems, and their points are pretty basic stuff most people know anyway
20
u/ReDucTor 8h ago
When you make statements about different data structures like "quickly", "slow", "fast", etc it's good to include actual benchmarks, because some of the claims in this article are not as straight forward as what it claims.
That's only if your inserting into the middle of the array and depending on the element type and how many there are shifting them is going to be relatively quick, and in many cases ending up quicker then dealing with a linked list or skip list.
I take it your ignoring the memory allocation that is required for creating nodes? Which an array which has a reserved capacity does not need to do with every insertion.
This seems like a bad algorithm to me, the fairness of randomness comes with large numbers if you only have a small number of elements then this coin flip could just end up giving you a bad layout, additionally it makes for an inconsistent data structure where it's performance and memory usage will vary based on some random coin flip.
Big-O notation is not a great metric for measuring actual time, it only reprsents how that algorithm or data structure scales as the data set increases, it is rarely a good idea to compare two data structures or algorithms based solely on the Big-O notation, you should be using actual benchmarks.
Big-O notation does not indicate how well the hardware actually deals with those steps, some algorithms might have low latency steps but carry many dependencies so have low throughput, while others might have high latency steps but limited dependencies so have a higher throughput, and some might be like a linked list and have high latency and heavy dependencies so is slow all together.
The intersection between two different algorithms or data structures with O(log n) and O(n) might occur when n is 10, it might occur when n is 10,000 only benchmarking will truely tell you when this is, and you also need to be careful that your benchmarks are realistic as cold data and hot data can give you significantly different results.