Para recuperar k números aleatorios a partir de una matriz de tamaño indeterminado utilizamos una técnica llamada embalse de muestreo. ¿Alguien puede destacar brevemente cómo sucede con un código de ejemplo?

InformationsquelleAutor Jony | 2010-04-10

3 Comentarios

  1. 31

    Yo en realidad no se dio cuenta de que había un nombre para esto, así que me resultó y llevó a la práctica a partir de cero:

    import random
    def random_subset( iterator, K ):
        result = []
        N = 0
    
        for item in iterator:
            N += 1
            if len( result ) < K:
                result.append( item )
            else:
                s = int(random.random() * N)
                if s < K:
                    result[ s ] = item
    
        return result
    

    De: http://web.archive.org/web/20141026071430/http://propersubset.com:80/2010/04/choosing-random-elements.html

    Con una prueba cerca de la final.

    • Donde es el accept it with probability s/k parte en el código? [ cita de algoritmo mencionado en blogs.msdn.com/spt/archive/2008/02/05/reservoir-sampling.aspx ]
    • Por coincidencia, parece que entre el artículo y el mío, se utilizan las mismas variables, pero para cosas diferentes. Mi «K» que parece ser su «S», y mi «N» (en el código) que parece ser su «K». En otras palabras, acepto las cosas con K/N probabilidad, donde N es el número actual de las cosas.
    • lo que quería preguntar era como fueron la aplicación de la probabilidad en el código. De todos modos, ahora entiendo. Gracias!
    • No comprender bien tu pregunta, pero me pueden explicar que el código un poco más si son específicos! =)
    • aquí mucho más simple explicación.
    • Gracias. Esto es super fácil de entender y empezar con lo basico.
    • Hay una manera de hacer esto para crear múltiples embalses de variados tamaños, desde una desenfrenada stream? Que es ser capaz de iterar sobre una secuencia de una vez y muestra de ellos en uno de los múltiples embalses? Asumir que cada embalse podría tener un tamaño diferente o igual tamaño.

  2. 8

    Siguientes Knuth de la (1981) descripción más de cerca, el Embalse de Muestreo (Algoritmo I) podría ser implementado de la siguiente manera:

    import random
    
    def sample(iterable, n):
        """
        Returns @param n random items from @param iterable.
        """
        reservoir = []
        for t, item in enumerate(iterable):
            if t < n:
                reservoir.append(item)
            else:
                m = random.randint(0,t)
                if m < n:
                    reservoir[m] = item
        return reservoir
    • ¿Cuál es la diferencia entre este y el la aceptó responder? Creo que esto es exactamente lo mismo, incluso si este código es el más elegante.
    • Esto puede estar directamente relacionado con la investigación publicada (Knuth, 1981), en caso de que alguien está interesado en más extendido en la explicación o Knuth de la prueba.
    • Donde 0 <= random.randint(0,t) <= t por aleatorio.randint.
  3. 1

    Java

    import java.util.Random;
    
    public static void reservoir(String filename,String[] list)
    {
        File f = new File(filename);
        BufferedReader b = new BufferedReader(new FileReader(f));
    
        String l;
        int c = 0, r;
        Random g = new Random();
    
        while((l = b.readLine()) != null)
        {
          if (c < list.length)
              r = c++;
          else
              r = g.nextInt(++c);
    
          if (r < list.length)
              list[r] = l;
    
          b.close();}
    }
    
    • Esta pregunta ya ha aceptado la respuesta de años hace…
    • Pero ahora en Java!

Dejar respuesta

Please enter your comment!
Please enter your name here