Skiplast besoin de fonction aléatoire expliqué

Question

j'ai lu sur la mise en œuvre skipList en C++ et je ne comprends pas cette fonction aléatoire:

float frand() { 
    return (float) rand()/RAND_MAX; 
} 
int random_level() { 
    static bool first = true; 

    if (first) { 
     srand((unsigned)time(NULL)); 
     first = false; 
    } 

    int lvl = (int)(log(frand())/log(1.-P)); 
    return lvl < MAX_LEVEL ? lvl : MAX_LEVEL; 
} 

Merci pour la lecture et je suis en attente de votre réponse :)

Answer 1

Ainsi, la façon dont les skiplists fonctionnent est de faire en sorte que le nouveau nœud se connecte à d'autres nœuds à des niveaux, choisissant au hasard d'ajouter ou non un niveau. Normalement, cela signifie retourner une pièce une fois pour chaque niveau auquel le nouveau noeud est destiné à être lié. Si ça monte, vous montez d'un niveau et vous retournez, si vous avez terminé, vous avez terminé.

Ce que cela fait est-il simule le retournement de cette pièce à plusieurs reprises, mais seulement appeler la source de nombres aléatoires une fois, et l'application d'une fonction avec la même distribution de probabilité que la somme flips pièces consécutive

Answer 2

// this function generates a random number between 0 and 1 
float frand() { 
    return (float) rand()/RAND_MAX; // RAND_MAX is the biggest possible value returned by rand() 
} 
int random_level() { 
    static bool first = true; // a static variable to track whether or not this is the first run of the function 

    if (first) { // if this is the first time the function has been called... 
     srand((unsigned)time(NULL)); // generate a seed from the current time 
     first = false; // set first to false 
    } 

    int lvl = (int)(log(frand())/log(1.-P)); // generate the value of lvl with some weird log functions 
    return lvl < MAX_LEVEL ? lvl : MAX_LEVEL; // cap the value to MAX_LEVEL, and return 
}