Tengo dos métodos de generación de m distintos números aleatorios en el intervalo [0..n-1]

Método 1:

//C++-ish pseudocode
int result[m];
for(i = 0; i < m; ++i)
{
   int r;
   do
   {
      r = rand()%n;
   }while(r is found in result array at indices from 0 to i)
   result[i] = r;   
}

Método 2:

//C++-ish pseudocode
int arr[n];
for(int i = 0; i < n; ++i)
    arr[i] = i;
random_shuffle(arr, arr+n);
result = first m elements in arr;

El primer método es más eficaz cuando n es mayor que m, mientras que la segunda es más eficiente de lo contrario. Pero «mucho más grande» no es que la estricta noción, que es? 🙂

Pregunta: Lo que la fórmula de n y m se debe usar para determinar si method1 o method2 será más eficiente? (en términos de esperanza matemática del tiempo de funcionamiento)

  • Si m es realmente pequeña, hace eficiencia importa mucho? Optimizar para el caso de que es más probable que causen problemas.
  • Voy a obtener dinámicamente n y m. Voy a tener que determinar en tiempo de ejecución el método que va a utilizar
  • Has probado los dos métodos con un par de diferentes parámetros? Sólo para tener una vaga sensación de ¿cuánto tiempo toman.

11 Comentarios

  1. 15

    La matemática pura:

    Vamos a calcular la cantidad de rand() función de llamadas en ambos casos y comparar los resultados:

    Caso 1:
    vamos a ver la esperanza matemática de llamadas en el paso i = k, cuando ya se tiene k números elegidos. La probabilidad de obtener un número con una rand() de la llamada es igual a p = (n-k)/n. Necesitamos saber la expectativa matemática de este tipo de llamadas de la cantidad que lleva a la obtención de un número que aún no tenemos.

    La probabilidad de obtener mediante 1 llamada p. El uso de 2 llamadas – q * p, donde q = 1 - p. En el caso general, la probabilidad de obtener exactamente después de n llamadas es (q^(n-1))*p. Por lo tanto, la esperanza matemática es

    Sum[ n * q^(n-1) * p ], n = 1 --> INF. Esta suma es igual a 1/p (demostrado por wolfram alpha).

    Así, en el paso i = k realizará 1/p = n/(n-k) llamadas de la rand() función.

    Ahora vamos a la suma total de:

    Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T – el número de rand llamadas en el método 1.

    Aquí T = Sum[ 1/(n - k) ], k = 0 --> m - 1

    Caso 2:

    Aquí rand() se llama dentro de random_shuffle n - 1 veces (en la mayoría de las implementaciones).

    Ahora, para elegir el método, hemos de comparar estos dos valores: n * T ? n - 1.

    Así, para elegir el método adecuado, calcular T como se describió anteriormente. Si T < (n - 1)/n es mejor usar el primer método. Utilizar el segundo método lo contrario.

    • Sería grande si usted podría, por favor ampliar – «Con 2 llamadas – p * p, donde q = 1 – p». Yo realmente no lo entiendo.
    • También me gustaría considerar la búsqueda de esfuerzo(que es 0 para el caso 2) en cada iteración del bucle while, no sólo los tiempos de llamadas al azar
  2. 9

    Comprobar la Wikipedia descripción de la original de Fisher-Yates algoritmo. Se aboga por el uso esencialmente su método 1 hasta n/2, y su método 2 para el resto.

    • Creo que es un afinando problema. Él sólo tendrá que medir en el sistema de destino.
    • Esto suena bastante bien, sin duda de una memoria perspectiva de eficiencia. Utilizando el método 2 puede consumir una enorme cantidad de memoria innecesariamente con menor m valores.
    • En visualstudiomagazine.com/articles/2013/07/01/… usted puede encontrar una buena explicación de implementación en c# de el método de Fisher. El post también muestra también un Enfoque alternativo con El Embalse de Método y las diferencias entre ellos.
  3. 6

    Personalmente, me gustaría utilizar el Método 1 y, a continuación, si M > N/2, elegir N-M valores, y luego invertir la matriz (el retorno de los números que no se han seleccionado). Así, por ejemplo, si N es 1000 y desea 950 de ellos, eligieron 50 valores que utilizar el Método 1 y, a continuación, volver a los otros 950.

    Edit: Aunque, si se ajusta el rendimiento es su objetivo, me gustaría utilizar un método modificado de 2, que no la completa shuffle, pero sólo se baraja la primera M elementos de su N la longitud de la matriz.

    int arr[n];
    for(int i = 0; i < n; ++i)
        arr[i] = i;
    
    for (int i =0; i < m; ++i) {
       int j = rand(n-i); //Pick random number from 0 <= r < n-i.  Pick favorite method
       //j == 0 means don't swap, otherwise swap with the element j away
       if (j != 0) { 
          std::swap(arr[i], arr[i+j]);
       }
    }
    result = first m elements in arr;
  4. 6

    Aquí un algoritmo que va a trabajar en O(n) en la memoria y O(n) tiempo (donde n es el número de resultados devueltos, no el tamaño del conjunto está seleccionando) para cualquier conjunto de resultados. Es en Python por conveniencia debido a que utiliza una tabla hash:

    def random_elements(num_elements, set_size):
        state = {}
        for i in range(num_elements):
            # Swap state[i] with a random element
            swap_with = random.randint(i, set_size - 1)
            state[i], state[swap_with] = state.get(swap_with, swap_with), state.get(i, i)
        return [state[i] for i in range(num_elements) # effectively state[:num_elements] if it were a list/array.

    Esto es sólo un parcial de fisher-yates shuffle, con la matriz que se barajan implementado como una escasa hashtable – cualquier elemento que no está presente es igual a la de su índice. Se baraja la primera num_elements índices, y devolver valores. En el caso de que set_size = 1, esto es equivalente a elegir un número aleatorio en el rango, y en el caso de que num_elements = set_size, esto es equivalente a un estándar de fisher-yates shuffle.

    Es trivial observar que este es O(n) tiempo, y porque en cada iteración del bucle se inicializa en la mayoría de los dos nuevos índices en la tabla hash, es O(n) en el espacio, también.

    • Hashtable/diccionario de acceso no es tiempo constante O(1), sino logarítmica tiempo O(log(n)) por lo que el total de complejidad O(n log(n)).
    • Es constante amortizado en realidad
    • Creo que debe ser swap_with = random.randint(i, set_size-1) desde randint() utiliza un intervalo inclusivo? @nick-johnson
    • Wow, tienes razón. Bonito biblioteca de Python gotcha ahí que yo nunca había notado antes. Fijo.
  5. 3

    Lo que alrededor de un tercio método?

    int result[m];
    for(i = 0; i < m; ++i)
    {
       int r;
       r = rand()%(n-i);
       r += (number of items in result <= r)
       result[i] = r;   
    }

    Editar debe ser <=. y es realmente una lógica adicional para evitar colisiones.

    Esto es mejor, un ejemplo de uso de la Método Moderno de Fisher-Yates

    //C++-ish pseudocode
    int arr[n];
    for(int i = 0; i < n; ++i)
        arr[i] = i;
    
    for(i = 0; i < m; ++i)
        swap(arr, n-i, rand()%(n-i) );
    
    result = last m elements in arr;
    • ¿Qué entiende usted por (number of items in result < r)? Quiere esto decir que 1 se añadirá, si r es mayor que el número de elementos en el resultado?
    • +1 una Vez más, nos faltaba la obvia. Me gustaría consumir una gran cantidad de espacio, porque aunque usted tendría que mantener sus resultados en una lista ordenada demasiado para realizar la (number of items in result < r) controlar eficientemente.
    • Me refiero +1 para cada elemento en el resultado <= r. Esto es para compensar el hecho de que estamos recibiendo rand() to n-i
    • Pero esto no es exactamente uniformemente al azar, ¿no?
    • Quiero decir, incluso si suponemos que la función rand() devuelve un distribuida uniformemente en número, su algoritmo no generará distribuye uniformemente en secuencias
    • ¿Por qué no? ¿No es esencialmente diciendo elige un entero aleatorio en [0,n-1], a continuación, elegir al azar uno de los n-1 restantes…finalmente elegir uno de los n-m+1 restantes. Es el inicio de la Fisher-Yates aleatorio, pero deteniéndose en n-m en lugar de 2.

  6. 2

    Hablando de la esperanza matemática, es bastante inútil, pero voy a publicar de todos modos 😀

    Shuffle es simple O(m).

    Ahora el otro algoritmo es un poco más complejo. El número de pasos necesarios para generar el siguiente número es el valor esperado del número de ensayos, y la probabilidad de que la longitud de proceso es un geomtric de distribución. Así que…

    p=1          E[X1]=1            = 1           = 1
    p=1-1/n      E[x2]=1/(1-1/n)    = 1 + 1/(n-1) = 1 + 1/(n-1) 
    p=1-2/n      E[x3]=1/(1-1/n)    = 1 + 2/(n-2) = 1 + 1/(n-2) + 1/(n-2)
    p=1-3/n      E[X4]=1/(1-2/n)    = 1 + 3/(n-3) = 1 + 1/(n-3) + 1/(n-3) + 1(n-3)
    ....
    p=1-(m-1)/n) E[Xm]=1/(1-(m-1)/n))

    Tenga en cuenta que la suma se puede dividir en una forma de triángulo, véase el lado derecho.

    Vamos a usar la fórmula de la serie armónica: H_n = Suma k=0->n (1/k) = aprox ln(k)

    Sum(E[Xk]) = m + ln(n-1)-ln(n-m-1) + ln(n-2)-ln(n-m-1) + ... = m + ln(n-1) + ln(n-2) + ... - (m-1)*ln(n-m-1) ..

    Y hay algunos forumla por la suma de la serie armónica, si todavía interesado voy a buscarlo…

    Actualización: en realidad es bastante agradable fórmula (gracias a la brillante Concreto Matemáticas libro)

    Sum(H_k) k=0->n = n*H_n - n

    Por lo que el número esperado de pasos:

    Sum(E[Xk]) = m + (n-1)*ln(n-1) - (n-1) - (n-m-1)*ln(n-m-1) - (n-m-1)) - (m-1)*ln(n-m-1).

    Nota: no he verificado.

  7. 1

    Esto es un poco de un tiro largo, pero podría funcionar, dependiendo de tu sistema.

    1. Comenzar con algunos proporción razonable, como 0.5.
    2. Cuando llega una solicitud, proceso con cualquiera que sea el método de obtener el valor actual de el umbral de la relación.
    3. Registrar el tiempo que tarda y cuando usted tiene «vacío» tiempo, realizar la misma tarea con el otro método.
    4. Si la alternativa de solución es mucho más rápido que el original, ajustar el umbral hacia arriba o hacia abajo.

    La evidente falla de este método es que en muy variable de carga de los sistemas de su «fuera de línea» de la prueba no será demasiado fiable.

  8. 0

    Había sugerido Fisher-Yates shuffle. No sé si el siguiente código genera igualmente distribuido enteros, pero no es menos compacto y de un paso:

    std::random_device rd;
    std::mt19937 g(rd());
    for (size_type i = 1; i < std::size(v); ++i) {
        v[i] = std::exchange(v[g() % i], i);
    }
  9. 0

    Lo que sobre el uso de conjunto en lugar de la matriz, creo que es mucho más fácil que la matriz de

    set<int> Numbers;
    while (Numbers.size() < m) {
       Numbers.insert(rand() % n);
    }
  10. -1

    Muy posiblemente sería más simple para iniciar en modo de depuración (y seguir un método como una nota) para un par de veces, para obtener un promedio, a continuación, utilizar el otro método para obtener un promedio de que

  11. -1

    Yo no te aconsejo este método, pero funciona

    #include <iostream>
    #include <random>
    #include <ctime>
    
    using namespace std;
    
    int randArray[26];
    int index = 0;
    
    bool unique(int rand) {
    
        for (int i = 0; i < index; i++)
            if (rand == randArray[i])
                return false;
        index++;
        return true;
    }
    
    
    int main()
    {
        srand(time(NULL));
    
        for (int i = 1; i < 26; i++)
            randArray[i] = -1;
    
        for (int i = 0; i < 26; i++) {
    
            randArray[i] = rand() % 26;
    
            while (!unique(randArray[i])) {
                randArray[i] = rand() % 26;
            }
        }
    
        for (int i = 0; i < 26; i++) {
            cout << randArray[i] << " ";
        }
    
        cout << "\n" << index << endl;
    
    
        return 0;
    }

Dejar respuesta

Please enter your comment!
Please enter your name here