Скипласт случайная функция нуждается в объяснении

Question

Я читал о реализации skipList в C ++ и не понимаю эту случайную функцию:

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;
} 

Спасибо за чтение, и я жду вашего ответа:)

Answer 1

Таким образом, способ работы скиплистов заключается в том, что новый узел связывается с другими узлами на уровнях, произвольно выбирая, добавлять уровень или нет.Обычно это означает подбрасывание монеты один раз для каждого уровня, на который новый узел предназначен для ссылки.если он поднимается головой, вы поднимаетесь на уровень и снова переворачиваетесь, если вы делаете хвост.

Что он делает, так это то, что он симулирует подбрасывание этой монеты несколько раз, но вызывает только случайный источникодин раз и применение функции с тем же распределением вероятностей, что и при суммировании последовательных бросков монет

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
}