5
$\begingroup$

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 \ll 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://gist.github.com/Kh4n/0618b6620b73aae6c5bde9adbfca1859

Note that I didn't implement removing items yet (the problem I am working on does not require it, so it wasn't a focus for this data structure). 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))$

$\endgroup$
11
  • $\begingroup$ I didn't understand how you perform insertion/deletion (and how they don't take linear time; it also seems that the optimal value for $g$ is $1$), but overall I don't think it's better than a balanced BST. Using binary search on certain nodes is equivalent to have a complete BST on these nodes. So you essentially have a BST, and then each leaf also has a list of length $g$ (which would replace height $g$ with height $\log g$). It's not clear why to not use trees instead of lists. Which simply gives you a balanced BST. $\endgroup$ – user114966 Mar 25 at 5:14
  • $\begingroup$ The insertion and deletion are hard to understand admittedly, I will work on some graphics for the explanation. You would think $g=1$ is optimal, but in practice $g=4$ is actually faster because the there is an overhead associated with binary search (dereferencing the pointer). Of course if you are using unrolled linked lists, $g=1$ is fine. As for why use this over a BST: less storage space is the main one, seems to have a performance advantage over BST in practice (especially unrolled variant), and can be used for text buffer when combined with a Fenwick tree (very fast for this as well). $\endgroup$ – hLk Mar 25 at 5:20
  • 4
    $\begingroup$ Have you looked at skip lists? en.wikipedia.org/wiki/Skip_list $\endgroup$ – Pseudonym Mar 25 at 5:47
  • 3
    $\begingroup$ Clever! From a theoretical perspective, it has no advantages over a self-balancing binary search tree; a tree supports $O(\log n)$ worst-case running time for all operations (insertion, search, deletion), whereas your algorithm offers $O(\log n)$ amortized time, which is in principle not as good if you only care about asymptotics. Of course, I do understand that your solution appears to have a better constant factor in practice, which is useful. A B-tree might also be worth looking at if you care about constant factors, given modern memory hierarchies. $\endgroup$ – D.W. Mar 25 at 6:41
  • 1
    $\begingroup$ D.W. meant A (B-tree) as in "A house", not (A B)-tree. $\endgroup$ – orlp Mar 25 at 13:39
2
$\begingroup$

I believe you have discovered a variant of "dynamic fractional cascading", which is closely related to skip lists.

$\endgroup$
2
  • $\begingroup$ This DS sort of falls under this category. From Wikipedia, it says that this technique is used to speed up sequences of binary searches, whereas this DS does a single binary search followed by a linear search. $\endgroup$ – hLk Apr 6 at 19:03
  • $\begingroup$ Actually I take that back; the DS does indeed do sequences of binary searches, if you consider the sequence to be all the searches as a whole $\endgroup$ – hLk Apr 6 at 22:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.