IgushArray
Languages and libraries
data structure library
SHOW HN2019
How HN took it
4 positive, 30 neutral or asking, 4 mixed, 20 critical, out of 58 comments about the project. Thread score -0.25.
Performance: 1 for, 8 againstIdea: 1 for, 6 againstExecution: 1 for, 3 againstDocs: 0 for, 3 against
The thread, comment by comment
Each row is a top-level comment and its replies, in HN's order. Select a cell to open that comment on HN.
positive neutral or mixed critical about another commenter or something else the maker
What HN said
What people liked
Clever idea and a neat restructuring of the vector
From 2 comments
For those reading along, the post describes a vector-like datastructure that has O(1) access time and O(sqrt(N)) insert and deletion time at an arbitrary index. The idea is…
malisper on HNI think the data-structure is careful to make sure the main array is at most SQRT(N) and all linked queues also SQRT(N). It's a neat restructuring of the vector into a SQRT(N) *…
juliusmusseau on HN
Objections
Insertion cost O(sqrt N) is still much slower than O(log N) trees
From 2 comments
For those reading along, the post describes a vector-like datastructure that has O(1) access time and O(sqrt(N)) insert and deletion time at an arbitrary index. The idea is…
malisper on HNDoesn'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…
kccqzy on HN
Benchmarks could be stronger (variance, warm cache, payload types)
From 1 comment
I don't want to detract from the cleverness here, but I believe your benchmarks could use some work. Here are a few suggestions: 1. Simply testing something 1000 times and…
birdbrain on HN
Name uses the author's own name
From 1 comment
For those reading along, the post describes a vector-like datastructure that has O(1) access time and O(sqrt(N)) insert and deletion time at an arbitrary index. The idea is…
malisper on HN
Needs fixed size known in advance; no automatic restructuring yet
From 2 comments
I also need to add automatic restructuring when it expands or shrinks significantly.
igushev on HNYes, the structure is sensitive for that and benefits a lot from using reserve(). I need to add automatic restructuring to maintain perfect k.
igushev on HN
Requests
Benchmarks against std::deque, std::list and trees
From 3 comments
Can you also benchmark against std::deque?
temac on HNThe performance numbers would be most interesting if he benchmarked against std::vector, std::list, std::multiset and std::deque just to see how it compares to all the major…
bnolsen on HNRe 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…
detrino on HN
Automatic restructuring on growth and shrink
From 2 comments
I also need to add automatic restructuring when it expands or shrinks significantly.
igushev on HNIt seems I need to add automatic restructuring to the structure, so it would maintain perfect lengths of DEQs
igushev on HN
Questions
Why hasn't this been done before, and what are the trade-offs
From 1 comment
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…
not_kurt_godel on HN
How it differs from ropes or std::deque
From 2 comments
How is that different from a rope data structure?
piccolbo on HNThis is very similar to what std::deque does under the covers already. It's a chunked array. The main difference AFAICT from std::deque is that this offers n^1/2 insertion and…
asdfasgasdgasdg on HN
Alternatives named
Tiered vectors (Goodrich and Kornerup paper)
From 2 comments
I believe this data structure is called Tiered vectors, and is described in: https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf
immawizard on HNFor those reading along, the post describes a vector-like datastructure that has O(1) access time and O(sqrt(N)) insert and deletion time at an arbitrary index. The idea is…
malisper on HN
Skip lists and balanced binary trees
From 2 comments
All of those operations are achievable when replacing sqrt with log by using Skip lists (https://en.wikipedia.org/wiki/Skip_list), and probably with Zip trees as well…
Labo333 on HNDoesn'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…
kccqzy on HN
std::deque
From 1 comment
This is very similar to what std::deque does under the covers already. It's a chunked array. The main difference AFAICT from std::deque is that this offers n^1/2 insertion and…
asdfasgasdgasdg on HN
Ropes
From 1 comment
sqrt(N) can be described as "fast" only with significant amounts of spin added. Use ropes instead. https://en.wikipedia.org/wiki/Rope_(data_structure)
piccolbo on HN