Ramine
3/12/2015 8:20:00 AM
Hello,
I want to speak today about a datastructure called Skiplist,
i have took a look at its time complexity and what i have
noticed that it's using a randomLevel() function that returnes
how many levels of pointers the element will have , but look
with me at this function:
randomLevel()
lvl := 1
-- random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl
As you have noticed the probability will get smaller and smaller when
you will get higher levels and when you get higher levels even at
a probability of 1/16 the datastructure may degenarate towards the worst
case performance far from a log(n) time complexity, and if
it degenarates and you are constructing your a bigger in-memory database
with your skiplist, your database will get too slow and
this is not good.. so this is why i don't like skiplists.
Thank you,
Amine Moulay Ramdane.