Selección aleatoria de un elemento de una lista ponderada

Question

Tengo una lista de 100.000 objetos. Cada elemento de lista tiene un "peso" asociado a él que es un int positivo de 1 a N.

¿Cuál es la forma más eficiente de seleccionar un elemento aleatorio de la lista? Quiero el comportamiento de que mi distribución de elementos elegidos al azar sea la misma que la distribución de los pesos en la lista.

Por ejemplo, si tengo una lista L = {1,1,2,5}, quiero que el 4º elemento se seleccione 5/9 de las veces, en promedio.

Supongamos inserciones y eliminaciones son comunes en esta lista, por lo que cualquier método que utiliza "tablas de área integrales" tendría que ser actualizado con frecuencia - la esperanza no es una solución con O (1) tiempo de ejecución y O (1) de memoria extra que se requiere.

Answer 1

Puede usar un árbol de búsqueda binaria aumentada para almacenar los elementos, junto con la suma de los pesos en cada subárbol. Esto le permite insertar y eliminar elementos y pesos como lo desee. Tanto el muestreo como las actualizaciones requieren O (lg n) tiempo por operación, y el uso del espacio es O (n).

El muestreo se logra generando un entero aleatorio en [1, S], donde S es la suma de todos los pesos (S se almacena en la raíz del árbol) y realiza una búsqueda binaria utilizando las sumas de peso almacenadas cada subárbol.

Answer 2

Una solución que se ejecuta en O (n) sería comenzar con la selección del primer elemento. Luego, para cada elemento siguiente, conserve el elemento que tiene o sustitúyalo por el siguiente. Deje w ser la suma de todos los pesos para los elementos considerados hasta ahora. Luego mantenga el anterior con probabilidad w/(w + x) y elija el nuevo con p = x/(w + x), donde x es el peso del siguiente elemento.

Answer 3

Si conoce la suma de los pesos (en su caso, 9) Y utiliza una estructura de datos de acceso aleatorio (lista implica O (n) tiempo de acceso), entonces se puede hacer rápido:

1) seleccione un elemento aleatorio (O (1)). Como hay 1/num_elems posibilidad de seleccionar un elemento en este paso, nos permite usar el impulso num_elems* para el paso 2), acelerando así el algoritmo.

2) calcular la probabilidad esperada: num_elems * (weight/total_weight)

3) toma un número aleatorio en el rango 0..1, y si es menor que la probabilidad esperada, usted tiene la salida. Si no, repita desde el paso 1)

Answer 4

Me gusta mucho la solución de jonderry, pero me pregunto si este problema necesita una estructura tan compleja como el árbol de búsqueda binaria aumentada. ¿Qué pasa si guardamos dos matrices, una con los pesos de entrada, digamos a = {1,1,2,5} y otra con los pesos acumulados (idea muy similar a la solución de jonderry) que sería b = {1,2,4 , 9}. Ahora genere un número aleatorio en [1 9] (digamos x) y búsqueda binaria en la matriz de suma acumulativa. Se anota la ubicación i donde b [i] < = x y b [i-1]> x y se devuelve [i]. Entonces, si el número aleatorio fuera 3, obtendríamos i = 3, y se devolvería [3] = 2. Esto garantiza la misma complejidad que la solución de árbol aumentada con una implementación más fácil.

Answer 5

Esto es lo que hice para resolverlo:

def rchoose(list1, weights): 
    ''' 
    list1 : list of elements you're picking from. 
    weights : list of weights. Has to be in the same order as the 
       elements of list1. It can be given as the number of counts 
       or as a probability. 
    ''' 

    import numpy as np 

    # normalizing the weights list 
    w_sum = sum(weights) 
    weights_normalized = [] 
    for w in weights: 
     weights_normalized.append(w/w_sum) 

    # sorting the normalized weights and the desired list simultaneously 
    weights_normalized, list1 = zip(*sorted(zip(weights_normalized, list1))) 

    # bringing the sorted tuples back to being lists 
    weights_normalized = list(weights_normalized) 
    list1 = list(list1) 

    # finalizing the weight normalization 
    dummy = []; count = 0 
    for item in weights_normalized: 
     count += item 
     dummy.append(count) 
    weights_normalized = dummy 

    # testing which interval the uniform random number falls in 
    random_number = np.random.uniform(0, 1) 
    for idx, w in enumerate(weights_normalized[:-1]): 
     if random_number <= w: 
      return list1[idx] 

    return list1[-1]