Obtiene un elemento aleatorio de una colección secuencial

Question

Hablo con una API que me da un java.util.Iterator sobre una colección. Eso significa que puedo iterar sobre él, pero no puedo obtener acceso directo/aleatorio a los elementos.

Ahora a mi problema: quiero obtener un elemento aleatorio de esta colección. ¿Cómo puedo hacer eso? Supongo que podría crear una nueva colección que permita el acceso directo, pero ¿no consume poca memoria? También podría iterar sobre toda la colección y para cada elemento "tirar un dado" para ver si debería tomar ese elemento y salir de la iteración o continuar. Pero luego necesito el tamaño de la colección y no puedo obtener eso del iterador.

Gracias de antemano.

Answer 1

Hay una manera de hacerlo en un pase a través de la colección que no usa mucha memoria extra (solo el tamaño de un elemento de la colección más un flotador). En pseudocódigo:

• Iterate a través de la colección.
• Para cada elemento, genere un flotante aleatorio.
• Si el flotante es el más bajo (o el más alto, no importa) que haya visto hasta ahora, almacene el elemento actual de la colección en una variable temporal. (También almacene el nuevo valor aleatorio más bajo.)
• Una vez que llega al final de la colección, tiene un elemento aleatorio en la variable temp.

Obviamente, esto tiene el inconveniente de iterar a través de la colección completa cada vez que lo llama, pero no tiene muchas opciones con las limitaciones que enfrenta.

Actualización: El nombre de este tipo de problema finalmente regresó a mí. Esto se llama Reservoir sampling.

Answer 2

Al iterar, usted sabe cuántos objetos ha iterado, por lo que sabe la probabilidad de que el elemento actual sea uno para seleccionar aleatoriamente. Entonces solo necesita mantener un conteo y el elemento seleccionado al azar actualmente.

public static <T> T selectRandom(final Iterator<T> iter, final Random random) { 
    if (!iter.hasNext()) { 
     throw new IllegalArgumentException(); 
    } 
    if (random == null) { 
     throw new NullPointerException(); 
    } 
    T selected = iter.next(); 
    int count = 1; 
    while (iter.hasNext()) { 
     final T current = iter.next(); 
     ++count; 
     if (random.nextInt(count) == 0) { 
      selected = current; 
     } 
    } 
    return selected; 
} 

(desbordamiento de pila de responsabilidad: no compilados, y ciertamente no evaluados.)

Véase también la sección sobre Collections.shuffle en Puzzlers Java.

Answer 3

La única solución segura (en caso de que se sabe/garantizada No existen más datos) es la forma que ha descrito: Crear una List del Iterator y elegir un elemento aleatorio.

Si el tamaño de la colección subyacente es siempre el mismo, puede reducir el esfuerzo a la mitad en un promedio: simplemente use el elemento que obtuvo después de Iterator.next() después de un número aleatorio de iteraciones.

BTW: ¿Realmente está utilizando una colección que implementa java.util.Iterator?

Answer 4

Depende de los requisitos, si el tamaño de la colección no es muy grande entonces esto va a hacerlo, de lo contrario, en caso de que iterar y utilizar el método dado que usted ha mencionado

List<Object> list = Arrays.asList(yourCollection.toArray(new Object[0])); 
result = list.get(new Random().nextInt(list.size())); 

Answer 5

Si realmente no tienen ningún acceso aleatorio, y usted tiene una lista muy grande, así que no se puede copiar a continuación, puede hacer lo siguiente:

int n = 2 
iterator i = ... 
Random rand = new Random(); 
Object candidate = i.next(); 
while (i.hasNext()) { 
    if (rand.nextInt(n)) { 
     candidate = i.next(); 
    } else { 
     i.next(); 
    } 
    n++; 
} 
return candidate; 

Esto retendrá un elemento aleatorio de una lista, pero requiere que recorra toda la lista. Si desea un valor distribuido de manera verdaderamente uniforme, no tiene más remedio que hacer esto.

Alternativamente, si el número de elementos es pequeño, o si desea una permutación aleatoria de una lista de tamaño desconocido (en otras palabras, desea acceder a todos los elementos de la lista en un orden aleatorio), entonces te recomiendo copiando todas las referencias a una nueva lista (esta no será una cantidad significativa de memoria a menos que tenga millones de elementos, ya que solo está almacenando referencias). A continuación, utilice get con un entero aleatorio o utilice el método de mezcla aleatorio java.util.Collections estándar para permutar la lista.

Answer 6

Utilizado para generar datos de prueba ponderados. no es eficiente, pero es fácil

class ProbabilitySet<E> { 

    Set<Option<E>> options = new HashSet<Option<E>>(); 

    class Option<E> { 
     E object; 
     double min; 
     double max; 

     private Option(E object, double prob) { 
      this.object = object; 
      min = totalProb; 
      max = totalProb + prob; 
     } 

     @Override 
     public String toString() { 
      return "Option [object=" + object + ", min=" + min + ", max=" + max + "]"; 
     } 
    } 

    double totalProb = 0; 
    Random rnd = new Random(); 

    public void add(E object, double probability){ 
     Option<E> tuple = new Option<E>(object, probability); 
     options.add(tuple); 
     totalProb += probability; 
    } 

    public E getRandomElement(){ 

     double no = rnd.nextDouble() * totalProb; 
     for (Option<E> tuple : options) { 
      if (no >= tuple.min && no < tuple.max){ 
       return tuple.object; 
      } 
     } 


     return null; // if this happens sumfink is wrong. 

    } 

    @Override 
    public String toString() { 
     return "ProbabilitySet [options=" + options + ", totalProb=" + totalProb + "]"; 
    } 

} 

NOTA: los parámetros de probabilidad estarán en relación con el total no a 1,0

Uso:

public static void main(String[] args) { 
    ProbabilitySet<String> stati = new ProbabilitySet<String>(); 
    stati.add("TIMEOUT", 0.2); 
    stati.add("FAILED", 0.2); 
    stati.add("SUCCESSFUL", 1.0); 

    for (int i = 0; i < 100; i++) { 
     System.out.println(stati.getRandomElement()); 
    } 

}