La génération m distinctes nombres aléatoires dans l'intervalle [0..n-1]

Mathématiques pures:

Nous allons calculer la quantité de rand() appels de fonction dans les deux cas, et de comparer les résultats:

Cas 1:
nous allons voir l'espérance mathématique d'appels sur l'étape i = k, quand vous avez déjà k numéros choisis. La probabilité d'obtenir un nombre avec un rand() appel est égal à p = (n-k)/n. Nous avons besoin de savoir l'espérance mathématique de tels appels à la quantité qui conduit à l'obtention d'un numéro nous n'avons pas encore.

La probabilité d'obtenir de l'aide 1 appel est p. À l'aide de 2 appels - q * p, où q = 1 - p. Dans le cas général, la probabilité d'obtenir exactement après n appels est (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).

Ainsi, à l'étape i = k vous allez effectuer 1/p = n/(n-k) appels de la rand() fonction.

Maintenant, nous allons somme globale de:

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

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

Cas 2:

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

Maintenant, le choix de la méthode, il nous faut comparer ces deux valeurs: n * T ? n - 1.

Donc, pour choisir la méthode appropriée, calculer T comme décrit ci-dessus. Si T < (n - 1)/n il est préférable d'utiliser la première méthode. Utiliser la deuxième méthode contraire.

Personnellement, je voudrais utiliser la Méthode 1, et puis si M > N/2, choisissez N-M valeurs, puis inverser la matrice (retourner les numéros qui n'ont pas été pris). Ainsi, par exemple, si N est de 1000 et que vous voulez 950 d'entre eux, choisi 50 valeurs à l'aide de la Méthode 1, puis les retourner et les autres 950.

Edit: Si, si cohérente de la performance est votre but, je voudrais utiliser une version modifiée de la méthode 2, ce qui ne veut pas faire le plein de lecture aléatoire, mais seulement le mélange de la première M éléments de votre N longueur du tableau.

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;

Qu'environ un tiers de la 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;   
}

Modifier il convient de <=. et il serait effectivement logique supplémentaire pour éviter les collisions.

C'est mieux, un exemple d'utilisation de la 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;

C'est un peu un long shot, mais il pourrait fonctionner, en fonction de votre système.

1. Commencer avec quelques ratio raisonnable, comme 0,5.
2. Lorsqu'une demande arrive, le traiter avec un quelle que soit la méthode que vous obtenez à partir de la valeur actuelle du seuil de ratio.
3. Enregistrer le temps qu'il faut et quand vous avez le "vide" de temps, d'effectuer la même tâche avec l'autre méthode.
4. Si la solution est beaucoup plus rapide que l'original, ajuster le seuil haut ou vers le bas.

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

Que sur l'utilisation de ensemble au lieu de tableau, je pense qu'il est beaucoup plus facile que la matrice de

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

Je ne conseille pas cette méthode, mais elle fonctionne

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