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

Question

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

Контекстом здесь является децентрализованная система репутации, и, следовательно, прилагаемая ценность - это ценность доверия одного пользователя к другому.В этой системе все узлы либо начинаются как друзья, которым полностью доверяют, либо как неизвестные, которым полностью не доверяют.Само по себе это бесполезно в большой сети 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 каждый раз, чтобы сгенерировать несколько выборок.