Selecionando nós com probabilidade proporcional à confiança

Question

Alguém sabe de uma estrutura de algoritmo ou dados relativos à seleção de itens, com uma probabilidade de eles serem selecionados proporcional algum valor anexado? Em outras palavras: http://en.wikipedia.org/wiki/Sampling_% 28statistics% 29 # Probability_proportional_to_size_sampling

O contexto aqui é um sistema de reputação descentralizada e o valor atribuído é, portanto, o valor da confiança de um usuário tem em outro. Neste sistema todos os nós, quer começar como amigos que são completamente confiáveis ??ou desconhecidos que são completamente não confiável. Isso não é útil por si só em uma grande rede P2P, porque haverá muitos nós mais do que você tem amigos e que você precisa saber que a confiança no grupo grande de usuários que não são seus amigos diretos, assim que eu tiver implementado um sistema de confiança dinâmico em que incógnitas pode ganhar a confiança através de relacionamentos amigo-de-um-amigo.

De vez em quando cada usuário irá selecionar um número fixo (por causa da velocidade e largura de banda) de nós de destino para recalcular a sua confiança com base em quanto outro número fixo selecionado de nós intermediários confiar neles. A probabilidade de selecionar um nó de destino para o novo cálculo será inversamente proporcional à sua confiança atual para que incógnitas tem uma boa chance de se tornar mais conhecido. Os nós intermediários serão selecionados da mesma forma, exceto que a probabilidade de seleção de um intermediário é proporcional à sua confiança atual.

Eu escrevi uma solução simples mim, mas é um pouco lento e eu gostaria de encontrar uma biblioteca C ++ para lidar com esse aspecto para mim. Eu, claro, feito minha própria pesquisa e eu consegui encontrar TRSL que eu estou cavando através agora. Uma vez que parece ser um problema bastante simples e talvez comum, seria de esperar que haja muitos mais bibliotecas C ++ que eu poderia usar para isso, então eu estou fazendo esta pergunta na esperança de que alguém aqui pode lançar alguma luz sobre este assunto.

Answer 1

Este é o que eu faria:

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

Você pode de repetir claro que o segundo ciclo tantas vezes quanto quiser, escolher um novo r cada vez, para gerar várias amostras.