arrays - una - view lenta mysql

¿Cómo se genera eficientemente una lista de enteros K no repetitivos entre 0 y un límite superior N

Question

Esta pregunta ya tiene una respuesta aquí:

• Números aleatorios únicos (no repetitivos) en O (1)? 21 respuestas

La pregunta proporciona todos los datos necesarios: qué es un algoritmo eficiente para generar una secuencia de K enteros no repetitivos dentro de un intervalo dado [0, N-1] . El algoritmo trivial (generar números aleatorios y, antes de agregarlos a la secuencia, buscarlos para ver si ya estaban allí) es muy costoso si K es grande y está lo suficientemente cerca de N.

El algoritmo proporcionado en la selección eficiente de un conjunto de elementos aleatorios de una lista vinculada parece más complicado de lo necesario y requiere cierta implementación. Acabo de encontrar otro algoritmo que parece hacer bien el trabajo, siempre que conozca todos los parámetros relevantes, en una sola pasada.

Answer 1

Acelera el algoritmo trivial almacenando los números K en una tienda hash. Conocer K antes de empezar elimina toda la ineficacia de insertar en un mapa hash, y aún así obtiene el beneficio de una búsqueda rápida.

Answer 2

De hecho, es posible hacerlo en espacio proporcional a la cantidad de elementos seleccionados, en lugar del tamaño del conjunto desde el que se selecciona, independientemente de la proporción del conjunto total que seleccione. Para ello, genere una permutación aleatoria y luego seleccione de la siguiente manera:

Elija un cifrado de bloque, como TEA o XTEA. Utilice plegado XOR para reducir el tamaño del bloque a la potencia más pequeña de dos más grande que el conjunto que está seleccionando. Use la semilla aleatoria como la clave del cifrado. Para generar un elemento n en la permutación, cifra n con el cifrado. Si el número de salida no está en su conjunto, encripte eso. Repita hasta que el número esté dentro del conjunto. En promedio, tendrá que hacer menos de dos encriptaciones por número generado. Esto tiene el beneficio adicional de que si tu semilla está criptográficamente segura, también lo es tu permutación completa.

Escribí sobre esto con mucho más detalle here .

Answer 3

El módulo aleatorio de la biblioteca de Python lo hace extremadamente fácil y efectivo:

from random import sample
print sample(xrange(N), K)

sample función de sample devuelve una lista de K elementos únicos elegidos de la secuencia dada.
xrange es un "emulador de lista", es decir, se comporta como una lista de números consecutivos sin crearlo en la memoria, lo que lo hace superrápido para tareas como esta.

Answer 4

El siguiente código (en C, origen desconocido) parece resolver el problema extremadamente bien:

 /* generate N sorted, non-duplicate integers in [0, max[ */
 int *generate(int n, int max) {
    int i, m, a;    
    int *g = (int *)calloc(n, sizeof(int));
    if ( ! g) return 0;

    m = 0;
    for (i=0; i<max; i++) {
        a = random_in_between(0, max - i);
        if (a < n - m) {
            g[m] = i;
            m ++;
        }
    }
    return g;
 }

¿Alguien sabe dónde puedo encontrar más gemas como esta?

Answer 5

En The Art of Computer Programming, Volumen 2: Algoritmos Seminumerical, tercera edición , Knuth describe el siguiente algoritmo de muestreo de selección:

Algoritmo S (técnica de muestreo de selección). Para seleccionar n registros al azar de un conjunto de N, donde 0 <n ≤ N.

S1. [Inicializar.] Establecer t ← 0, m ← 0. (Durante este algoritmo, m representa el número de registros seleccionados hasta el momento, yt es la cantidad total de registros de entrada que hemos tratado).

S2. [Generate U.] Genera un número aleatorio U, distribuido uniformemente entre cero y uno.

S3. [Prueba]. Si (N - t) U ≥ n - m, vaya al paso S5.

S4. [Seleccionar.] Seleccione el siguiente registro para la muestra, e incremente m y t en 1. Si m <n, vaya al paso S2; de lo contrario, la muestra se completa y el algoritmo finaliza.

S5. [Omitir.] Omita el siguiente registro (no lo incluya en la muestra), aumente t por 1 y vuelva al paso S2.

Una implementación puede ser más fácil de seguir que la descripción. Aquí hay una implementación de Common Lisp que selecciona n miembros aleatorios de una lista:

(defun sample-list (n list &optional (length (length list)) result)
  (cond ((= length 0) result)
        ((< (* length (random 1.0)) n)
         (sample-list (1- n) (cdr list) (1- length)
                      (cons (car list) result)))
        (t (sample-list n (cdr list) (1- length) result))))

Y aquí hay una implementación que no usa recursión, y que funciona con todo tipo de secuencias:

(defun sample (n sequence)
  (let ((length (length sequence))
        (result (subseq sequence 0 n)))
    (loop
       with m = 0
       for i from 0 and u = (random 1.0)
       do (when (< (* (- length i) u) 
                   (- n m))
            (setf (elt result m) (elt sequence i))
            (incf m))
       until (= m n))
    result))

Answer 6

Esta es una forma de hacerlo en O (N) sin almacenamiento adicional. Estoy bastante seguro de que esta no es una distribución puramente aleatoria, pero probablemente sea lo suficientemente cerca para muchos usos.

/* generate N sorted, non-duplicate integers in [0, max[  in O(N))*/
 int *generate(int n, int max) {
    float step,a,v=0;
    int i;    
    int *g = (int *)calloc(n, sizeof(int));
    if ( ! g) return 0;

    for (i=0; i<n; i++) {
        step = (max-v)/(float)(n-i);
        v+ = floating_pt_random_in_between(0.0, step*2.0);
        if ((int)v == g[i-1]){
          v=(int)v+1;             //avoid collisions
        }
        g[i]=v;
    }
    while (g[i]>max) {
      g[i]=max;                   //fix up overflow
      max=g[i--]-1;
    }
    return g;
 }

Answer 7

Este código de Ruby muestra el método de muestreo de reservorios, algoritmo R. En cada ciclo, selecciono n=5 enteros aleatorios únicos del rango [0,N=10) :

t=0
m=0
N=10
n=5
s=0
distrib=Array.new(N,0)
for i in 1..500000 do
 t=0
 m=0
 s=0
 while m<n do

  u=rand()
  if (N-t)*u>=n-m then
   t=t+1
  else 
   distrib[s]+=1
   m=m+1
   t=t+1
  end #if
  s=s+1
 end #while
 if (i % 100000)==0 then puts i.to_s + ". cycle..." end
end #for
puts "--------------"
puts distrib

salida:

100000. cycle...
200000. cycle...
300000. cycle...
400000. cycle...
500000. cycle...
--------------
250272
249924
249628
249894
250193
250202
249647
249606
250600
250034

todos los números enteros entre 0-9 fueron elegidos con casi la misma probabilidad.

Es esencialmente el algoritmo de Knuth aplicado a secuencias arbitrarias (de hecho, esa respuesta tiene una versión LISP de esto). El algoritmo es O (N) en el tiempo y puede ser O (1) en la memoria si la secuencia se transmite como se muestra en la respuesta de @ MichaelCramer .

Answer 8

Este es el código Perl. Grep es un filtro, y como siempre, no probé este código.

@list = grep ($_ % I) == 0, (0..N);

• I = intervalo
• N = límite superior

Solo obtenga números que coincidan con su intervalo a través del operador de módulo.

@list = grep ($_ % 3) == 0, (0..30);

devolverá 0, 3, 6, ... 30

Este es el código pseudo Perl. Es posible que deba modificarlo para que compile.

Answer 9

Genera una matriz 0...N-1 llenada a[i] = i .

Luego baraja los primeros K elementos.

Arrastramiento:

• Comience J = N-1
• Elige un número aleatorio 0...J (di, R )
• intercambia a[R] con a[J]
  • como R puede ser igual a J , el elemento puede intercambiarse consigo mismo
• reste 1 de J y repita.

Finalmente, tome K últimos elementos.

Esto esencialmente selecciona un elemento aleatorio de la lista, lo mueve, luego elige un elemento aleatorio de la lista restante, y así sucesivamente.

Funciona en O (K) y O (N) tiempo, requiere O (N) almacenamiento.

La parte de mezcla se llama mezcla de Fisher-Yates o mezcla de Knuth , descrita en el 2 ° volumen de El arte de la programación de computadoras.

Answer 10

La versión de Reservoir Sampling es bastante simple:

my $N = 20;
my $k;
my @r;

while(<>) {
  if(++$k <= $N) {
    push @r, $_;
  } elsif(rand(1) <= ($N/$k)) {
    $r[rand(@r)] = $_;
  }
}

print @r;

Eso es $ N filas seleccionadas al azar de STDIN. Reemplace las cosas <> / $ _ con algo más si no está utilizando filas de un archivo, pero es un algoritmo bastante sencillo.

Answer 11

Mi solución está orientada a C ++, pero estoy seguro de que podría traducirse a otros idiomas, ya que es bastante simple.

• Primero, genera una lista vinculada con elementos K, yendo de 0 a K
• Entonces, siempre y cuando la lista no esté vacía, genere un número aleatorio entre 0 y el tamaño del vector
• Tome ese elemento, empújelo en otro vector y elimínelo de la lista original

Esta solución solo involucra dos iteraciones de bucle, y ninguna búsqueda de tabla hash ni nada por el estilo. Entonces en el código real:

// Assume K is the highest number in the list
std::vector<int> sorted_list;
std::vector<int> random_list;

for(int i = 0; i < K; ++i) {
    sorted_list.push_back(i);
}

// Loop to K - 1 elements, as this will cause problems when trying to erase
// the first element
while(!sorted_list.size() > 1) {
    int rand_index = rand() % sorted_list.size();
    random_list.push_back(sorted_list.at(rand_index));
    sorted_list.erase(sorted_list.begin() + rand_index);
}                 

// Finally push back the last remaining element to the random list
// The if() statement here is just a sanity check, in case K == 0
if(!sorted_list.empty()) {
    random_list.push_back(sorted_list.at(0));
}

Answer 12

Paso 1: genera tu lista de enteros.
Paso 2: realiza Knuth Shuffle .

Tenga en cuenta que no necesita barajar toda la lista, ya que el algoritmo Knuth Shuffle le permite aplicar solo n combinaciones, donde n es la cantidad de elementos que debe devolver. Generar la lista todavía llevará tiempo proporcional al tamaño de la lista, pero puede reutilizar su lista existente para futuras necesidades de mezcla (suponiendo que el tamaño permanezca igual) sin necesidad de modificar la lista parcialmente mezclada antes de reiniciar el algoritmo de mezcla.

El algoritmo básico para Knuth Shuffle es que comienzas con una lista de enteros. Luego, intercambia el primer entero con cualquier número en la lista y devuelve el primer entero actual (nuevo). Luego, intercambia el segundo entero con cualquier número en la lista (excepto el primero) y devuelve el segundo entero actual (nuevo). Entonces ... etc ...

Este es un algoritmo absurdamente simple, pero tenga cuidado de incluir el elemento actual en la lista al realizar el intercambio o romperá el algoritmo.

Answer 13

Si la lista está ordenada, por ejemplo, si desea extraer elementos K de N, pero no le importa su orden relativo, se propone un algoritmo eficiente en el documento Un algoritmo eficiente para el muestreo aleatorio secuencial (Jeffrey Scott Vitter, ACM Transactions on Mathematical Software , Vol. 13, No. 1, marzo de 1987, páginas 56-67).

editado para agregar el código en c ++ usando boost. Acabo de tipearlo y puede haber muchos errores. Los números aleatorios provienen de la biblioteca de impulso, con una semilla estúpida, así que no hagas nada serio con esto.

/* Sampling according to [Vitter87].
 * 
 * Bibliography
 * [Vitter 87]
 *   Jeffrey Scott Vitter, 
 *   An Efficient Algorithm for Sequential Random Sampling
 *   ACM Transactions on MAthematical Software, 13 (1), 58 (1987).
 */

#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <string>
#include <iostream>

#include <iomanip>

#include <boost/random/linear_congruential.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/uniform_real.hpp>

using namespace std;

// This is a typedef for a random number generator.
// Try boost::mt19937 or boost::ecuyer1988 instead of boost::minstd_rand
typedef boost::minstd_rand base_generator_type;

    // Define a random number generator and initialize it with a reproducible
    // seed.
    // (The seed is unsigned, otherwise the wrong overload may be selected
    // when using mt19937 as the base_generator_type.)
    base_generator_type generator(0xBB84u);
    //TODO : change the seed above !
    // Defines the suitable uniform ditribution.
    boost::uniform_real<> uni_dist(0,1);
    boost::variate_generator<base_generator_type&, boost::uniform_real<> > uni(generator, uni_dist);



void SequentialSamplesMethodA(int K, int N) 
// Outputs K sorted random integers out of 0..N, taken according to 
// [Vitter87], method A.
    {
    int top=N-K, S, curr=0, currsample=-1;
    double Nreal=N, quot=1., V;

    while (K>=2)
        {
        V=uni();
        S=0;
        quot=top/Nreal;
        while (quot > V)
            {
            S++; top--; Nreal--;
            quot *= top/Nreal;
            }
        currsample+=1+S;
        cout << curr << " : " << currsample << "/n";
        Nreal--; K--;curr++;
        }
    // special case K=1 to avoid overflow
    S=floor(round(Nreal)*uni());
    currsample+=1+S;
    cout << curr << " : " << currsample << "/n";
    }

void SequentialSamplesMethodD(int K, int N)
// Outputs K sorted random integers out of 0..N, taken according to 
// [Vitter87], method D. 
    {
    const int negalphainv=-13; //between -20 and -7 according to [Vitter87]
    //optimized for an implementation in 1987 !!!
    int curr=0, currsample=0;
    int threshold=-negalphainv*K;
    double Kreal=K, Kinv=1./Kreal, Nreal=N;
    double Vprime=exp(log(uni())*Kinv);
    int qu1=N+1-K; double qu1real=qu1;
    double Kmin1inv, X, U, negSreal, y1, y2, top, bottom;
    int S, limit;
    while ((K>1)&&(threshold<N))
        {
        Kmin1inv=1./(Kreal-1.);
        while(1)
            {//Step D2: generate X and U
            while(1)
                {
                X=Nreal*(1-Vprime);
                S=floor(X);
                if (S<qu1) {break;}
                Vprime=exp(log(uni())*Kinv);
                }
            U=uni();
            negSreal=-S;
            //step D3: Accept ?
            y1=exp(log(U*Nreal/qu1real)*Kmin1inv);
            Vprime=y1*(1. - X/Nreal)*(qu1real/(negSreal+qu1real));
            if (Vprime <=1.) {break;} //Accept ! Test [Vitter87](2.8) is true
            //step D4 Accept ?
            y2=0; top=Nreal-1.;
            if (K-1 > S)
                {bottom=Nreal-Kreal; limit=N-S;}
            else {bottom=Nreal+negSreal-1.; limit=qu1;}
            for(int t=N-1;t>=limit;t--)
                {y2*=top/bottom;top--; bottom--;}
            if (Nreal/(Nreal-X)>=y1*exp(log(y2)*Kmin1inv))
                {//Accept !
                Vprime=exp(log(uni())*Kmin1inv);
                break;
                }
            Vprime=exp(log(uni())*Kmin1inv);
            }
        // Step D5: Select the (S+1)th record
        currsample+=1+S;
        cout << curr << " : " << currsample << "/n";
        curr++;
        N-=S+1; Nreal+=negSreal-1.;
        K-=1; Kreal-=1; Kinv=Kmin1inv;
        qu1-=S; qu1real+=negSreal;
        threshold+=negalphainv;
        }
    if (K>1) {SequentialSamplesMethodA(K, N);}
    else {
        S=floor(N*Vprime);
        currsample+=1+S;
        cout << curr << " : " << currsample << "/n";
        }
    }


int main(void)
    {
    int Ntest=10000000, Ktest=Ntest/100;
    SequentialSamplesMethodD(Ktest,Ntest);
    return 0;
    }

$ time ./sampling|tail

da el siguiente ouptut en mi computadora portátil

99990 : 9998882
99991 : 9998885
99992 : 9999021
99993 : 9999058
99994 : 9999339
99995 : 9999359
99996 : 9999411
99997 : 9999427
99998 : 9999584
99999 : 9999745

real    0m0.075s
user    0m0.060s
sys 0m0.000s