3 ms·

My somewhat naïve question is: if indeed this is an objectively superior data structure as claimed, why hasn't anyone else thought of it before in the history o

My somewhat naïve question is: if indeed this is an objectively superior data structure as claimed, why hasn't anyone else thought of it before in the history of computer science? Extraordinary claims of devising a radically better implementation of a fundamental data structure require extraordinary evidence that A. the idea is indeed novel and B. it doesn't come with hidden tradeoffs that are only advertised in the fine print. The work seems impressive, and maybe it is somehow a completely new genius idea no-one has thought of, but whatever the case it needs to much more heavily reference existing literature to credibly make the barely-without-qualifiers claims contained in the README. (And to be clear: I actually hope that such references bear out the claims, because if so - awesome! But in the meantime: "trust but verify") Edit: curious about the downvotes - care to explain? I feel like this is a legitimate and fairly uncontroversial take, but happy to hear differing perspectives...

FridgeSeal 7y ago
As other commentors have pointed out [1], it appears to be a Tiered Vector implementation [2]. [1] https://news.ycombinator.com/item?id=20873110 https://news.ycombinator.com/item?id=20873110 [2] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf
asdfasgasdgasdg 7y ago
The downvotes are probably because your question could be asked of any new thing. "If this is so great, why didn't someone do it before? Therefore it is probably not so great." I mean you could literally paste that same comment with almost no modification as a response to almost anything new thing posted on this site. That's a good signal that the comment is not helpful. Also, I don't think the author claimed it's "objectively superior." It has objectively superior asymptotic performance in certain relatively niche workloads. However, its constant time factor is iffy due to all the pointer following and calculations you have to do for random accesses. And the benchmark results in the README show this clearly -- both the strengths and the weaknesses. Actually, your whole train of thought around the claims in the README is puzzling to me. You seem to think they're grandiose and over the top, but the README seems mostly explanatory to me. What statements in there do you think ought to be qualified, specifically, and how? If you want upvotes next time, explain in detail what claims you object to, and why. This comment I'm afraid did not add much to the discussion, at least for me.
- not_kurt_godel 7y ago
  Thanks for your explanation. > It has objectively superior asymptotic performance in certain relatively niche workloads. However, its constant time factor is iffy due to all the pointer following and calculations you have to do for random accesses. And the benchmark results in the README show this clearly -- both the strengths and the weaknesses. I got that impression after going through a fair bit of the README. My feeling is neither the post title nor the introductory statements in the README reflected these very relevant qualifications to the claim of "An Array with Constant Time Access and Fast Insertion and Deletion", and putting the onus on the reader to dig through the whole thing to discover this is either naïve or a bit disingenuous. As others have noted, and as I implied in my comment, there is in fact existing literature that captures the particular ideas and tradeoffs in this implementation - Tiered Vectors. I believe the author has a duty to cite that up front and prominently in the spirit of honest academic discourse.
  - adwn 7y ago
    > As others have noted, and as I implied in my comment, there is in fact existing literature that captures the particular ideas and tradeoffs in this implementation - Tiered Vectors. I believe the author has a duty to cite that up front and prominently in the spirit of honest academic discourse. What "academic discourse"? This is a datastructure implementation with some documentation in a Github repo, not a submission to a scientific journal. You're insinuating a level of rigor that is completely unwarranted. Just lean back, relax, and accept that you overreacted a bit in your original post. It's not the end of the world to admit that.
  - asdfasgasdgasdg 7y ago
    > very relevant qualifications to the claim of "An Array with Constant Time Access and Fast Insertion and Deletion" Why would the author need to add qualifications to the title? That is literally and exactly what the data structure is.
kccqzy 7y ago
No one claimed this is an objectively superior data structure. Even the author presented benchmark numbers that showed that in some scenarios (calculating the sum) this data structure is slower than std::vector in all data sizes. To me, the author's claim isn't extraordinary at all. He simply offered a new data structure with different set of trade offs compared with arrays and linked lists. Also I don't think the author hid the trade offs in fine print. It's literally present in the first table of Big O complexities, and the first benchmark result literally shows his data structure beaten soundly by std::vector.
- igushev 7y ago
  That is true. The complexities in Big O notations, but I put all real-life measurements in README.md, so readers could see. On small item counts the complexity of data structure itself makes it performs worse comparing to std::vectors, only on large item counts it performs betters. Note that access is slower then std::vector due to complexity of data structure but multiplier is always the same.
quickthrower2 7y ago
I think it would do some stuff slower. It's probably a boring old trade off. Like you'd make if you swapped arrays for linked lists. Where I think this would be slower is streaming access. Say you have 10,000 elements, this would store it in a 100 by 100 grid. You want to read off elements 200-500. A normal array would allow you to sequence through them as a continuous block of memory, probably as fast as it gets. I'm outside my expertise here but I believe that block could be loaded into the processors inner most cache? This array OTOH would require some indexing/pointers along the way which would slow it down. So this will add to some of the constants that the O notation conveniently omits!

FridgeSeal 7y ago

As other commentors have pointed out [1], it appears to be a Tiered Vector implementation [2]. [1] https://news.ycombinator.com/item?id=20873110 https://news.ycombinator.com/item?id=20873110 [2] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

asdfasgasdgasdg 7y ago

The downvotes are probably because your question could be asked of any new thing. "If this is so great, why didn't someone do it before? Therefore it is probably not so great." I mean you could literally paste that same comment with almost no modification as a response to almost anything new thing posted on this site. That's a good signal that the comment is not helpful. Also, I don't think the author claimed it's "objectively superior." It has objectively superior asymptotic performance in certain relatively niche workloads. However, its constant time factor is iffy due to all the pointer following and calculations you have to do for random accesses. And the benchmark results in the README show this clearly -- both the strengths and the weaknesses. Actually, your whole train of thought around the claims in the README is puzzling to me. You seem to think they're grandiose and over the top, but the README seems mostly explanatory to me. What statements in there do you think ought to be qualified, specifically, and how? If you want upvotes next time, explain in detail what claims you object to, and why. This comment I'm afraid did not add much to the discussion, at least for me.

not_kurt_godel 7y ago
Thanks for your explanation. > It has objectively superior asymptotic performance in certain relatively niche workloads. However, its constant time factor is iffy due to all the pointer following and calculations you have to do for random accesses. And the benchmark results in the README show this clearly -- both the strengths and the weaknesses. I got that impression after going through a fair bit of the README. My feeling is neither the post title nor the introductory statements in the README reflected these very relevant qualifications to the claim of "An Array with Constant Time Access and Fast Insertion and Deletion", and putting the onus on the reader to dig through the whole thing to discover this is either naïve or a bit disingenuous. As others have noted, and as I implied in my comment, there is in fact existing literature that captures the particular ideas and tradeoffs in this implementation - Tiered Vectors. I believe the author has a duty to cite that up front and prominently in the spirit of honest academic discourse.
- adwn 7y ago
  > As others have noted, and as I implied in my comment, there is in fact existing literature that captures the particular ideas and tradeoffs in this implementation - Tiered Vectors. I believe the author has a duty to cite that up front and prominently in the spirit of honest academic discourse. What "academic discourse"? This is a datastructure implementation with some documentation in a Github repo, not a submission to a scientific journal. You're insinuating a level of rigor that is completely unwarranted. Just lean back, relax, and accept that you overreacted a bit in your original post. It's not the end of the world to admit that.
- asdfasgasdgasdg 7y ago
  > very relevant qualifications to the claim of "An Array with Constant Time Access and Fast Insertion and Deletion" Why would the author need to add qualifications to the title? That is literally and exactly what the data structure is.

kccqzy 7y ago

No one claimed this is an objectively superior data structure. Even the author presented benchmark numbers that showed that in some scenarios (calculating the sum) this data structure is slower than std::vector in all data sizes. To me, the author's claim isn't extraordinary at all. He simply offered a new data structure with different set of trade offs compared with arrays and linked lists. Also I don't think the author hid the trade offs in fine print. It's literally present in the first table of Big O complexities, and the first benchmark result literally shows his data structure beaten soundly by std::vector.

igushev 7y ago
That is true. The complexities in Big O notations, but I put all real-life measurements in README.md, so readers could see. On small item counts the complexity of data structure itself makes it performs worse comparing to std::vectors, only on large item counts it performs betters. Note that access is slower then std::vector due to complexity of data structure but multiplier is always the same.

quickthrower2 7y ago

I think it would do some stuff slower. It's probably a boring old trade off. Like you'd make if you swapped arrays for linked lists. Where I think this would be slower is streaming access. Say you have 10,000 elements, this would store it in a 100 by 100 grid. You want to read off elements 200-500. A normal array would allow you to sequence through them as a continuous block of memory, probably as fast as it gets. I'm outside my expertise here but I believe that block could be loaded into the processors inner most cache? This array OTOH would require some indexing/pointers along the way which would slow it down. So this will add to some of the constants that the O notation conveniently omits!