Génération d'une séquence aléatoire et non répétitive de tous les entiers en .NET

Question

Existe-t-il un moyen en .NET de générer une séquence de todos les entiers de 32 bits ( Int32 ) dans un ordre aléatoire, sans répétitions, et d'une manière efficace du point de vue de la mémoire ? Une mémoire efficace signifie qu'il faut utiliser au maximum quelques centaines de méga-octets de mémoire principale.

Idéalement, la séquence devrait être quelque chose comme IEnumerable<int> et il renvoie paresseusement le numéro suivant dans la séquence, uniquement lorsque cela est demandé.

J'ai fait quelques recherches rapides et j'ai trouvé quelques solutions partielles à ce problème :

• Utilisation d'un registre à décalage à rétroaction linéaire maximale - si j'ai bien compris, il ne génère que les numéros en séquence croissante et ne couvre pas la totalité de la plage.
• Utilisation de la Fisher-Yates ou d'autres algorithmes de brassage sur les collections - cela violerait les restrictions de mémoire étant donné la grande gamme
• Maintenir une collection de type ensemble et continuer à générer un entier aléatoire (en utilisant peut-être Random ) jusqu'à ce qu'il ne se répète plus, c'est-à-dire qu'il ne fasse plus partie de l'ensemble - en plus de ne pas satisfaire aux exigences de mémoire, cela deviendrait ridiculement lent lors de la génération des derniers chiffres de la séquence.
• Permutations aléatoires sur 32 bits, mais je n'arrive pas à trouver un moyen de garantir la non-répétitivité.

Existe-t-il une autre façon d'aborder ce problème - peut-être en tirant parti de la plage fixe de valeurs - qui permettrait de satisfaire aux exigences en matière de mémoire ? Peut-être les bibliothèques de classes .NET contiennent-elles quelque chose d'utile ?

MISE À JOUR 1

Merci à tous pour vos idées et vos suggestions créatives pour trouver une solution. J'essaierai d'implémenter et de tester bientôt (à la fois pour l'exactitude et l'efficacité de la mémoire) les 2 ou 3 solutions les plus prometteuses proposées ici, de publier les résultats et de choisir un "gagnant".

MISE À JOUR 2

J'ai essayé de mettre en œuvre la suggestion de hvd dans la section commentaire ci-dessous . J'ai essayé d'utiliser à la fois le BitArray dans .NET et mon implémentation personnalisée, puisque celle de .NET est limitée à int.MaxValue entrées, donc pas assez pour couvrir toute la gamme des nombres entiers.

J'aimais la simplicité de l'idée et j'étais prêt à "sacrifier" ces 512 Mo de mémoire si cela fonctionnait bien. Malheureusement, le temps d'exécution est assez lent, passant jusqu'à des dizaines de secondes pour générer le prochain nombre aléatoire sur ma machine, qui a un CPU Core i7 de 3,5 GHz. Donc, malheureusement, ce n'est pas acceptable si vous demandez à ce que de très nombreux nombres aléatoires soient générés. Je suppose que c'est prévisible cependant, c'est un algorithme O(M x N) si je ne me trompe pas, où N est 2^32 et M est le nombre d'entiers demandés, donc toutes ces itérations prennent leur péage.

Idéalement, j'aimerais générer le prochain nombre aléatoire en O(1) temps, tout en respectant les exigences de mémoire, peut-être que les prochains algorithmes suggérés ici sont adaptés pour cela. Je les essaierai dès que je le pourrai.

MISE À JOUR 3

Je viens de tester le Générateur linéaire de congruence et je peux dire que je suis assez satisfait des résultats. Il s'agit d'un candidat solide pour la position de gagnant dans ce fil.

Correctness tous les entiers sont générés exactement une fois (j'ai utilisé un vecteur de bits pour vérifier cela).

Randomness : assez bon.

Utilisation de la mémoire : Excellent, juste quelques octets.

Temps de fonctionnement : Génère le prochain entier aléatoire très rapidement, comme vous pouvez l'attendre d'un algorithme O(1). La génération de chaque entier a pris un total d'environ 11 secondes sur ma machine.

Dans l'ensemble, je dirais que c'est une technique très appropriée si vous ne recherchez pas des séquences hautement aléatoires.

UPDATE 4

Le système modulaire technique inverse multiplicative décrite ci-dessous se comporte de manière assez similaire à la technique LCG - ce qui n'est pas surprenant, puisque les deux sont basées sur l'arithmétique modulaire -, bien que j'ai trouvé qu'elle était un peu moins simple à mettre en œuvre pour produire des séquences aléatoires satisfaisantes.

Une différence intéressante que j'ai trouvée est que cette technique semble plus rapide que LCG : générer la séquence entière a pris environ 8 secondes, contre 11 secondes pour LCG. A part cela, toutes les autres remarques concernant l'efficacité de la mémoire, la correction et le caractère aléatoire sont les mêmes.

MISE À JOUR 5

On dirait que l'utilisateur TomTom a supprimé sa réponse avec le Mersenne Twister sans préavis après que j'ai signalé dans un commentaire que j'avais découvert qu'il générait des numéros en double plus tôt que prévu. Donc je suppose que cela exclut complètement le Mersenne Twister.

MISE À JOUR 6

J'ai testé une autre technique suggérée qui semble prometteuse, Skip32 et, bien que la qualité des nombres aléatoires m'ait beaucoup plu, l'algorithme ne permet pas de générer toute la gamme des nombres entiers en un temps acceptable. Malheureusement, il n'est pas à la hauteur des autres techniques qui ont permis d'achever le processus. J'ai utilisé l'implémentation en C# de aquí J'ai modifié le code pour réduire le nombre de tours à 1, mais il ne peut toujours pas se terminer dans les temps.

Après tout, si l'on en juge par les résultats décrits ci-dessus, mon choix personnel pour la solution va aux inverses multiplicatifs modulaires suivie de très près par la technique générateur de congruence linéaire . Certains diront peut-être que cette technique est inférieure à d'autres sur certains points, mais compte tenu de mes contraintes initiales, je dirais qu'elle est la plus adaptée.

Answer 1

Si vous n'avez pas besoin que les nombres aléatoires soient cryptographiquement sûrs, vous pouvez utiliser un fichier de type Générateur linéaire de congruence .

Un LCG est une formule de la forme X_n+1 = X_n * a + c (mod m), il nécessite une mémoire constante et un temps constant pour chaque nombre généré.
Si les valeurs appropriées pour le LCG sont choisies, il aura une longueur de période complète, ce qui signifie qu'il produira tous les nombres compris entre 0 et le module que vous avez choisi.

Un LCG a une période complète si et seulement si :

• Le module et l'incrément sont relativement premiers, c'est-à-dire que GCD(m, c) = 1
• a - 1 est divisible par tous les facteurs premiers de m
• Si m est divisible par 4, a - 1 doit être divisible par 4.

Notre module est 2 ^ 32 c'est-à-dire a doit être un nombre de forme 4k + 1 où k est un nombre entier arbitraire, et c ne doit pas être divisible par 2.

Bien qu'il s'agisse d'une question en C#, j'ai codé un petit programme en C++ pour tester la vitesse de cette solution, puisque je suis plus à l'aise dans ce langage :

#include <iostream>
#include <stdlib.h>

class lcg {
private:
    unsigned a, c, val;
public:
    lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
    lcg(unsigned seed, unsigned a, unsigned c) {
        val = seed;
        this->a = a;
        this->c = c;
        std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
    }

    unsigned next() {
        this->val = a * this->val + c;
        return this->val;
    }
};

int main() {
    srand(time(NULL));
    unsigned seed = rand();
    int dummy = 0;
    lcg gen(seed);
    time_t t = time(NULL);
    for (uint64_t i = 0; i < 0x100000000ULL; i++) {
        if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
    }
    std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
    if (dummy > 0) return 0;
    return 1;
}

Vous pouvez remarquer que je n'utilise pas l'opération modulus dans la classe lcg, c'est parce que nous utilisons le débordement des entiers 32 bits pour notre opération modulus.
Cela produit toutes les valeurs dans la plage [0, 4294967295] inclusive.
J'ai également dû ajouter une variable fictive pour que le compilateur n'optimise pas tout.
Sans optimisation, cette solution se termine en 15 secondes environ, tandis qu'avec -O2, une optimisation modérée, elle se termine en moins de 5 secondes.

Si le caractère aléatoire "réel" n'est pas un problème, c'est une solution très rapide.

Answer 2

Existe-t-il un moyen dans .NET

En fait, cela peut être fait dans presque toutes les langues.

pour générer une séquence de tous les entiers de 32 bits (Int32)

Sí.

dans un ordre aléatoire,

Nous devons ici nous mettre d'accord sur la terminologie, car le terme "aléatoire" n'est pas ce que la plupart des gens pensent. Nous y reviendrons dans un instant.

sans répétitions,

Sí.

et de manière efficace en termes de mémoire ?

Sí.

Une mémoire efficace signifie que l'on utilise au maximum quelques centaines de méga-octets de mémoire principale.

Ok, alors est-ce qu'utiliser presque aucune mémoire serait acceptable ? ;-)

Avant d'en venir à la suggestion, nous devons clarifier la question du "caractère aléatoire". Quelque chose qui est vraiment aléatoire n'a pas de modèle discernable. Par conséquent, exécuter l'algorithme des millions de fois d'affilée pourrait théoriquement retourner la même valeur à travers toutes les itérations. Si vous ajoutez le concept de "doit être différent de l'itération précédente", alors ce n'est plus aléatoire. Cependant, si l'on considère l'ensemble des exigences, il semble que tout ce qui est réellement demandé soit "différents modèles de distribution des entiers". Et c'est faisable.

Alors comment le faire efficacement ? Utilisez Inverses multiplicatifs modulaires . Je l'ai utilisé pour répondre à la question suivante qui avait une exigence similaire de générer des données d'échantillon non répétitives, pseudo-aléatoires, dans certaines limites :

Générer un temps aléatoire différent dans l'intervalle donné

J'ai entendu parler de ce concept pour la première fois ici ( générer un ID numérique unique apparemment aléatoire dans SQL Server ) et vous pouvez utiliser l'une des calculatrices en ligne suivantes pour déterminer vos valeurs "Entier" et "Inverses Multiplicatives Modulaires (IMM)" :

• http://planetcalc.com/3311/
• http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php

En appliquant ce concept ici, vous utiliseriez Int32.MaxSize comme valeur modulo.

Cela donnerait l'impression d'une distribution aléatoire, sans risque de collision et sans mémoire nécessaire pour stocker les valeurs déjà utilisées.

Le seul problème initial est que le modèle de distribution est toujours le même pour les mêmes valeurs "Integer" et "MMI". Vous pouvez donc obtenir des modèles différents en ajoutant un Int généré "aléatoirement" à la valeur de départ (comme je crois l'avoir fait dans ma réponse sur la génération des données échantillons dans SQL Server) ou vous pouvez pré-générer plusieurs combinaisons de valeurs "Integer" et "MMI" correspondantes, les stocker dans un fichier de configuration / dictionnaire, et utiliser une fonction aléatoire .NET pour en choisir une au début de chaque exécution. Même si vous stockez 100 combinaisons, cela ne consomme pratiquement pas de mémoire (en supposant que ce n'est pas dans un fichier de configuration). En fait, si vous stockez les deux en tant que Int et que le dictionnaire utilise Int comme index, alors 1000 valeurs représentent environ 12k ?

---

UPDATE

Notes :

• Il existe une tendance dans les résultats, mais elle n'est pas perceptible à moins d'en avoir suffisamment à un moment donné pour les examiner dans leur ensemble. Pour la plupart des cas d'utilisation, cette situation est acceptable, car aucun destinataire des valeurs n'en possède une grande collection, ni ne sait qu'elles ont été attribuées dans l'ordre sans aucune discontinuité (et cette connaissance est nécessaire pour déterminer s'il existe une tendance).
• Seule une des deux valeurs variables - "Integer" et "Modular Multiplicative Inverse (MMI)" - est nécessaire dans la formule pour une exécution particulière. Par conséquent :
  • chaque paire donne deux séquences distinctes
  • si l'on maintient un ensemble en mémoire, on n'a besoin que d'un simple tableau, et si l'on suppose que l'indice du tableau n'est qu'un décalage en mémoire par rapport à l'adresse de base du tableau, alors la mémoire requise ne devrait être que de 4 octets * capacité (c'est-à-dire que 1024 options ne représentent que 4k, non ?)

Voici un code de test. Il est écrit en T-SQL pour Microsoft SQL Server puisque c'est là que je travaille principalement, et il a aussi l'avantage de rendre les choses très faciles, comme tester l'unicité, les valeurs min et max, etc, sans avoir besoin de compiler quoi que ce soit. La syntaxe fonctionnera dans SQL Server 2008 ou plus récent. Pour SQL Server 2005, l'initialisation des variables n'avait pas encore été introduite, donc chaque DECLARE qui contient un = devrait simplement être séparée dans le DECLARE par lui-même et un SET @Variable = ... quelle que soit la manière dont cette variable est initialisée. Et le SET @Index += 1; devrait devenir SET @Index = @Index + 1; .

Le code de test sera erroné si vous fournissez des valeurs qui produisent des doublons. Et la requête finale indique s'il y a des lacunes puisqu'on peut en déduire que si la variable de table population ne s'est pas trompée (donc pas de doublons), y le nombre total de valeurs est le nombre attendu, alors il ne peut y avoir de lacunes (c'est-à-dire de valeurs manquantes) que SI l'une ou l'autre ou les deux valeurs MIN et MAX réelles sont en dehors des valeurs attendues.

VEUILLEZ NOTER que ce code de test n'implique pas que l'une des valeurs soit pré-générée ou doive être stockée. Le code stocke uniquement les valeurs afin de tester l'unicité et les valeurs min/max. En pratique, tout ce qui est nécessaire est la formule simple, et tout ce qui est nécessaire pour passer dans cette formule est :

• la capacité (bien qu'elle puisse également être codée en dur dans ce cas)
• la valeur MMI / Integer
• l'"indice" actuel

Vous n'avez donc besoin de gérer que 2 ou 3 valeurs simples.

DECLARE @TotalCapacity INT = 30; -- Modulo; -5 to +4 = 10 OR Int32.MinValue
                                 -- to Int32.MaxValue = (UInt32.MaxValue + 1)
DECLARE @MMI INT = 7; -- Modular Multiplicative Inverse (MMI) or
                      -- Integer (derived from @TotalCapacity)

DECLARE @Offset INT = 0; -- needs to stay at 0 if min and max values are hard-set
-----------
DECLARE @Index INT = (1 + @Offset); -- start

DECLARE @EnsureUnique TABLE ([OrderNum] INT NOT NULL IDENTITY(1, 1),
                             [Value] INT NOT NULL UNIQUE);
SET NOCOUNT ON;

BEGIN TRY
    WHILE (@Index < (@TotalCapacity + 1 + @Offset)) -- range + 1
    BEGIN
        INSERT INTO @EnsureUnique ([Value]) VALUES (
                 ((@Index * @MMI) % @TotalCapacity) - (@TotalCapacity / 2) + @Offset
                                                   );
        SET @Index += 1;
    END;
END TRY
BEGIN CATCH
    DECLARE @Error NVARCHAR(4000) = ERROR_MESSAGE();
    RAISERROR(@Error, 16, 1);
    RETURN;
END CATCH;

SELECT * FROM @EnsureUnique ORDER BY [OrderNum] ASC;
SELECT COUNT(*) AS [TotalValues],
       @TotalCapacity AS [ExpectedCapacity],
       MIN([Value]) AS [MinValue],
       (@TotalCapacity / -2) AS [ExpectedMinValue],
       MAX([Value]) AS [MaxValue],
       (@TotalCapacity / 2) - 1 AS [ExpectedMaxValue]
FROM   @EnsureUnique;

Answer 3

Un PRP 32 bits en mode CTR me semble être la seule approche viable (votre 4ème variante).

Vous pouvez soit

• Utilisez un chiffrement par blocs de 32 bits dédié.

  Skip32, la variante 32 bits de Skipjack, est un choix populaire.

  En guise de compromis entre la qualité/sécurité et les performances, vous pouvez adapter le nombre de cartouches à vos besoins. Un plus grand nombre de tours est plus lent mais plus sûr.

• Cryptage avec préservation de la longueur (un cas particulier de cryptage avec préservation du format)

  Le mode FFX est la recommandation typique. Mais dans ses instanciations typiques (par exemple en utilisant AES comme chiffrement sous-jacent), ce sera beaucoup plus lent que les chiffrements par blocs 32 bits dédiés.

Notez que beaucoup de ces constructions ont un défaut important : ce sont même des permutations. Cela signifie qu'une fois que vous avez vu 2^32-2 sorties, vous serez en mesure de prédire l'avant-dernière sortie avec certitude, au lieu de seulement 50%. Je pense que l'article de Rogaways AEZ mentionne un moyen de corriger ce défaut.

Answer 4

En guise de préambule à cette réponse, je dirai que je suis conscient que certaines des autres réponses sont infiniment plus élégantes et répondent probablement mieux à vos besoins que celle-ci. Il s'agit très certainement d'une approche par la force brute de ce problème.

Si l'obtention d'un résultat vraiment aléatoire* (ou suffisamment pseudo-aléatoire* à des fins cryptographiques) est importante, vous pourriez générer à l'avance une liste de tous les entiers et les stocker sur le disque dans un ordre aléatoire. Au moment de l'exécution de votre programme, vous lisez ensuite ces nombres sur le disque.

Vous trouverez ci-dessous les grandes lignes de l'algorithme que je propose pour générer ces chiffres. Tous les nombres entiers 32 bits peuvent être stockés dans ~16 GiB d'espace disque (32 bits = 4 octets, 4 octets / nombre entier * 2^32 nombres entiers = 2^34 octets = 16 GiB, plus toute surcharge dont le système d'exploitation/système de fichiers a besoin), et j'ai considéré que "quelques centaines de mégaoctets" signifient que vous voulez lire un fichier de pas plus de 256 MiB à la fois.

1. Générer 16 GiB / 256 MiB = 64 fichiers texte ASCII avec 256 MiB de caractères "nuls" (tous les bits sont à 0) chacun. Nommez chaque fichier texte "0.txt" à "64.txt".
2. Boucle séquentiellement de Int32.MinValue à Int32.MaxValue, en sautant 0. C'est la valeur de l'entier que vous êtes en train de stocker.
3. À chaque itération, générez un nombre entier aléatoire compris entre 0 et UInt32.MaxValue à partir de la source d'aléa de votre choix (générateur aléatoire matériel réel, algorithme pseudo-aléatoire, etc.) Il s'agit de l'index de la valeur que vous stockez actuellement.
4. Divisez l'index en deux entiers : les 6 bits les plus significatifs, et les 26 restants. Utilisez les bits supérieurs pour charger le fichier texte correspondant.
5. Multipliez les 26 bits inférieurs par 4 et utilisez-les comme index dans le fichier ouvert. Si les quatre octets suivant cet index sont toujours le caractère "null", codez la valeur actuelle en quatre caractères ASCII et stockez ces caractères à cette position. S'ils ne sont pas tous le caractère "null", retournez à l'étape 3.
6. Répétez l'opération jusqu'à ce que tous les entiers aient été stockés.

Cela permettrait de s'assurer que les numéros proviennent d'une source aléatoire connue, mais qu'ils restent uniques, plutôt que d'avoir les limites de certaines des autres solutions proposées. La "compilation" prendrait beaucoup de temps (surtout avec l'algorithme relativement naïf ci-dessus), mais elle répondrait aux exigences d'efficacité de l'exécution.

Au moment de l'exécution, vous pouvez maintenant générer un indice de départ aléatoire, puis lire les octets des fichiers de manière séquentielle pour obtenir une séquence unique, aléatoire* et non répétitive d'entiers. En supposant que vous utilisiez un nombre relativement faible d'entiers à la fois, vous pourriez même indexer aléatoirement dans les fichiers, en stockant les indices que vous avez utilisés et en vous assurant qu'un nombre n'est pas répété de cette façon.

(* Je comprends que le caractère aléatoire de toute source est diminué par l'imposition de la contrainte d'"unicité", mais cette approche devrait produire des nombres relativement proches en termes de caractère aléatoire de la source originale).

TL;DR - Mélangez les entiers à l'avance, stockez-les tous sur le disque dans un certain nombre de fichiers plus petits, puis lisez les fichiers selon les besoins au moment de l'exécution.

Answer 5

Comme vos chiffres, selon votre définition, sont supposés être au hasard alors, par définition, il n'y a pas d'autre moyen que de les stocker tous, car les nombres n'ont aucune relation intrinsèque entre eux. Cela signifie donc que vous devez stocker toutes les valeurs que vous avez utilisées afin d'éviter qu'elles ne soient réutilisées.

Toutefois, en informatique, il suffit que le motif ne soit pas "perceptible". Habituellement, le système calcule un nombre aléatoire en effectuant des opérations de multiplication avec d'énormes valeurs prédéterminées et des valeurs de temporisation de telle sorte qu'elles débordent et semblent ainsi sélectionnées au hasard. Donc, soit vous utilisez votre troisième option, soit vous devez penser à générer ces nombres pseudo-aléatoires de manière à pouvoir reproduire la séquence de chaque nombre généré et vérifier si quelque chose se reproduit. Cela serait évidemment extrêmement coûteux en termes de calcul, mais vous avez demandé l'efficacité de la mémoire.

Ainsi, vous pourriez stocker le nombre d'éléments avec lequel vous avez ensemencé votre générateur aléatoire et le nombre d'éléments que vous avez générés. Chaque fois que vous avez besoin d'un nouveau nombre, réensemencez le générateur et parcourez le nombre d'éléments que vous avez générés + 1. C'est votre nouveau nombre. Maintenant, réinitialisez et itérez à nouveau la séquence pour vérifier si elle s'est produite auparavant.

Donc quelque chose comme ça :

int seed = 123;
Int64 counter = 0;
Random rnd = new Random(seed);

int GetUniqueRandom()
{
    int newNumber = rnd.Next();
    Random rndCheck = new Random(seed);

    counter++;

    for (int j = 0; j < counter; j++)
    {
        int checkNumber = rndCheck.Next();

        if (checkNumber == newNumber)
            return GetUniqueRandom();
    }

    return newNumber;        
}

EDITAR: Il a été souligné que counter atteindra une valeur énorme et on ne sait pas s'il débordera avant que vous ayez obtenu les 4 milliards de valeurs ou non.