Oh nice, I've designed something similar before. You can do this within a single array by always adding new elements to the end of the array and performing an in-place merge of adjacent equal-sized bins. So the example given would look like:
1, 4, 6, 7, 8, 10, 11, 12, 2, 3, 9, 13, 5
The structure is implicit in the size (as mentioned in the article). No need for an explicit array-of-array structure.
----
A related data structure I've been playing around with in F# (but haven't had time to write up) --
1. Instead of merging arrays, just append them.
2. Instead of arrays, use binary trees.
3. Instead of an array of these arrays/binary trees, use a linked list (so, a linked list of complete binary trees of strictly increasing depth). Omit elements whose trees are empty.
4. Put two of these back to back ("large" ends touching).
5. Recognize that if one of these lists is empty, a binary tree (or half of one) can be moved from the back of the other list to populate it.
Now you have a purely functional double-ended list with log(n) indexing, insertion, deletion, and append, while retaining a high degree of sharing.
----
Similarly, another related data structure I've been playing around with in Prolog --
1. No merging or appending.
2. Instead of arrays, use binary trees.
3. Instead of an array of these arrays/binary trees, use an infinite linked list, in order of increasing depth.
4. Do not explicitly instantiate this structure. Represent everything initially as a logic variable, only expanding linked list and binary tree nodes as needed.
5. Place two of these back to back, and add one extra logic variable in-between.
Now you have a purely relational array with integer indexes, supporting log(n) indexing and assignment, no upper or lower bound, and native Prolog unification. (Which coincidentally is in identical to the notion of "array" in SMTLIBv2.)
----
TLDR sequences of complete binary trees of increasing depth can be used for many interesting data structures.
Oh, I don't know that there's a way to do that. The G++ implementation uses free memory if available for linear merge, else it falls back to n log n merge. I don't think this affects the performance of insert though (which is already log n due to the necessary lookup).
Comments
Oh nice, I've designed something similar before. You can do this within a single array by always adding new elements to the end of the array and performing an in-place merge of adjacent equal-sized bins. So the example given would look like:
The structure is implicit in the size (as mentioned in the article). No need for an explicit array-of-array structure.----
A related data structure I've been playing around with in F# (but haven't had time to write up) --
1. Instead of merging arrays, just append them.
2. Instead of arrays, use binary trees.
3. Instead of an array of these arrays/binary trees, use a linked list (so, a linked list of complete binary trees of strictly increasing depth). Omit elements whose trees are empty.
4. Put two of these back to back ("large" ends touching).
5. Recognize that if one of these lists is empty, a binary tree (or half of one) can be moved from the back of the other list to populate it.
Now you have a purely functional double-ended list with log(n) indexing, insertion, deletion, and append, while retaining a high degree of sharing.
----
Similarly, another related data structure I've been playing around with in Prolog --
1. No merging or appending.
2. Instead of arrays, use binary trees.
3. Instead of an array of these arrays/binary trees, use an infinite linked list, in order of increasing depth.
4. Do not explicitly instantiate this structure. Represent everything initially as a logic variable, only expanding linked list and binary tree nodes as needed.
5. Place two of these back to back, and add one extra logic variable in-between.
Now you have a purely relational array with integer indexes, supporting log(n) indexing and assignment, no upper or lower bound, and native Prolog unification. (Which coincidentally is in identical to the notion of "array" in SMTLIBv2.)
----
TLDR sequences of complete binary trees of increasing depth can be used for many interesting data structures.
How do you do an in-place merge in linear time (i.e. without blowing up the time complexity)? I've been chasing that for many years with no solution. https://www.nayuki.io/page/is-there-an-ideal-comparison-sort
Oh, I don't know that there's a way to do that. The G++ implementation uses free memory if available for linear merge, else it falls back to n log n merge. I don't think this affects the performance of insert though (which is already log n due to the necessary lookup).
I was curious enough to have a go at implementing the same algorithm using a single vector [0], but it still runs about twice as slow as the original.
std::set is almost 4x faster on my machine.
A straight binary sorted vector is even faster. But degrades when the input is highly "unsorted" because of vector manipulations.
[0] doesn't show any sensitivity to insert order, which is a bit odd.
https://gist.github.com/codr7/d94ef02a5949cb01c57038c606838d...