Random.Next () - trouver le Nième .Next ()

Question

Étant donné un aléatoire prédéfini de manière cohérente:

Random r = new Random(0);

L'appel de r.Next() produit systématiquement la même série;alors y a-t-il un moyen de découvrir rapidement la N -ième valeur de cette série, sans appeler r.Next() N fois?

Mon scénario est un énorme tableau de valeurs créées via r.Next().L'application lit occasionnellement une valeur du tableau à des index arbitraires.Je voudrais optimiser l'utilisation de la mémoire en éliminant le tableau et en générant les valeurs à la demande.Mais forcer le r.Next() 5 millions de fois pour simuler le 5 millionième index du tableau coûte plus cher que de stocker le tableau.Est-il possible de raccourcir votre chemin vers la valeur Nth .Next (), sans / avec moins de boucles?

Answer 1

En théorie, si vous connaissiez l'algorithme exact et l'état initial, vous seriez capable de dupliquer la série, mais le résultat final serait juste identique à l'appel de r.next ().

En fonction de la qualité de vos nombres aléatoires, vous pouvez envisager de créer votre propre PRNG basé sur un Générateur congruentiel linéaire pour lequel il est relativement facile / rapide de générer des nombres.Si vous pouvez vivre avec un "mauvais" PRNG, il y a probablement d'autres algorithmes qui pourraient être mieux utilisés pour vos besoins.La question de savoir si ce serait plus rapide / meilleur que de simplement stocker un large éventail de nombres à partir de r.next () est une autre question.

Answer 2

I don't know the details of the PRNG used in the BCL, but my guess is that you will find it extremely difficult / impossible to find a nice, closed-form solution for N-th value of the series.

How about this workaround:

Make the seed to the random-number generator the desired index, and then pick the first generated number. This is equally 'deterministic', and gives you a wide range to play with in O(1) space.

static int GetRandomNumber(int index)
{
    return new Random(index).Next();
} 

Answer 3

No, I don't believe there is. For some RNG algorithms (such as linear congruential generators) it's possible in principle to get the n'th value without iterating through n steps, but the Random class doesn't provide a way of doing that.

I'm not sure whether the algorithm it uses makes it possible in principle -- it's a variant (details not disclosed in documentation) of Knuth's subtractive RNG, and it seems like the original Knuth RNG should be equivalent to some sort of polynomial-arithmetic thing that would allow access to the n'th value, but (1) I haven't actually checked that and (2) whatever tweaks Microsoft have made might break that.

If you have a good enough "scrambling" function f then you can use f(0), f(1), f(2), ... as your sequence of random numbers, instead of f(0), f(f(0)), f(f(f(0))), etc. (the latter being roughly what most RNGs do) and then of course it's trivial to start the sequence at any point you please. But you'll need to choose a good f, and it'll probably be slower than a standard RNG.

Answer 4

You could build your own on-demand dictionary of 'indexes' & 'random values'. This assumes that you will always 'demand' indexes in the same order each time the program runs or that you don't care if the results are the same each time the program runs.

Random rnd = new Random(0);
Dictionary<int,int> randomNumbers = new Dictionary<int,int>();
int getRandomNumber(int index)
{
    if (!randomNumbers.ContainsKey(index))
        randomNumbers[index] = rnd.Next();
    return randomNumbers[index];
}