Seleccionar eficientemente un conjunto de elementos aleatorios de una lista vinculada

StackOverflow https://stackoverflow.com/questions/54059

Pregunta

Digamos 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 completamente números al azar ¿de la lista?

¿Fue útil?

Solución

Hay un algoritmo muy agradable y eficiente para esto que utiliza un método llamado muestreo de yacimientos.

Déjame empezar dándote su historia:

Knuth llama a este algoritmo R en la p.144 de su edición de 1997 de Algoritmos seminuméricos (volumen 2 de El arte de la programación informática), y proporciona algo de código allí.Knuth atribuye el algoritmo a Alan G.Barquero.A pesar de una larga búsqueda, no he podido encontrar el documento original de Waterman, si es que existe, lo que puede ser la razón por la que con mayor frecuencia verás a Knuth citado como la fuente de este algoritmo.

McLeod y Bellhouse, 1983 (1) proporciona una discusión más exhaustiva que Knuth, así como la primera prueba publicada (que yo sepa) 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 toque diferente.En lugar de elegir incluir u omitir cada elemento entrante, su algoritmo predetermina el número de elementos entrantes que se omitirán.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 de 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 escribí el código específicamente para evitar especificar el tamaño de la entrada.Esa es una de las propiedades interesantes de este algoritmo:puedes ejecutarlo sin necesidad de saber el tamaño de la entrada de antemano y aún te asegura que cada elemento que encuentres tiene la misma probabilidad de terminar en R (es decir, no hay sesgo).Además, R Contiene una muestra justa y representativa de los elementos que el algoritmo ha considerado en cada momento.Esto significa que puedes usar esto como un algoritmo en línea.

¿Por qué funciona esto?

McLeod y Bellhouse (1983) proporcionan una demostración utilizando la matemática de combinaciones.Es bonito, pero sería un poco difícil reconstruirlo 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 s elementos y que ya hemos visto n>s elementos.

Supongamos que nuestro actual s Los elementos ya han sido elegidos cada uno con 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 de la n-el conjunto de resultados visto se reemplaza en el n+1-el conjunto de resultados visto 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, la n+1-el conjunto de resultados visto contiene un elemento si era parte del n-visto el conjunto de resultados y no fue reemplazado---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 la primera s Los elementos se incluyen automáticamente como los primeros. n=s miembros del conjunto de resultados.Por lo tanto, la n-seen El conjunto de resultados incluye cada elemento con s/n (=1) probabilidad que nos da el caso base necesario para la inducción.

Referencias

  1. McLeod, A.Ian y David R.Campanario."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.(Enlace)

  2. Vitter, Jeffrey S."Muestreo aleatorio con un depósito". Transacciones ACM en software matemático (TOMS) 11.1 (1985):37-57.(Enlace)

Otros consejos

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

Yo sugeriría:Primero encuentra tus k números aleatorios.Ordenarlos.Luego recorra tanto la lista vinculada como sus números aleatorios una vez.

Si de alguna manera no conoce la longitud de su lista enlazada (¿cómo?), entonces podría tomar la primera k en una matriz, luego, para el nodo r, generar un número aleatorio en [0, r), y si eso es menor Gracias a k, reemplace el elemento r de la matriz.(No estoy del todo convencido de que eso no sea parcial...)

Aparte de eso:"Si yo fuera tú, no comenzaría desde aquí". ¿Está seguro de que la lista vinculada es adecuada para su problema?¿No existe una mejor estructura de datos, como una buena lista de matriz plana?

Si no conoce la longitud de la lista, tendrá que recorrerla por completo para garantizar selecciones aleatorias.El método que he utilizado en este caso es el descrito por Tom Hawtin (54070).Mientras recorre la lista que mantiene k elementos que forman su selección aleatoria hasta ese punto.(Inicialmente solo agregas el primero k elementos que encuentres.) Entonces, con probabilidad k/i, reemplazas un elemento aleatorio de tu selección con el iº elemento de la lista (es decir,el elemento en el que te encuentras, en ese momento).

Es fácil demostrar que esto da una selección aleatoria.Después de ver m elementos (m > k), tenemos que cada uno de los primeros m Los elementos de la lista son parte de su selección aleatoria con una probabilidad. k/m.Que esto se cumpla inicialmente es trivial.Luego para cada elemento m+1, lo pones en tu selección (reemplazando un elemento aleatorio) con probabilidad k/(m+1).Ahora necesitas demostrar 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.probabilidad de que el elemento estuviera en la lista multiplicada por la probabilidad de que todavía esté allí).Con el cálculo puedes demostrar directamente que esto es igual a k/(m+1).

Bueno, necesitas saber qué es N al menos en tiempo de ejecución, incluso si esto implica hacer una pasada adicional por 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, si está permitido devolver números repetidos, no elimine el artículo.

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

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

¿Por qué no puedes simplemente 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?

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top