Génération de m nombres aléatoires distincts dans la plage [0..n-1].

Question

J'ai deux méthodes pour générer m nombres aléatoires distincts dans l'intervalle [0..n-1].

Méthode 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éthode 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;

La première méthode est plus efficace lorsque n est beaucoup plus grand que m, tandis que la seconde est plus efficace dans le cas contraire. Mais "beaucoup plus grand" n'est pas une notion si stricte, n'est-ce pas ? :)

Pregunta: Quelle formule de n et m dois-je utiliser pour déterminer si la méthode1 ou la méthode2 sera plus efficace ? (en termes d'espérance mathématique du temps d'exécution)

Answer 1

En ce qui concerne l'espérance mathématique, c'est plutôt inutile mais je vais quand même le poster :D

Le brassage est simple O(m).

L'autre algorithme est un peu plus complexe. Le nombre d'étapes nécessaires pour générer le nombre suivant est la valeur attendue du nombre d'essais, et la probabilité de la longueur des essais est une distribution géométrique. Donc...

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

Notez que la somme peut être divisée en forme de triangle, voir la partie droite.

Utilisons la formule de la série harmonique : H_n = Somme k=0->n (1/k) = approx 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) ..

Et il y a un certain forumla pour la somme des séries harmoniques, si vous êtes todavía intéressé, je vais chercher...

Mise à jour : en fait, c'est une formule assez agréable (grâce au brillant livre Concrete Mathematics).

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

Donc le nombre d'étapes prévu :

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).

Note : Je ne l'ai pas vérifié.

Answer 2

Et si on utilisait set au lieu de array, je pense que c'est beaucoup plus facile que array

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

Answer 3

C'est un peu tiré par les cheveux, mais cela pourrait fonctionner, selon votre système.

1. Commencez par un ratio raisonnable, comme 0,5.
2. Lorsqu'une demande arrive, elle est traitée avec la méthode que vous obtenez à partir de la valeur actuelle du ratio de seuil.
3. Notez le temps que cela prend et lorsque vous avez du temps "vide", effectuez la même tâche avec l'autre méthode.
4. Si la solution alternative est beaucoup plus rapide que la solution originale, ajustez le seuil vers le haut ou vers le bas.

Le défaut évident de cette méthode est que sur des systèmes à charge très variable, votre test "hors ligne" ne sera pas très fiable.

Answer 4

Il a été suggéré de procéder à un remaniement Fisher-Yates. Je ne sais pas si le code suivant génère des entiers distribués de manière égale, mais il est au moins compact et ne nécessite qu'un seul passage :

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

Answer 5

Il serait peut-être plus simple de le lancer en mode débogage (et de garder une méthode en note) quelques fois pour obtenir une moyenne, puis d'utiliser l'autre méthode pour en obtenir une moyenne.