Selección de nodos con probabilidad proporcional a la confianza

Question

¿Alguien sabe de una estructura algoritmo o los datos relativos a la selección de artículos, con una probabilidad de que sean seleccionados proporcional a algún valor que se asigna? En otras palabras: http://en.wikipedia.org/wiki/Sampling_% 28statistics% 29 # Probability_proportional_to_size_sampling

El contexto aquí es un sistema de reputación descentralizada y, por tanto, el valor que se asigna es el valor de la confianza de un usuario en otro. En este sistema todos los nodos o bien comienzan como amigos que están completamente de confianza o incógnitas que son completamente no fiable. Esto no es útil por sí mismo en una gran red P2P, ya que habrá muchos más nodos que usted tiene amigos y lo que necesita saber en quién confiar en el gran grupo de usuarios que no son tus amigos directos, por lo que he implementado un sistema de confianza dinámico en el que las incógnitas se puede ganar la confianza a través de las relaciones amigo-de-un-amigo.

Cada tanto cada usuario seleccionará un número fijo (en aras de la velocidad y ancho de banda) de nodos de destino para volver a calcular su confianza basado en la cantidad de otro número fijo seleccionado de nodos intermedios confían en ellos. La probabilidad de seleccionar un nodo de destino para el recálculo será inversamente proporcional a su confianza actual para que incógnitas tienen una buena oportunidad de llegar a ser mejor conocida. Los nodos intermedios serán seleccionados de la misma manera, excepto que la probabilidad de selección de un intermediario es proporcional a su confianza actual.

He escrito una solución simple a mí mismo, pero es bastante lento y me gustaría encontrar una biblioteca de C ++ para manejar este aspecto para mí. Me he hecho, por supuesto, mi propia búsqueda y he conseguido encontrar TRSL la que estoy cavando a través de este momento. Ya que parece un problema bastante simple y tal vez común, que sería de esperar que haya muchos más bibliotecas de C ++ que podría utilizar para esto, así que estoy haciendo esta pregunta con la esperanza de que alguien aquí puede arrojar alguna luz sobre esto.

Answer 1

Esto es lo que haría:

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

Por supuesto, puede repetir el segundo bucle tantas veces como desee, la elección de un nuevo r cada vez, para generar múltiples muestras.