Ramine
3/21/2015 11:13:00 PM
Hello,
I was thinking more about Skiplists...
If you look at the the randomLevel functions:
randomLevel()
lvl := 1
-- random() that returns a random value in [0...1)
while random() < p and lvl < MaxLevel do
lvl := lvl + 1
return lvl
If p = 1 /4 that means that the nodes with 2 levels will have
a probability of (1/4)/ 4 = 1/16 to show and the the nodes with
3 levels will have a probability of (1/16)/4 = 1/64 to appear,
but i was thinking more about the the nodes with 2 levels that
have a probability of 1/16 to appear, a probability of 1/16
means that there is a probability of 15/16 to not appear, but
a probability of 15/16 is greater enough and this can make the system
to degenerates towards the "worst" case, so how can we guarranty
that the system will not degenarate towards the worst case with
the nodes with 2 levels or above ? this is not good for realtime systems
i think and this is not good if you are constructing your a bigger
in-memory database with your skiplist, your database will get too slow
and this is not good..
Other than that, in mathematics of probability we say that if an event
have a probability 1/1000000000 to appear that means that the event
is very improbable to appear , but what i want to say is that
this is not a proof that it will not appear, because the event
can appear at ANY MOMENT and this is what also i want to explain...
Thank you,
Amine Moulay Ramdane.