Je lance plusieurs programmes C / C ++ en parallèle, qui reposent sur des nombres aléatoires. Assez nouveau sur ce sujet, j'ai entendu dire que la graine devrait être faite au fil du temps.

De plus, j'utilise l'algorithme de Fisher Yates pour obtenir une liste avec des valeurs aléatoires uniques mélangées. Cependant, démarrer le programme deux fois en parallèle donne les mêmes résultats pour les deux listes.

Comment puis-je réparer cela? Puis-je utiliser une graine différente, mais toujours pertinente?

Mon code de test simple pour cela ressemble à ceci:

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include <time.h>
static int rand_int(int n) {

        int limit = RAND_MAX - RAND_MAX % n;
        int rnd;

        do {
                rnd = rand();
        }
        while (rnd >= limit);
        return rnd % n;
}


void shuffle(int *array, int n) {

        int i, j, tmp;
        for (i = n - 1; i > 0; i--) {
                j = rand_int(i + 1);
                tmp = array[j];
                array[j] = array[i];
                array[i] = tmp;
        }
}


int main(int argc,char* argv[]){

        srand(time(NULL));
        int x = 100;
        int randvals[100];
        for(int i =0; i < x;i++)
                randvals[i] = i;

        shuffle(randvals,x);
        for(int i=0;i < x;i++)
                printf("%d %d \n",i,randvals[i]);

}

J'ai utilisé l'implémentation de l'algorithme fisher yates à partir d'ici:

http://www.sanfoundry.com/c-program-implement-fisher-yates-algorithm-array-shuffling/

J'ai commencé les programmes en parallèle comme ceci:

./randomprogram >> a.txt & ./randomprogram >> b.txt

Puis comparé les deux fichiers texte, qui avaient le même contenu.

L'application finale est destinée à l'augmentation des données dans le domaine de l'apprentissage profond. La machine exécute Ubuntu 16.04 avec C ++ 11.

2
Kev1n91 11 août 2017 à 20:20

2 réponses

Meilleure réponse

Vous obtenez les mêmes résultats en raison de la façon dont vous semez le RNG:

srand(time(NULL));

La fonction time renvoie le temps en secondes depuis l'époque. Si deux instances du programme démarrent pendant la même seconde (ce qui est probable si vous les lancez en succession rapide), alors les deux utiliseront la même graine et obtiendront le même ensemble de valeurs aléatoires.

Vous devez ajouter plus d'entropie à votre graine. Un moyen simple de le faire est de XOR au niveau du bit de l'ID de processus avec l'heure:

srand(time(NULL) ^ getpid());
4
dbush 11 août 2017 à 17:26

Comme je l'ai mentionné dans un commentaire, j'aime utiliser un pseudo Xorshift * générateur de nombres aléatoires, initialisé à partir de /dev/urandom si présent, sinon en utilisant POSIX.1 clock_gettime() et getpid() pour amorcer le générateur.

C'est assez bon pour la plupart des travaux statistiques, mais évidemment pas pour tout type de sécurité ou à des fins cryptographiques.

Considérez l'implémentation en ligne xorshift64.h suivante:

#ifndef   XORSHIFT64_H
#define   XORSHIFT64_H
#include <stdlib.h>
#include <unistd.h>
#include <stdint.h>
#include <time.h>

#ifndef  SEED_SOURCE
#define  SEED_SOURCE  "/dev/urandom"
#endif

typedef struct {
    uint64_t    state[1];
} prng_state;

/* Mixes state by generating 'rounds' pseudorandom numbers,
   but does not store them anywhere. This is often done
   to ensure a well-mixed state after seeding the generator.
*/
static inline void prng_skip(prng_state *prng, size_t rounds)
{
    uint64_t state = prng->state[0];
    while (rounds-->0) {
        state ^= state >> 12;
        state ^= state << 25;
        state ^= state >> 27;
    }
    prng->state[0] = state;
}

/* Returns an uniform pseudorandom number between 0 and 2**64-1, inclusive.
*/
static inline uint64_t prng_u64(prng_state *prng)
{
    uint64_t state = prng->state[0];
    state ^= state >> 12;
    state ^= state << 25;
    state ^= state >> 27;
    prng->state[0] = state;
    return state * UINT64_C(2685821657736338717);
}

/* Returns an uniform pseudorandom number [0, 1), excluding 1.
   This carefully avoids the (2**64-1)/2**64 bias on 0,
   but assumes that the double type has at most 63 bits of
   precision in the mantissa.
*/
static inline double prng_one(prng_state *prng)
{
    uint64_t u;
    double   d;
    do {
        do {
            u = prng_u64(prng);
        } while (!u);
        d = (double)(u - 1u) / 18446744073709551616.0;
    } while (d == 1.0);
    return d;
}

/* Returns an uniform pseudorandom number (-1, 1), excluding -1 and +1.
   This carefully avoids the (2**64-1)/2**64 bias on 0,
   but assumes that the double type has at most 63 bits of
   precision in the mantissa.
*/
static inline double prng_delta(prng_state *prng)
{
    uint64_t u;
    double   d;
    do {
        do {
            u = prng_u64(prng);
        } while (!u);
        d = ((double)(u - 1u) - 9223372036854775808.0) / 9223372036854775808.0;
    } while (d == -1.0 || d == 1.0);
    return d;
}

/* Returns an uniform pseudorandom integer between min and max, inclusive.
   Uses the exclusion method to ensure uniform distribution.
*/
static inline uint64_t prng_range(prng_state *prng, const uint64_t min, const uint64_t max)
{
    if (min != max) {
        const uint64_t  basis = (min < max) ? min : max;
        const uint64_t  range = (min < max) ? max-min : min-max;
        uint64_t        mask = range;
        uint64_t        u;

        /* In range, all bits up to the higest bit set in range, must be set. */
        mask |= mask >> 1;
        mask |= mask >> 2;
        mask |= mask >> 4;
        mask |= mask >> 8;
        mask |= mask >> 16;
        mask |= mask >> 32;

        /* In all cases, range <= mask < 2*range, so at worst case,
           (mask = 2*range-1), this excludes at most 50% of generated values,
           on average. */
        do {
            u = prng_u64(prng) & mask;
        } while (u > range);

        return u + basis;
    } else
        return min;
}

static inline void prng_seed(prng_state *prng)
{
#if _POSIX_TIMERS-0 > 0
    struct timespec  now;
#endif
    FILE            *src;

    /* Try /dev/urandom. */
    src = fopen(SEED_SOURCE, "r");
    if (src) {
        int  tries = 16;
        while (tries-->0) {
            if (fread(prng->state, sizeof prng->state, 1, src) != 1)
                break;
            if (prng->state[0]) {
                fclose(src);
                return;
            }
        }
        fclose(src);
    }

#if _POSIX_TIMERS-0 > 0
#if _POSIX_MONOTONIC_CLOCK-0 > 0
    if (clock_gettime(CLOCK_MONOTONIC, &now) == 0) {
        prng->state[0] = (uint64_t)((uint64_t)now.tv_sec * UINT64_C(60834327289))
                       ^ (uint64_t)((uint64_t)now.tv_nsec * UINT64_C(34958268769))
                       ^ (uint64_t)((uint64_t)getpid() * UINT64_C(2772668794075091))
                       ^ (uint64_t)((uint64_t)getppid() * UINT64_C(19455108437));
        if (prng->state[0])
            return;
    } else
#endif
    if (clock_gettime(CLOCK_REALTIME, &now) == 0) {
        prng->state[0] = (uint64_t)((uint64_t)now.tv_sec * UINT64_C(60834327289))
                       ^ (uint64_t)((uint64_t)now.tv_nsec * UINT64_C(34958268769))
                       ^ (uint64_t)((uint64_t)getpid() * UINT64_C(2772668794075091))
                       ^ (uint64_t)((uint64_t)getppid() * UINT64_C(19455108437));
        if (prng->state[0])
            return;
    }
#endif

    prng->state[0] = (uint64_t)((uint64_t)time(NULL) * UINT64_C(60834327289))
                   ^ (uint64_t)((uint64_t)clock() * UINT64_C(34958268769))
                   ^ (uint64_t)((uint64_t)getpid() * UINT64_C(2772668794075091))
                   ^ (uint64_t)((uint64_t)getppid() * UINT64_C(19455108437));
    if (!prng->state[0])
        prng->state[0] = (uint64_t)UINT64_C(16233055073);
}

#endif /* XORSHIFT64_H */

S'il peut amorcer l'état de SEED_SOURCE, il est utilisé tel quel. Sinon, si POSIX.1 clock_gettime() est disponible, il est utilisé (CLOCK_MONOTONIC, si possible; sinon CLOCK_REALTIME). Sinon, le temps (time(NULL)), le temps processeur passé jusqu'ici (clock()), l'ID de processus (getpid()) et l'ID de processus parent (getppid()) sont utilisés pour amorcer le Etat.

Si vous souhaitez que ce qui précède s'exécute également sous Windows, vous devez ajouter quelques #ifndef _WIN32 gardes et soit omettre les éléments d'ID de processus, soit les remplacer par autre chose. (Je n'utilise pas Windows moi-même et je ne peux pas tester un tel code, j'ai donc omis celui-ci ci-dessus.)

L'idée est que vous pouvez inclure le fichier ci-dessus et implémenter d'autres générateurs de nombres pseudo-aléatoires dans le même format, et choisir entre eux en incluant simplement différents fichiers. (Vous pouvez inclure plusieurs fichiers, mais vous devrez effectuer des piratages #define prng_state prng_somename_state, #include "somename.h", #undef prng_state pour garantir des noms uniques pour chacun.)

Voici un exemple d'utilisation de ce qui précède:

#include <stdlib.h>
#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>
#include "xorshift64.h"

int main(void)
{
    prng_state  prng1, prng2;

    prng_seed(&prng1);
    prng_seed(&prng2);

    printf("Seed 1 = 0x%016" PRIx64 "\n", prng1.state[0]);
    printf("Seed 2 = 0x%016" PRIx64 "\n", prng2.state[0]);

    printf("After skipping 16 rounds:\n");
    prng_skip(&prng1, 16);
    prng_skip(&prng2, 16); 

    printf("Seed 1 = 0x%016" PRIx64 "\n", prng1.state[0]);
    printf("Seed 2 = 0x%016" PRIx64 "\n", prng2.state[0]);

    return EXIT_SUCCESS;
}

De toute évidence, l'initialisation de deux PRNG comme celui-ci est problématique dans le cas de secours, car elle repose essentiellement sur clock() donnant des valeurs différentes pour des appels consécutifs (donc s'attend à ce que chaque appel prenne au moins 1 milliseconde de temps CPU).

Cependant, même un petit changement dans les graines ainsi générées est suffisant pour donner des séquences très différentes. J'aime générer et ignorer (sauter) un certain nombre de valeurs initiales pour m'assurer que l'état du générateur est bien mélangé:

Seed 1 = 0x8a62585b6e71f915
Seed 2 = 0x8a6259a84464e15f
After skipping 16 rounds:
Seed 1 = 0x9895f664c83ad25e
Seed 2 = 0xa3fd7359dd150e83

L'en-tête implémente également 0 <= prng_u64() < 2**64, 0 <= prng_one() < 1, -1 < prng_delta() < +1 et min <= prng_range(,min,max) <= max, qui devraient être uniformes.

J'utilise la variante Xorshift64 * ci-dessus pour les tâches où beaucoup de nombres pseudo-aléatoires assez uniformes sont nécessaires, de sorte que les fonctions ont également tendance à utiliser des méthodes plus rapides (comme un taux d'exclusion moyen maximal de 50% au lieu d'un fonctionnement par module de 64 bits, etc. ) (de ceux que je connais).

De plus, si vous avez besoin de répétabilité, vous pouvez simplement enregistrer une structure prng_state aléatoirement amorcée (un seul uint64_t), et la charger plus tard, pour reproduire exactement la même séquence. N'oubliez pas de ne faire le saut (générer et supprimer) qu'après un amorçage aléatoire, pas après avoir chargé une nouvelle graine à partir d'un fichier.

2
Nominal Animal 11 août 2017 à 19:32