CODEWITHSUNDEEP
algorithmbig-oskip-lists
moo
moo

Reputation: 73

finding the optimal gap size of a deterministic skiplist with only two levels

I am trying to make a "perfect" skiplist with a constant gap size that only has two levels. From calculating the visited nodes for different sized skiplists, I can tell that it's determined by the size, but I can't come up with a formula in terms of n to calculate it.

Upvotes: 0

Views: 311

Answers (1)

Jim Mischel
Jim Mischel

Reputation: 134045

If you really want a constant gap size, then your optimum gap size is the square root of the list's length. For example, if your skip list is 16 items long, then the optimum gap size is 4. To get to the 15th item, you'd make 3 long jumps and 3 short jumps. That's the worst case.

To get to the kth item, you follow k/sqrt(n) + k%sqrt(n) links.

A larger gap size will get you to the end faster, but to get somewhere within the list, you might have to follow more single links. On average, you will follow more links. With a smaller gap size, you follow fewer single links, but more long links.

If your list is 1,000,000 items, then, your gap size should be 1,000.

Your asymptotic complexity goes from O(n) for a single linked list to O(sqrt(n)) with this fixed second level. That's the best you can do with only two levels.

Upvotes: 1

Related Questions