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

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 pretty clever. The datastructure maintains sqrt(N) circular arrays each of size sqrt(N). For reference indexing into a circular array has O(1) access time and O(1) insert and deletion time at the ends.

For accesses, you can in constant time determine which circular array contains the element at the given index (it's simply i % sqrt(N)) and then in constant time access the element from the underlying array. For inserts and deletions, you find the circular array that contains the location you want to insert into. First you make sure there is space in the array to insert. You do this by moving one element from each circular array to the next one. Since deleting and inserting from the end of a circular array takes O(1) and there are O(sqrt(N)) arrays, this takes a total of O(sqrt(N)) time. Then you insert the new element into the middle of the designated circular array which is of size sqrt(N) so it takes in the worst case O(sqrt(N)). This means insertions take a total of O(sqrt(N)) time.

As immawizard pointed out, there is a generalized version of this idea called tiered vectors[0] that supports an arbitrary level of nesting. A 1-tiered vector is a circular array. A k-tiered vector is an array of n^(1/k) tiered vectors of tier (k-1). You can show that for a k-tiered vector, access time is O(k), while insertion and deletion have a runtime of O(n^(1/k)). The datastructure mentioned in the post can be considered a 2-tiered vector.

The post includes benchmarks comparing the datastructure to std::vector. I would be interested in seeing benchmarks vs a binary search tree. Even though the datastructure has O(sqrt(N)) performance, that's still a lot slower than O(log(N)). The square root of a million is 1000, while the log base 2 of a million is only ~20.

One nitpick is that the author names the datastructure after themselves. Naming things after yourself is typically a faux pas.

[0] https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

I believe this data structure is called Tiered vectors, and is described in: https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf

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 (presumably) presenting the arithmetic mean is not very informative. Looking at the detailed reported benchmark times (in the output file in tests), it looks like many of the timing outcomes have high variance. Rather than running the tests 1000 times and taking the mean, you might consider running 10 batches of 100 tests (or 1000, if you can) and presenting the mean and variance of the resulting distribution. In general, k sample groups each of size p will provide more reliable information about the underlying distribution than one sample group of size k*p (for reasonable k and p, obviously).

2. Related to that, the results of the "inserting a number of elements" and "deleting a number of elements" tests are significantly worse for the tiered vector vs the std::vector than the "insert/delete a single element" tests. You don't mention this in the readme, but thinking about why it is might be informative. Thrashing seems like a possible explanation, and one you might be able to mitigate.

3. Are you making sure your cache is warm before starting to measure performance? (Pardon, I didn't look through every line of your tests.) Particularly for std::vector, and likely your intermediate deques too, this will have a big effect on timing.

4. Finally, it looks like you're primarily testing using ints (?). It would probably be a good idea to see if your results hold for a different payload size.

I don't know whether these will improve or worsen your comparison against std::vector, but they will make your claims more robust.

There's some interesting pointers for how to improve your data structure here: https://stackoverflow.com/questions/10478260/looking-for-a-d...

There's also some benchmarks for another implementation of the same idea linked to in the README here: https://github.com/mettienne/tiered-vector/blob/master/READM.... That implementation also just punted on growing the maximum capacity of the area.

Correct me if I am wrong, but I think the insertion/deletion time complexity is incorrect. It should be O(N). If each DEQ is implemented using array instead of list, wouldn’t the insert/delete operation of IgushArray still take linear time? Since popping or pushing (pick one) of DEQ implementation with array still take linear time, that means, let’s say insertion is at position N/2, then N/2 ... N-1 elements still need to be moved to the right by one? Popping/pushing is only linear if the DEQ is implemented with linked list, but that would mean linear access time instead of constant.

Update: answer is to implement DEQ with circular buffer for O(1) pop/push.

Interesting that some people found an article about tiered vectors, I didn't find it back then. I implemented this structure many many years ago and also published in Bauman Moscow State Technical University magazine back in 2012: http://engjournal.ru/articles/101/101.pdf (in Russian)

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 deletion within the body of the array. This guarantee is provided by allowing for the possibility of significant overallocation in the chunks themselves, if many modifications happen in the middle of the array. On the other hand, std::deque does not overallocate by as much -- just a chunk at the beginning and a chunk at the end. But as a consequence it has to move trailing elements when an element is inserted or deleted in the middle.

Interesting!

I'd like to see the performance of growing the list (a common scenario):

    ArrayList list = new ArrayList();
    for (int i = 0; i < N; i++) {
      list.add(i);
    }

(Forgive me, Java is my mother tongue).

This is cool. I wanted to comment on the necessity of knowing the approximate size of N a priori, but this is very clearly stated on the github page.

Interesting alternatives that also support insertion, deletion, and lookup (is there a name for this interface?) are AVL trees and hash tables.

As described in https://arxiv.org/pdf/1711.00275.pdf, tiered vectors can be improved further:

"We present a highly optimized implementation of tiered vectors, a data structure for maintaining a sequence of n elements supporting access in time O(1) and insertion and deletion in time O(n^ε) for ε > 0 while using o(n) extra space."

I wonder how this would compare to Judy arrays. Would anyone like to benchmark this?

https://en.wikipedia.org/wiki/Judy_array http://judy.sourceforge.net

To install the Judy C lib:

  brew install judy
  apt-get install libjudy-dev

Then compile with -lJudy and #include <Judy.h>

Example: http://judy.sourceforge.net/doc/JudyL_3x.htm

Why would you chose this over a Van Emde Boas tree where indexing, insert, delete are O(log log) and prev/next are constant?

https://en.wikipedia.org/wiki/Van_Emde_Boas_tree

(it basically trades a little more work on indexing for a little loser structure)

I like the use of the DE queue, but having to keep all the sub vectors packed to ensure constant time lookup might not be completely needed if you are willing to keep a little more information around or have two candidate buckets. Not sure if would be a win or not though, since they your probably just better using a VeB tree.

e.g., I don't think you always need to compress everything back to the front if you can make sure all the buckets are within 1 or each other, but you can hit cases where you have to look in two buckets which isn't that difficult since you how the high and low of each bucket at the head and tail of each DEQ.

But then you would need to keep some local coloring info keep the buckets perfectly balanced, as everything should be.

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.

Is there a reason you didn’t just use std::deque? You’re already in C++.

It says in bold type at the beginning "The IgushArray class fully implements std::vector interface" but it's clear it cannot provide an equivalent of std::vector::data.

Side-question: is there any way to explicitly tell github whether a file is C or C++? I have this same issue, where C code is marked as C++ and vice-versa. Not a huge issue, but a bit annoying. It seems a bit weird that linguist (github's tool for doing language recognition) marks a file with namespaces in it as C, which is obviously not supported.

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 (https://arxiv.org/abs/1806.06726).

That being said, the overload of a complex data structure might multiply the running time by a factor up to ~10 (mostly because of cache misses), so simpler structures will be more performant for short inputs.

There is a more general pattern in most tree data structures where you can transform the log(n) recursive operations on the tree into sqrt(n) operations on a simpler structure with 2 levels.

I happen to have described the solution to a problem where you must use a sqrt-decomposition datastructure to have updates in O(1) and queries in O(sqrt(n)) because O(log(n)) everywhere is not good enough as there are a lot of updates to do (https://tryalgo.org/en/2017/09/01/path-statistics/).

The 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 collections. Using different items, say std::string, int64_t and a big POD struct might fill in a few things too.

If deq had to be fixed length beforehand with length k but with many insertions k can be much smaller than n^0.5 I think you might end up with a much worse worst case for insertion? Something in the order of O(n) than O(n^0.5)

Or there has to be a readjustment of k.

Cab somebody point out my thinking error?

The Push Front time could be improved to O(1)* by making it circular. Assuming "*" means amortized. But as-is it does provide a better comparison to an array. A circular IgushArray would be better compared to a circular array (which an std::vector isn't).

You could do this with O(N^1/K) for arbitrary K, using K layers of indirection, no?

This is similar to how you can do O(logN) for insertion / deletion & access using an indexed B-tree, except you're using a fixed height instead of a fixed branching factor.

cool! looks like from that, you could maybe

1. extend the construction to three dimensions, so that the insertion cost is a cubic root?

2. iterate the extension to an increasing number of dimensions, so that the cost becomes logarithmic?

The benchmarks compare this to standard arrays, but I'd be curious to see how tiered vectors stack up against persistent vectors (either Clojure's or Python's [pyrsistent's])

As someone who doesn't know much about this level of CS, can someone explain to me why inserting/deleting an element in a linear array is expensive?

Your idea appears to build upon the concepts in the https://en.wikipedia.org/wiki/Hashed_array_tree .

Alternatively, here's my list ADT implementation which has O(log n) access/insertion/deletion time: https://www.nayuki.io/page/avl-tree-list .

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)

I had some hard time parsing O(N^1/2)... ;)

( O(N^(1/2)), O(N^0.5), O(sqrt(N)), O(N¹ᐟ²), O(√N̅) would have been better... )

Reminds me of a skip list.

Nothing beats !a[$0]++

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...