Generando m números aleatorios distintos en el rango

Tengo dos métodos para generar m números aleatorios distintos en el rango [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 eficiente cuando n es mucho mayor que m, mientras que el segundo es más eficiente de lo contrario. Pero “mucho más grande” no es una noción estricta, ¿verdad? 🙂

Pregunta: ¿Qué fórmula de nym debería usar para determinar si method1 o method2 serán más eficientes? (en términos de expectativa matemática del tiempo de ejecución)

Matemáticas puras
Calculemos la cantidad de llamadas a la función rand() en ambos casos y compare los resultados:

Caso 1: veamos la expectativa matemática de las llamadas en el paso i = k , cuando ya tienes k números elegidos. La probabilidad de obtener un número con una llamada rand() es igual a p = (nk)/n . Necesitamos saber la expectativa matemática de tal cantidad de llamadas que conduce a obtener un número que todavía no tenemos.

La probabilidad de obtenerlo usando 1 llamada es p . Usando 2 llamadas – q * p , donde q = 1 - p . En general, la probabilidad de obtenerlo exactamente después de n llamadas es (q^(n-1))*p . Por lo tanto, la expectativa matemática es
Sum[ n * q^(n-1) * p ], n = 1 --> INF . Esta sum es igual a 1/p (demostrado por wolfram alpha).

Por lo tanto, en el paso i = k realizará llamadas 1/p = n/(nk) de la función rand() .

Ahora, resumámoslo en general:

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

Caso 2

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

Ahora, para elegir el método, tenemos que comparar estos dos valores: n * T ? n - 1 n * T ? n - 1 .
Entonces, para elegir el método apropiado, calcule T como se describe arriba. Si T < (n - 1)/n es mejor usar el primer método. Use el segundo método de lo contrario.

Compruebe la descripción de Wikipedia del algoritmo original de Fisher-Yates . Aboga por utilizar esencialmente su método 1 hasta por n / 2, y su método 2 por el rest.

Personalmente, usaría el Método 1, y luego, si M> N / 2, elegiría valores NM, y luego invertiría la matriz (devolvería los números que no fueron recogidos). Entonces, por ejemplo, si N es 1000 y quiere 950 de ellos, elija 50 valores usando el Método 1, y luego devuelva los otros 950.

Editar: Sin embargo, si tu objective es el rendimiento consistente, usaría un método modificado 2, que no hace la mezcla completa, sino que solo mezcla los primeros M elementos de tu matriz de longitud N.

 int arr[n]; for(int i = 0; i < n; ++i) arr[i] = i; for (int i =0; i < m; ++i) { int j = rand(ni); // Pick random number from 0 <= r < ni. 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; 

Aquí hay un algoritmo que funcionará en O (n) memoria y O (n) tiempo (donde n es el número de resultados devueltos, no el tamaño del conjunto desde el que se selecciona) para cualquier conjunto de resultados. Está en Python por conveniencia porque usa 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 solo una mezcla parcial de fisher-yates, con la matriz que se baraja implementada como hashtable dispersa: cualquier elemento que no está presente es igual a su índice. num_elements los primeros índices num_elements y devolvemos esos 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 barajado de fisher-yates estándar.

Es trivial observar que este es el tiempo O (n), y dado que cada iteración del ciclo inicializa como máximo dos nuevos índices en la tabla hash, también es O (n) espacio.

¿Qué tal un tercer método?

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

Editar debe ser < =. y en realidad sería una lógica adicional para evitar colisiones.

Esto es mejor, un ejemplo usando el 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, ni, rand()%(ni) ); result = last m elements in arr; 

Hablando de expectativas matemáticas, es bastante inútil, pero lo publicaré de todos modos: D

Shuffle es simple O (m).

Ahora el otro algoritmo es un poco más complejo. El número de pasos necesarios para generar el próximo número es el valor esperado del número de ensayos, y la probabilidad de la duración del ensayo es una distribución geométrica. Asi 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 sum se puede dividir en forma de triángulo, ver el lado derecho.

Usemos la fórmula para la serie de armónicos: H_n = Suma k = 0-> n (1 / k) = aproximadamente ln (k)

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

Y hay algunos forumla para la sum de series armónicas, si todavía estás interesado lo buscaré …

Actualización : en realidad es una fórmula bastante agradable (gracias al shiny libro Concrete Mathematics)

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

Entonces, el número esperado de pasos:

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

Nota: no lo he verificado

Esta es una posibilidad remota, pero podría funcionar, dependiendo de su sistema.

  1. Comience con una proporción razonable, como 0.5.
  2. Cuando llega una solicitud, trátela con el método que obtenga del valor actual de la relación de umbral.
  3. Registre el tiempo que toma y cuando tiene tiempo “vacío”, realice la misma tarea con el otro método.
  4. Si la solución alternativa es mucho más rápida que la original, ajuste el umbral hacia arriba o hacia abajo.

La falla obvia en este método es que en sistemas de carga muy variables su prueba “fuera de línea” no será demasiado confiable.

Se sugirió la mezcla de Fisher-Yates. No sé si el próximo código genera enteros igualmente distribuidos, pero es al menos compacto y de una sola pasada:

 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); } 

Es muy posible que sea más simple iniciarlo en modo de depuración (y mantener un método como una nota) por un par de veces para obtener un promedio, luego use el otro método para obtener un promedio de ese

No aconsejo este método, pero funciona

 #include  #include  #include  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; }