5 ms·
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.
by malisper 7y ago
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 https://www.ics.uci.edu/~goodrich/pubs/wads99.pdf
- igushev 7y agoThanks for feedback! Any naming suggestions? :-)
- rixed 7y ago2-tiered vector.
- deleted 7y ago[deleted]
- Stratoscope 7y agoThis is fun, let's have a naming party! Here's my nomination: Loop List
- lkesteloot 7y agoThe key to having things named after you is to give them generic names. Name your thing "array", literally, everywhere in the readme and the code. Then people using it won't have any choice but to say "igushev's array" and that'll stick in the long run.
- abra0 7y agoIn competitive programming circles I've heard the basic idea called root or sqrt decomposition.
- aldanor 7y agotiered_array
- k_s 7y agoHere's an implementation that combines the paper you referenced with http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf http://www.cs.uwaterloo.ca/research/tr/1999/09/CS-99-09.pdf, which gives dynamic sizing: https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/data_structure/ThriftyList.java https://github.com/KevinStern/software-and-algorithms/blob/m...
- detrino 7y agoRe benchmarking vs other data structures: Here is a B+Tree based sequence container I made: https://github.com/det/segmented_tree https://github.com/det/segmented_tree Basically, it has O(log n) everything like a binary search tree you suggested but also very good constant factors. By default, leaves hold 1024/sizeof(T) elements and branches hold 47 elements, so it can access up to 13,289,344 8 byte elements with only 4 levels.
- piccolbo 7y agoHow is that different from a rope data structure?
- piccolbo 7y agoShould've said a generalized rope, as ropes are generally described as a replacement for strings, but if you replace characters with other fixed size data types everything still works.
- detrino 7y agoDepends what you consider a Rope. Does it require constant time concat? Does it require immutability? Does it require a balancing scheme based on the fib sequence? Does it require that the tree is binary? My tree is an attempt to be as fast as possible with log everything operations and no pointer/reference stability.