algorithm - sorteos - Selección eficiente de un conjunto de elementos aleatorios de una lista vinculada

random android ejemplo (6)

Supongamos que tengo una lista vinculada de números de longitud N N es muy grande y no sé de antemano el valor exacto de N

¿Cómo puedo escribir de manera más eficiente una función que devolverá k números completamente aleatorios de la lista?

¿Por qué no puedes hacer algo como

List GetKRandomFromList(List input, int k) List ret = new List(); for(i=0;i<k;i++) ret.Add(input[Math.Rand(0,input.Length)]); return ret;

Estoy seguro de que no te refieres a algo tan simple, ¿puedes especificar más?

Bueno, necesitas saber qué N es en tiempo de ejecución al menos, incluso si esto implica hacer un pase extra sobre la lista para contarlos. El algoritmo más simple para hacer esto es simplemente elegir un número aleatorio en N y eliminar ese elemento, repetido k veces. O bien, si está permitido devolver números repetidos, no elimine el artículo.

A menos que tenga un N muy grande y requisitos de rendimiento muy estrictos, este algoritmo se ejecuta con complejidad O(N*k) , que debería ser aceptable.

Editar: No importa, el método de Tom Hawtin es mucho mejor. Seleccione primero los números aleatorios, luego recorra la lista una vez. La misma complejidad teórica, creo, pero mucho mejor tiempo de ejecución esperado.

Esto se llama un problema de muestreo de yacimientos . La solución simple es asignar un número aleatorio a cada elemento de la lista como lo ve, luego mantener los elementos k superiores o inferiores según lo ordenado por el número aleatorio.

Hay un algoritmo muy bueno y eficiente para esto usando un método llamado muestreo de yacimientos .

Déjame comenzar dándote su historia :

Knuth llama a este Algoritmo R en p. 144 de su edición de 1997 de Seminumerical Algorithms (volumen 2 de The Art of Computer Programming), y proporciona algún código para ello allí. Knuth atribuye el algoritmo a Alan G. Waterman. A pesar de una larga búsqueda, no he podido encontrar el documento original de Waterman, si es que existe, que puede ser el motivo por el que con mayor frecuencia ve a Knuth citado como la fuente de este algoritmo.

McLeod y Bellhouse, 1983 (1) proporcionan una discusión más completa que Knuth, así como la primera prueba publicada (de la que tengo conocimiento) de que el algoritmo funciona.

Vitter 1985 (2) revisa el algoritmo R y luego presenta tres algoritmos adicionales que proporcionan el mismo resultado, pero con un giro. En lugar de elegir incluir u omitir cada elemento entrante, su algoritmo predetermina el número de elementos entrantes que se saltean. En sus pruebas (que, ciertamente, ahora están desactualizadas), esto redujo drásticamente el tiempo de ejecución al evitar la generación de números aleatorios y las comparaciones en cada número entrante.

En pseudocódigo, el algoritmo es:

Let R be the result array of size s Let I be an input queue > Fill the reservoir array for j in the range [1,s]: R[j]=I.pop() elements_seen=s while I is not empty: elements_seen+=1 j=random(1,elements_seen) > This is inclusive if j<=s: R[j]=I.pop() else: I.pop()

Tenga en cuenta que he escrito específicamente el código para evitar especificar el tamaño de la entrada. Esa es una de las propiedades geniales de este algoritmo: puede ejecutarlo sin necesidad de conocer el tamaño de la entrada de antemano y aún así le asegura que cada elemento que encuentre tiene la misma probabilidad de terminar en R (es decir, no hay parcialidad). Además, R contiene una muestra justa y representativa de los elementos que el algoritmo ha considerado en todo momento. Esto significa que puede usar esto como un algoritmo en línea .

¿Por qué funciona esto?

McLeod y Bellhouse (1983) proporcionan una prueba usando las matemáticas de las combinaciones. Es bonito, pero sería un poco difícil de reconstruir aquí. Por lo tanto, he generado una prueba alternativa que es más fácil de explicar.

Procedemos vía prueba por inducción.

Digamos que queremos generar un conjunto de elementos y que ya hemos visto n>s elementos.

Supongamos que nuestros elementos actuales ya se han elegido con la probabilidad s/n .

Por la definición del algoritmo, elegimos el elemento n+1 con probabilidad s/(n+1) .

Cada elemento que ya forma parte de nuestro conjunto de resultados tiene una probabilidad 1/s de ser reemplazado.

La probabilidad de que un elemento del conjunto de resultados n seeen se reemplace en el conjunto de resultados n+1 es por lo tanto (1/s)*s/(n+1)=1/(n+1) . Por el contrario, la probabilidad de que un elemento no sea reemplazado es 1-1/(n+1)=n/(n+1) .

Por lo tanto, el conjunto de resultados n+1 contiene un elemento, ya sea si formaba parte del conjunto de resultados n see y no se reemplazó, esta probabilidad es (s/n)*n/(n+1)=s/(n+1) --- o si el elemento fue elegido --- con probabilidad s/(n+1) .

La definición del algoritmo nos dice que los primeros elementos se incluyen automáticamente como los primeros n=s miembros del conjunto de resultados. Por lo tanto, el conjunto de resultados n-seen incluye cada elemento con s/n probabilidad s/n (= 1) que nos proporciona el caso base necesario para la inducción.

Referencias

McLeod, A. Ian y David R. Bellhouse. "Un algoritmo conveniente para dibujar una muestra aleatoria simple". Revista de la Royal Statistical Society. Serie C (Estadística Aplicada) 32,2 (1983): 182-184. ( Link )
Vitter, Jeffrey S. "Muestreo aleatorio con un depósito". Transacciones de ACM en software matemático (TOMS) 11.1 (1985): 37-57. ( Link )

Si no conoce la longitud de la lista, tendrá que atravesarla para garantizar selecciones al azar. El método que he usado en este caso es el descrito por Tom Hawtin ( 54070 ). Mientras recorre la lista, mantiene k elementos que forman su selección aleatoria hasta ese punto. (Inicialmente, solo agrega los primeros k elementos que encuentre.) Luego, con probabilidad k/i , reemplaza un elemento aleatorio de su selección con el elemento i ésimo de la lista (es decir, el elemento en el que se encuentra, en ese momento).

Es fácil mostrar que esto da una selección aleatoria. Después de ver m elementos ( m > k ), tenemos que cada uno de los primeros m elementos de la lista son parte de su selección aleatoria con una probabilidad k/m . Que esto inicialmente se sostiene es trivial. Luego, para cada elemento m+1 , póngalo en su selección (reemplazando un elemento aleatorio) con probabilidad k/(m+1) . Ahora necesita mostrar que todos los demás elementos también tienen probabilidad k/(m+1) de ser seleccionado. Tenemos que la probabilidad es k/m * (k/(m+1)*(1-1/k) + (1-k/(m+1))) (es decir, la probabilidad de que ese elemento estuviera en la lista multiplicado por probabilidad de que todavía esté allí). Con el cálculo puede demostrar claramente que esto es igual a k/(m+1) .

Sugeriría: Primero encuentre sus k números aleatorios. Ordenarlos Luego, recorra una vez la lista vinculada y sus números aleatorios.

Si de alguna manera no sabe la longitud de su lista vinculada (¿cómo?), Puede tomar la primera k en una matriz, luego para el nodo r, generar un número aleatorio en [0, r), y si eso es menos que k, reemplaza el cuarto elemento de la matriz. (No del todo convencido de que no sesga ...)

Aparte de eso: "Si fuera tú, no estaría comenzando desde aquí". ¿Estás seguro de que la lista vinculada es adecuada para tu problema? ¿No hay una mejor estructura de datos, como una buena lista de arreglos planos antiguos?