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

Les mathématiques pures :
Calculons la quantité de rand() dans les deux cas et comparez les résultats :

Cas 1 : voyons l'espérance mathématique des appels sur l'étape i = k alors que vous avez déjà choisi les numéros k. La probabilité d'obtenir un numéro avec un rand() est égal à p = (n-k)/n . Nous devons connaître l'espérance mathématique de cette quantité d'appels, ce qui conduit à obtenir un nombre que nous n'avons pas encore.

La probabilité de l'obtenir en utilisant 1 L'appel est p . Utilisation de 2 appels - q * p , donde q = 1 - p . Dans le cas général, la probabilité de l'obtenir exactement après n Les appels sont (q^(n-1))*p . Ainsi, l'espérance mathématique est
Sum[ n * q^(n-1) * p ], n = 1 --> INF . Cette somme est égale à 1/p (prouvé par wolfram alpha).

Donc, sur la marche i = k vous effectuerez 1/p = n/(n-k) appels de la rand() fonction.

Maintenant, résumons l'ensemble :

Sum[ n/(n - k) ], k = 0 --> m - 1 = n * T - le nombre de rand appels dans la méthode 1.
Ici T = Sum[ 1/(n - k) ], k = 0 --> m - 1

Cas 2 :

Ici rand() est appelé à l'intérieur random_shuffle n - 1 fois (dans la plupart des implémentations).

Maintenant, pour choisir la méthode, nous devons comparer ces deux valeurs : n * T ? n - 1 .
Pour choisir la méthode appropriée, il faut donc calculer T comme décrit ci-dessus. Si T < (n - 1)/n il est préférable d'utiliser la première méthode. Sinon, utilisez la deuxième méthode.

Answer 2

Consultez la description Wikipedia du algorithme original de Fisher-Yates . Il préconise d'utiliser essentiellement votre méthode 1 jusqu'à n/2, et votre méthode 2 pour le reste.

Answer 3

Personnellement, j'utiliserais la méthode 1, et si M > N/2, je choisirais N-M valeurs, puis j'inverserais le tableau (en retournant les nombres qui n'ont pas été choisis). Ainsi, par exemple, si N est égal à 1000 et que vous en voulez 950, choisissez 50 valeurs en utilisant la méthode 1, puis retournez les 950 autres.

Edit : Cependant, si la performance constante est votre objectif, j'utiliserais une méthode 2 modifiée, qui ne fait pas le shuffle complet, mais mélange seulement les M premiers éléments de votre tableau de N longueurs.

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;

Answer 4

Voici un algorithme qui fonctionnera en O(n) mémoire et O(n) temps (où n est le nombre de résultats retournés, et non la taille de l'ensemble dans lequel vous faites votre sélection) pour n'importe quel ensemble de résultats. Il est en Python par commodité car il utilise une table de hachage :

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.

Il s'agit simplement d'un brassage partiel de type fisher-yates, le tableau brassé étant implémenté comme une table de hachage clairsemée - tout élément qui n'est pas présent est égal à son index. Nous mélangeons le premier num_elements et de renvoyer ces valeurs. Dans le cas où set_size = 1, cela équivaut à choisir un nombre aléatoire dans l'intervalle, et dans le cas où num_elements = set_size ce qui équivaut à un mélange standard de type fisher-yates.

Il est trivial d'observer que c'est O(n) temps, et parce que chaque itération de la boucle initialise au plus deux nouveaux indices dans la table de hachage, c'est O(n) espace, aussi.

Answer 5

Qu'en est-il d'une troisième méthode ?

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 il devrait être <=. et il y aurait en fait une logique supplémentaire pour éviter les collisions.

C'est mieux, un exemple utilisant le Méthode moderne 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;