dimanche 27 septembre 2015

How is probability of skiplist node height Implement in redis when it comes to calculate the height of inserted node?

the follow is a function in t_zset.c in redis source. The purpose of zslRandomLevel is to get height for a new inserted node by stochastic algorithm. What makes me confused is the while condition. As I can understand, the probability of while condition to be true is 0.25,should the probability of this condition be 0.5? So, can someone help me understanding how much the probability of this condition and what is the theory of (random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF), cause I can replace it simply with random()<ZSKIPLIST_P?

int zslRandomLevel(void) {
    int level = 1;

    while ((random() & 0xFFFF) < (ZSKIPLIST_P * 0xFFFF))//ZSKIPLIST_P=0.25
        level += 1;

    return (level < ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}




Aucun commentaire:

Enregistrer un commentaire