Выбор узлов с вероятностью, пропорциональной доверию

Question

Кто-нибудь знает алгоритм или структуру данных, относящихся к выбору элементов, с вероятностью того, что они будут выбраны пропорционально некоторому приложенному значению? Другими словами: http://en.wikipedia.org/wiki/Sampling_%28statistics%29

Здесь контекст представляет собой децентрализованную систему репутации, и поэтому прилагаемое значение - это значение доверия, которое один пользователь оказывает другому. В этой системе все узлы либо начинаются как друзья, которым полностью доверяют, либо неизвестные, которым полностью не доверяют. Это само по себе бесполезно в большой сети P2P, потому что будет гораздо больше узлов, чем у вас есть друзья, и вам нужно знать, кому можно доверять в большой группе пользователей, которые не являются вашими прямыми друзьями, поэтому я реализовал динамическая система доверия, в которой неизвестные могут завоевать доверие посредством отношений друг с другом.

Время от времени каждый пользователь выбирает фиксированное число (ради скорости и полосы пропускания) целевых узлов, чтобы пересчитать их доверие на основе того, насколько доверяет им другое выбранное фиксированное число промежуточных узлов. Вероятность выбора целевого узла для пересчета будет обратно пропорциональна его текущему доверию, так что неизвестные имеют хороший шанс стать более известным. Промежуточные узлы будут выбраны таким же образом, за исключением того, что вероятность выбора посредника пропорциональна его текущему доверию.

Я сам написал простое решение, но оно довольно медленное, и я хотел бы найти библиотеку C++, чтобы справиться с этим аспектом для меня. Я, конечно, сделал свой собственный поиск, и мне удалось найти TRSL, который я сейчас копаю. Поскольку это кажется довольно простой и, возможно, распространенной проблемой, я ожидаю, что будет еще много библиотек C++, которые я мог бы использовать для этого, поэтому я задаю этот вопрос в надежде, что кто-то здесь сможет пролить свет на это.

Answer 1

Вот что я бы сделал:

int select(double *weights, int n) {
    // This step only necessary if weights can be arbitrary
    // (we know total = 1.0 for probabilities)
    double total = 0;
    for (int i = 0; i < n; ++i) {
        total += weights[i];
    }

    // Cast RAND_MAX to avoid overflow
    double r = (double) rand() * total / ((double) RAND_MAX + 1);
    total = 0;
    for (int i = 0; i < n; ++i) {
        // Guaranteed to fire before loop exit
        if (total <= r && total + weights[i] > r) {
            return i;
        }

        total += weights[i];
    }
}

Конечно, вы можете повторить второй цикл столько раз, сколько хотите, выбрав новый r каждый раз, чтобы сгенерировать несколько образцов.