¿Cuál es la mejor manera de elegir un subconjunto aleatorio de una colección?

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

Pregunta

Tengo un conjunto de objetos en un Vector del que me gustaría seleccionar un subconjunto aleatorio (por ejemplo, 100 elementos que regresan; elija 5 al azar). En mi primer pase (muy apresurado) hice una solución extremadamente simple y quizás demasiado inteligente: 

Vector itemsVector = getItems();

Collections.shuffle(itemsVector);
itemsVector.setSize(5);

Si bien esto tiene la ventaja de ser agradable y simple, sospecho que no va a escalar muy bien, es decir, Collections.shuffle () debe ser O (n) al menos. Mi alternativa menos inteligente es 

Vector itemsVector = getItems();

Random rand = new Random(System.currentTimeMillis()); // would make this static to the class    

List subsetList = new ArrayList(5);
for (int i = 0; i < 5; i++) {
     // be sure to use Vector.remove() or you may get the same item twice
     subsetList.add(itemsVector.remove(rand.nextInt(itemsVector.size())));
}

¿Alguna sugerencia sobre mejores formas de extraer un subconjunto aleatorio de una Colección?

¿Fue útil?

Solución

Jon Bentley analiza esto en 'Perlas de programación' o 'Más perlas de programación'. Debe tener cuidado con su proceso de selección de N de M, pero creo que el código que se muestra funciona correctamente. En lugar de barajar aleatoriamente todos los elementos, puede hacer la barajadura aleatoria solo barajando las primeras N posiciones, lo cual es un ahorro útil cuando N & Lt; & Lt; M.

Knuth también analiza estos algoritmos: creo que sería Vol 3 " Ordenar y buscar " ;, pero mi conjunto está empaquetado en espera de una mudanza de casa, así que no puedo verificarlo formalmente.

Otros consejos

@Jonathan,

Creo que esta es la solución de la que estás hablando: 

void genknuth(int m, int n)
{    for (int i = 0; i < n; i++)
         /* select m of remaining n-i */
         if ((bigrand() % (n-i)) < m) {
             cout << i << "\n";
             m--;
         }
}

Está en la página 127 de Programming Pearls por Jon Bentley y se basa en la implementación de Knuth.

EDITAR: acabo de ver una modificación adicional en la página 129: 

void genshuf(int m, int n)
{    int i,j;
     int *x = new int[n];
     for (i = 0; i < n; i++)
         x[i] = i;
     for (i = 0; i < m; i++) {
         j = randint(i, n-1);
         int t = x[i]; x[i] = x[j]; x[j] = t;
     }
     sort(x, x+m);
     for (i = 0; i< m; i++)
         cout << x[i] << "\n";
}

Esto se basa en la idea de que " ... necesitamos mezclar solo los primeros elementos m de la matriz ... "

Si está intentando seleccionar k elementos distintos de una lista de n, los métodos que proporcionó anteriormente serán O (n) u O (kn), porque al eliminar un elemento de un Vector, una copia de matriz desplazará todo los elementos abajo.

Dado que está solicitando la mejor manera, depende de lo que se le permita hacer con su lista de entrada.

Si es aceptable modificar la lista de entrada, como en sus ejemplos, simplemente puede intercambiar k elementos aleatorios al comienzo de la lista y devolverlos en el tiempo O (k) de esta manera: 

public static <T> List<T> getRandomSubList(List<T> input, int subsetSize)
{
    Random r = new Random();
    int inputSize = input.size();
    for (int i = 0; i < subsetSize; i++)
    {
        int indexToSwap = i + r.nextInt(inputSize - i);
        T temp = input.get(i);
        input.set(i, input.get(indexToSwap));
        input.set(indexToSwap, temp);
    }
    return input.subList(0, subsetSize);
}

Si la lista debe terminar en el mismo estado en que comenzó, puede realizar un seguimiento de las posiciones que intercambió y luego devolver la lista a su estado original después de copiar la sublista seleccionada. Esta sigue siendo una solución O (k).

Sin embargo, si no puede modificar la lista de entrada y k es mucho menor que n (como 5 de 100), sería mucho mejor no eliminar los elementos seleccionados cada vez, sino simplemente seleccionar cada elemento, y si alguna vez obtienes un duplicado, tíralo y vuelve a seleccionarlo. Esto le dará O (kn / (n-k)) que todavía está cerca de O (k) cuando n domina k. (Por ejemplo, si k es menor que n / 2, entonces se reduce a O (k)).

Si k no está dominado por n, y no puede modificar la lista, podría copiar su lista original y usar su primera solución, porque O (n) será tan bueno como O (k).

Como otros han notado, si usted depende de una fuerte aleatoriedad donde cada sublista es posible (e imparcial), definitivamente necesitará algo más fuerte que java.util.Random. Ver java.security.SecureRandom.

Escribí una implementación eficiente de esta una forma de probar que está aquí .

Se basa en una implementación de Durstenfeld de la mezcla aleatoria de Fisher-Yates.

Sin embargo, su segunda solución de usar Random para elegir un elemento parece sólida:

¿Cuánto cuesta eliminar? Porque si eso necesita reescribir la matriz en una nueva porción de memoria, entonces ha realizado operaciones O (5n) en la segunda versión, en lugar de la O (n) que quería antes.

Puede crear una matriz de booleanos establecida en falso y luego: 

for (int i = 0; i < 5; i++){
   int r = rand.nextInt(itemsVector.size());
   while (boolArray[r]){
       r = rand.nextInt(itemsVector.size());
   }
   subsetList.add(itemsVector[r]);
   boolArray[r] = true;
}

Este enfoque funciona si su subconjunto es más pequeño que su tamaño total por un margen significativo. A medida que esos tamaños se acercan entre sí (es decir, 1/4 del tamaño o algo así), obtendría más colisiones en ese generador de números aleatorios. En ese caso, haría una lista de enteros del tamaño de su matriz más grande, y luego barajaría esa lista de enteros, y sacaría los primeros elementos de eso para obtener sus indeces (no colisionantes). De esa manera, tiene el costo de O (n) en la construcción de la matriz de enteros, y otro O (n) en la combinación aleatoria, pero no puede haber colisiones de un verificador interno mientras que el O (5n) potencial que elimina puede costar.

Yo personalmente optaría por su implementación inicial: muy conciso. Las pruebas de rendimiento mostrarán qué tan bien se escala. Implementé un bloque de código muy similar en un método maltratado de manera decente y se amplió lo suficiente. El código particular se basaba en matrices que contenían & Gt; 10,000 elementos también. 

Set<Integer> s = new HashSet<Integer>()
// add random indexes to s
while(s.size() < 5)
{
    s.add(rand.nextInt(itemsVector.size()))
}
// iterate over s and put the items in the list
for(Integer i : s)
{
    out.add(itemsVector.get(i));
}

Esta es una pregunta muy similar sobre stackoverflow.

Para resumir mis respuestas favoritas de esa página (la primera del usuario Kyle):

  • Solución O (n) : Itere a través de su lista y copie un elemento (o referencia a él) con probabilidad (#needed / #remaining). Ejemplo: si k = 5 yn = 100, entonces toma el primer elemento con el problema 5/100. Si copia ese, elige el siguiente con el problema 4/99; pero si no tomó el primero, el problema es 5/99.
  • O (k log k) u O (k 2 ) : Cree una lista ordenada de k índices (números en {0, 1, ..., n -1}) eligiendo aleatoriamente un número & Lt; n, luego elegir aleatoriamente un número < n-1, etc. En cada paso, debe recalibrar su elección para evitar colisiones y mantener las probabilidades uniformes. Como ejemplo, si k = 5 yn = 100, y su primera opción es 43, su próxima opción está en el rango [0, 98], y si es & Gt; = 43, entonces le agrega 1 . Entonces, si tu segunda opción es 50, entonces le sumas 1 y tienes {43, 51}. Si su próxima opción es 51, agregue 2 para obtener {43, 51, 53}.

Aquí hay algunos pseudopython - 

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

Estoy diciendo que la complejidad del tiempo es O (k 2 ) u O (k log k) porque depende de qué tan rápido puede buscar e insertar en su contenedor para s. Si s es una lista normal, una de esas operaciones es lineal y obtienes k ^ 2. Sin embargo, si está dispuesto a construir s como un árbol binario equilibrado, puede obtener el tiempo O (k log k).

dos soluciones que no creo que aparezcan aquí: la correspondiente es bastante larga y contiene algunos enlaces, sin embargo, no creo que todas las publicaciones se relacionen con el problema de elegir un conjunto de K elementos de un conjunto de N elementos. [Por & Quot; set & Quot ;, me refiero al término matemático, es decir, todos los elementos aparecen una vez, el orden no es importante].

Sol 1: 

//Assume the set is given as an array:
Object[] set ....;
for(int i=0;i<K; i++){
randomNumber = random() % N;
    print set[randomNumber];
    //swap the chosen element with the last place
    temp = set[randomName];
    set[randomName] = set[N-1];
    set[N-1] = temp;
    //decrease N
    N--;
}

Esto se parece a la respuesta que dio Daniel, pero en realidad es muy diferente. Es de tiempo de ejecución O (k).

Otra solución es usar algunas matemáticas: considere los índices de la matriz como Z_n y, por lo tanto, podemos elegir aleatoriamente 2 números, x que es co-primo para n, es decir, chhose gcd (x, n) = 1 y otro, a, que es " punto de partida < !> quot; - luego la serie: a% n, a + x% n, a + 2 * x% n, ... a + (k-1) * x% n es una secuencia de números distintos (siempre que k < = n).

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