java - with - Pourquoi ce code utilisant des chaînes aléatoires imprime-t-il "hello world"?




randomstringutils (10)

À partir des documents Java, il s'agit d'une fonctionnalité intentionnelle lors de la spécification d'une valeur de départ pour la classe Random.

Si deux occurrences de Random sont créées avec la même graine et que la même séquence d'appels de méthodes est faite pour chacune, elles génèreront et renverront des séquences identiques de nombres. Afin de garantir cette propriété, des algorithmes particuliers sont spécifiés pour la classe Random. Les implémentations Java doivent utiliser tous les algorithmes présentés ici pour la classe Random, pour des raisons de portabilité absolue du code Java.

http://docs.oracle.com/javase/1.4.2/docs/api/java/util/Random.html

Bizarre cependant, on pourrait penser qu'il y a des problèmes de sécurité implicites en ayant des nombres aléatoires prévisibles.

L'instruction d'impression suivante afficherait "Bonjour tout le monde". Quelqu'un pourrait-il expliquer cela?

System.out.println(randomString(-229985452) + " " + randomString(-147909649));

Et randomString() ressemble à ceci:

public static String randomString(int i)
{
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    while (true)
    {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char)('`' + k));
    }

    return sb.toString();
}

Aléatoire retourne toujours la même séquence. Il est utilisé pour mélanger les tableaux et d'autres opérations comme permutations.

Pour obtenir différentes séquences, il est nécessaire d'initialiser la séquence dans une certaine position, appelée "graine".

Le randomSting obtient le nombre aléatoire dans la position i (seed = -229985452) de la séquence "random". Utilise ensuite le code ASCII pour les 27 caractères suivants dans la séquence après la position de départ jusqu'à ce que cette valeur soit égale à 0. Cela retourne le "bonjour". La même opération est faite pour "monde".

Je pense que le code n'a pas fonctionné pour d'autres mots. Le gars qui a programmé ça connaît très bien la séquence aléatoire.

C'est un très bon code geek!


Dérivé de la réponse de Denis Tulskiy , cette méthode génère la graine.

public static long generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
        for (long seed = start; seed < finish; seed++) {
            Random random = new Random(seed);

            for (int i = 0; i < input.length; i++)
                pool[i] = (char) (random.nextInt(27)+'`');

            if (random.nextInt(27) == 0) {
                for (int i = 0; i < input.length; i++) {
                    if (input[i] != pool[i])
                        continue label;
                }
                return seed;
            }

        }

    throw new NoSuchElementException("Sorry :/");
}

Il s'agit de "graine". Les mêmes graines donnent le même résultat.


J'ai été intrigué par cela, j'ai couru ce générateur de mots au hasard sur une liste de mots du dictionnaire. Plage: Integer.MIN_VALUE à Integer.MAX_VALUE

J'ai eu 15131 hits.

int[] arrInt = {-2146926310, -1885533740, -274140519, 
                -2145247212, -1845077092, -2143584283,
                -2147483454, -2138225126, -2147375969};

for(int seed : arrInt){
    System.out.print(randomString(seed) + " ");
}

Impressions

the quick browny fox jumps over a lazy dog 

Je vais juste laisser ça ici. Celui qui a beaucoup de temps (CPU), n'hésitez pas à expérimenter :) Aussi, si vous avez maîtrisé fork-join-fu pour que cette chose brûle tous les cœurs de CPU (les threads sont ennuyeux, non?), Merci de partager votre code. Je l'apprécierais grandement.

public static void main(String[] args) {
    long time = System.currentTimeMillis();
    generate("stack");
    generate("over");
    generate("flow");
    generate("rulez");

    System.out.println("Took " + (System.currentTimeMillis() - time) + " ms");
}

private static void generate(String goal) {
    long[] seed = generateSeed(goal, Long.MIN_VALUE, Long.MAX_VALUE);
    System.out.println(seed[0]);
    System.out.println(randomString(seed[0], (char) seed[1]));
}

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();
    char[] pool = new char[input.length];
    label:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);

        for (int i = 0; i < input.length; i++)
            pool[i] = (char) random.nextInt(27);

        if (random.nextInt(27) == 0) {
            int base = input[0] - pool[0];
            for (int i = 1; i < input.length; i++) {
                if (input[i] - pool[i] != base)
                    continue label;
            }
            return new long[]{seed, base};
        }

    }

    throw new NoSuchElementException("Sorry :/");
}

public static String randomString(long i, char base) {
    System.out.println("Using base: '" + base + "'");
    Random ran = new Random(i);
    StringBuilder sb = new StringBuilder();
    for (int n = 0; ; n++) {
        int k = ran.nextInt(27);
        if (k == 0)
            break;

        sb.append((char) (base + k));
    }

    return sb.toString();
}

Sortie:

-9223372036808280701
Using base: 'Z'
stack
-9223372036853943469
Using base: 'b'
over
-9223372036852834412
Using base: 'e'
flow
-9223372036838149518
Using base: 'd'
rulez
Took 7087 ms

Le principal est la classe aléatoire construite avec la même graine générera le même modèle de nombres à chaque fois.


Les autres réponses expliquent pourquoi, mais voici comment.

Étant donné une instance de Random :

Random r = new Random(-229985452)

Les 6 premiers nombres r.nextInt(27) par r.nextInt(27) sont:

8
5
12
12
15
0

et les 6 premiers nombres que r.nextInt(27) génère étant donné Random r = new Random(-147909649) sont:

23
15
18
12
4
0

Ensuite, ajoutez simplement ces nombres à la représentation entière du caractère ` (qui est 96):

8  + 96 = 104 --> h
5  + 96 = 101 --> e
12 + 96 = 108 --> l
12 + 96 = 108 --> l
15 + 96 = 111 --> o

23 + 96 = 119 --> w
15 + 96 = 111 --> o
18 + 96 = 114 --> r
12 + 96 = 108 --> l
4  + 96 = 100 --> d

Tout le monde ici a fait un excellent travail pour expliquer comment le code fonctionne et montrer comment vous pouvez construire vos propres exemples, mais voici une réponse théorique montrant pourquoi nous pouvons raisonnablement espérer qu'une solution existera finalement.

Les 26 lettres minuscules différentes forment notre alphabet Σ . Pour permettre de générer des mots de longueurs différentes, nous ajoutons un symbole de terminaison pour obtenir un alphabet étendu Σ' := Σ ∪ {⊥} .

Soit α un symbole et X une variable aléatoire uniformément distribuée sur Σ' . La probabilité d'obtenir ce symbole, P(X = α) , et son contenu informationnel, I(α) , sont donnés par:

P (X = α) = 1 / | Σ '| = 1/27

I (α) = -log₂ [P (X = α)] = -log₂ (1/27) = log₂ (27)

Pour un mot ω ∈ Σ* et son homologue ⊥- terminé ω' := ω · ⊥ ∈ (Σ')* , nous avons

I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)

Puisque le générateur de nombres pseudo-aléatoires (PRNG) est initialisé avec une graine de 32 bits, on peut s'attendre à ce que la plupart des mots de longueur

λ = plancher [32 / log₂ (27)] - 1 = 5

être généré par au moins une graine. Même si nous devions rechercher un mot de 6 caractères, nous aurions quand même du succès dans environ 41,06% des cas. Pas trop mal.

Pour 7 lettres, nous regardons plus près de 1,52%, mais je ne l'avais pas réalisé avant de l'essayer:

#include <iostream>
#include <random>

int main()
{
    std::mt19937 rng(631647094);
    std::uniform_int_distribution<char> dist('a', 'z' + 1);

    char alpha;
    while ((alpha = dist(rng)) != 'z' + 1)
    {
        std::cout << alpha;
    }
}

Voir la sortie: http://ideone.com/JRGb3l


Voici une amélioration mineure pour Denis Tulskiy. Il coupe le temps de moitié

public static long[] generateSeed(String goal, long start, long finish) {
    char[] input = goal.toCharArray();

    int[] dif = new int[input.length - 1];
    for (int i = 1; i < input.length; i++) {
        dif[i - 1] = input[i] - input[i - 1];
    }

    mainLoop:
    for (long seed = start; seed < finish; seed++) {
        Random random = new Random(seed);
        int lastChar = random.nextInt(27);
        int base = input[0] - lastChar;
        for (int d : dif) {
            int nextChar = random.nextInt(27);
            if (nextChar - lastChar != d) {
                continue mainLoop;
            }
            lastChar = nextChar;
        }
        if(random.nextInt(27) == 0){
            return new long[]{seed, base};
        }
    }

    throw new NoSuchElementException("Sorry :/");
}






random