I was working on a problem for some time now, and I made a data structure to solve it. To my surprise, I could not find any instance of this data structure on the internet (though I am certain someone has thought of this).
Put simply, it is a sorted linked list and a sorted array, with the array pointing to spots a fixed distance apart in the linked list:
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
| | |
where the gap between elements $g = c*log_2(n)$
To find an element, just binary search the array and then go to that spot in the linked list, traverse the list until the element is found or greater than the target, return true or false respectively.
To insert you do much the same: traverse and insert before the first largest element.
Of course this by itself is not sufficient as our performance will rapidly degrade over time from $log_2(n)$ to $n$. To fix this, I came up with a very simple solution: as you are traversing the list to find / insert the element, every $g$ elements ($g$ is the gap size) you just move the next "pole" (poles are the items in the array) over to the current element. If there is no next pole, add a pole to the end of the array:
insert(6.5) called (before, gap size = 4)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10
| |
(after)
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 6.5 -> 7 -> 8 -> 9 -> 10
| | |
Surprisingly, I could not find a way to permanently degrade the average performance to $n$: it would always average out to $log(n)$. The intuitive logic is that every time an adversarial user would attempt an insert/find that is relatively expensive (that is when the gap grows large, which happens when the order of insertion is reversed ie. inserting decreasing elements), they are pushing this gap further to the right, until it gets pushed to the end and new poles are inserting, bringing the performance back down to $log_2(n)$.
My analysis was this: lets say you insert $n$ elements at the front. Now the list is doubled in size, and all the poles are bunched on one end. The next find call could be made a worse case $n$ operations, which would shift all those poles to the front. You could do this one more time, which again is $n$, and this time there are no poles in front, so you add them, approximately doubling the number of poles, bringing the worst case performance back down to $log_2(n)$.
Note that you can't create gaps and make expensive calls one after the other: every expensive call fixes the list more and more, so you can either make a large gap and exploit it some number of times, or you will spread the poles out and the performance will level out (I think, I am no expert at this).
In general, if you insert $n/q$ elements in the front (which is the worse case), you will be able to incur a $n/q$ cost another $(q+1)/q$ more times, which makes the total cost average out to $log_2(n)$:
$\frac{n/q*log_2(n/g) + ((q+1)/q)*(n/q)}{2*n/q} = \frac{log_2(n/g)}{2} + \frac{1}{2} + \frac{1}{2q} = O(log_2(n/g)) + g \approx O(log_2(n))$
Removing items is a bit annoying. The simplest way is to leave deleted elements in the list and mark them as deleted, performing a clean up every time $n/d \geq 0.5$. This is amortized $log_2(n)$, same as above. This does waste space, however.
My implementation and benchmarks are here (along with some bugs most likely 😃): https://github.com/Kh4n/teleport-list
For the regular linked list version, I used two arrays, one that "caches" the linked list values to improve the binary search speed, and the other which contains the actual pointers.
It beats the built in multiset implementation easily, which is a red-black tree. The unrolled version (which uses an unrolled linked list instead of a regular linked list) is particularly fast. Nevertheless, I am not certain if it is $log_2(n)$. This is something I would like verification of.
Advantages:
- Fast and simple to program
- Good cache usage
- Very low space overhead when compared to other $log(n)$ data structures
- Can easily trade space/speed to tune the structure to your needs
- Trivial bulk insertion methods
- Can be combined with other data structures easily
- Excellent performance for long increasing/decreasing runs of data
- Good for primitive types
Disadvantages:
- I don't think it is viable for multithreaded usage. Although the whole array only needs to be locked when growing in size, finds and inserts might not be performant when the indices are locked (I have not tested this)
- Amortized performance means that there can be high variance from call to call
- Deletion wastes space (I cannot find a way to make deletion space efficient, though by rebuilding more often you can trade performance for memory efficiency)
Edit: the amortization calculation above is not correct (it is an underestimate), this is the right one:
$\frac{n/q*log_2(n/g) + ((q+1)/q)*(n/q)}{n/q + (q+1)/q} = \frac{n*log_2(n/g) + n*((q+1)/q)}{n+q+1} \approx log_2(n/g) + \frac{q+1}{q} = O(log_2(n))$
