Pytanie Dlaczego ten kod używający losowych ciągów drukuje "Witaj, świecie"?


Następująca instrukcja print wypisze "hello world". Czy ktoś mógłby to wyjaśnić?

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

I randomString() wygląda tak:

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();
}

1591
2018-03-03 04:38


pochodzenie


Cóż, te szczególne nasiona właśnie się sprawdziły. Losowe nie jest naprawdę losowe, jest pseudolosowe. - Doorknob
Działa, jak powiedzieli inni, ponieważ przypadek nie jest. Dla mnie bardziej interesującym pytaniem byłaby osoba, która to napisała, brutalnie wymuszała to, czy istnieje łatwy sposób przewidywania, co los wygeneruje dla następnych N wartości dla danego nasienia. Brutalne forsowanie jest łatwe, a dzięki nowoczesnemu sprzętowi nie powinno to zająć zbyt wiele czasu, więc nie było to wykonalne. Biorąc pod uwagę, że jest statyczny, można nawet łatwo rozpowszechniać wyszukiwanie w sieci. - jmoreno
Zastanawiam się, jaki jest cel n w for (int n = 0; ; n++). Mogą wykorzystać for(;;) lub while(true) zamiast! - Eng.Fouad
W prawdziwie losowej kolejności ostatecznie pojawi się każdy możliwy ciąg. W wysokiej jakości pseudo losowej sekwencji na puszce można rozsądnie spodziewać się każdego możliwego ciągu długości (log_s (N) - n) bitów (gdzie N jest liczbą bitów w wewnętrznym stanie PRNG, a n jest małą liczbą, pozwala wybrać 8 dla wygody ) pojawią się w cyklu. Ten kod uzyskuje pomoc przy korzystaniu ze swobodnie wybranego zakodowanego na stałe punktu początkowego (wartość backtick postaci), który otrzymuje prawie całe 8 bitów. - dmckee
zwycięzca najdziwniejszego sposobu na wydrukowanie "Witaj świecie" - osdamv


Odpowiedzi:


Kiedy wystąpi java.util.Random jest skonstruowany z określonym parametrem początkowym (w tym przypadku -229985452 lub -147909649), działa zgodnie z algorytmem generowania liczb losowych początek z tą wartością siewną.

Każdy Random zbudowane z tego samego materiału siewnego będą generować ten sam wzorzec liczb za każdym razem.


846
2018-03-03 04:40



@Vulcan - javadoc mówi, że materiał siewny ma 48 bitów. docs.oracle.com/javase/7/docs/api/java/util/Random.html. Poza tym rzeczywiste nasiona są wartościami 32-bitowymi. - Stephen C
Każdy element losowej sekwencji liczbowej przyjmuje modulo 27, aw każdym z nich znajduje się 6 elementów "hello\0" i "world\0". Jeśli założysz naprawdę losowy generator, szansa będzie wynosić 1 na 27 ^ 6 (387, 420,489), aby uzyskać sekwencję, której szukasz - więc jest to imponujące, ale nie do końca oszałamiające! - Russell Borogove
@RussellBorogove: Ale przy tych szansach i 2 ^ 64 możliwych nasionach, oczekiwane są 47,6 miliardowe wartości początkowe, które dają tę sekwencję. To tylko kwestia znalezienia jednego. - dan04
@ dan04 - Nie chciałem tego oszacować; w zależności od implementacji PRNG wielkość słowa początkowego może nie być równa wielkości stanu, a ścieżki sekwencji mogą nie być równomiernie rozłożone. Mimo to szanse są zdecydowanie dobre, a jeśli nie możesz znaleźć pary, możesz spróbować ponownie z inną obudową ("Hello"  "World") lub używając 122-k zamiast 96+klub ... - Russell Borogove
@ ThorbjørnRavnAndersen Javadoc określa, że ​​"określone algorytmy są określone dla klasy Random. Implementacje Java muszą używać wszystkich pokazanych tutaj algorytmów dla klasy Random, ze względu na całkowitą przenośność kodu Java." - Vulcan


Inne odpowiedzi wyjaśniają dlaczego, ale oto jak to zrobić.

Biorąc pod uwagę przykład Random:

Random r = new Random(-229985452)

Pierwsze 6 liczb, które r.nextInt(27) generuje to:

8
5
12
12
15
0

i pierwszych 6 liczb, które r.nextInt(27) generuje dany Random r = new Random(-147909649) są:

23
15
18
12
4
0

Następnie dodaj te liczby do całkowitej reprezentacji postaci ` (co stanowi 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

1086
2018-03-03 04:55



Pedantycznie, new Random(-229985452).nextInt(27)zawsze zwraca 8. - immibis
@immibis dlaczego? mam na myśli Random () powinien zwracać losową liczbę za każdym razem, a nie ustalony numer porządkowy? - roottraveller
@rootTraveller Na początek new Random() nie zwraca w ogóle numeru. - immibis
@immibis 4 lata i miesiąc późno, ale ustalone dla ciebie. ;RE - jpmc26


Zostawię to tutaj. Ktokolwiek ma dużo czasu (CPU) do stracenia, nie krępuj się eksperymentować :) Ponadto, jeśli opanowałeś trochę fork-join-fu, aby ta rzecz wypaliła wszystkie rdzenie procesora (tylko wątki są nudne, prawda?), Proszę udostępnij Twój kod. Byłbym bardzo wdzięczny.

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();
}

Wydajność:

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

263
2018-03-03 15:03



@Raz Dwa Trzy nextInt(27) oznacza w zakresie [0, 26]. - Eng.Fouad
@ Wulkana Większość nasion jest bardzo zbliżona do wartości maksymalnej, tak jak w przypadku wybierania liczb losowych od 1 do 1000, większość numerów, które otrzymasz, będzie miała trzy cyfry. Nic dziwnego, kiedy o tym myślisz :) - Thomas
@Vulcan W rzeczywistości, jeśli wykonasz obliczenia matematyczne, zobaczysz, że są one bliskie maksymalnej wartości od zera (przypuszczam, że nasiona są interpretowane jako niepodpisane w kodzie generacyjnym). Ale ponieważ liczba cyfr rośnie tylko logarytmicznie z rzeczywistą wartością, liczba wygląda naprawdę blisko, gdy tak naprawdę nie jest. - Thomas
Ciekawą i pokrewną zasadą jest Prawo Benforda, stwierdzając, że w wielu naturalnych źródłach danych początkowe liczby "1" i "2" pojawiają się znacznie częściej, z podobnego powodu: przejście od 9 do 10 zajmuje znacznie mniejszy współczynnik niż od 10 do 20. W tym przypadku przejść od 0 do int.max/10 zajmuje znacznie mniej czasu niż od int.max/10 do int.max. - FeepingCreature
@Marek: Nie sądzę, aby bogowie pseudo losowych aprobowali takie zachowanie. - Denis Tulskiy


Wszyscy tutaj świetnie spisali się, wyjaśniając, w jaki sposób działa kod i pokazując, w jaki sposób można tworzyć własne przykłady, ale oto teoretyczna odpowiedź z informacją, pokazującą, dlaczego możemy rozsądnie oczekiwać, że istnieje rozwiązanie, które zostanie ostatecznie znalezione przez brutalną siłę.

26 różnych małych liter tworzy nasz alfabet Σ. Aby umożliwić generowanie słów o różnych długościach, dodajemy dodatkowo symbol terminatora  aby uzyskać rozszerzony alfabet Σ' := Σ ∪ {⊥}.

Pozwolić α być symbolem i X równomiernie rozłożoną zmienną losową Σ'. Prawdopodobieństwo uzyskania tego symbolu, P(X = α)i jego zawartość informacyjna, I(α), są podane przez:

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

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

Na słowo ω ∈ Σ* i jego ⊥-zakończony odpowiednik ω' := ω · ⊥ ∈ (Σ')*, mamy

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

Ponieważ generator liczb pseudolosowych (PRNG) jest inicjowany za pomocą 32-bitowego źródła, możemy oczekiwać, że większość słów o długości do

λ = podłoga [32 / log₂ (27)] - 1 = 5

być generowane przez co najmniej jedno nasiono. Nawet jeśli szukalibyśmy 6-znakowego słowa, nadal odnosilibyśmy sukces w 41,06% przypadków. Niezbyt brudny.

W przypadku 7 liter zbliżamy się do 1,52%, ale nie zdawałem sobie z tego sprawy przed podjęciem próby:

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

Zobacz dane wyjściowe: http://ideone.com/JRGb3l


248
2018-03-04 09:49



moja teoria informacji jest słaba, ale uwielbiam ten dowód. Czy ktoś może mi wytłumaczyć linię lambda, wyraźnie dzielimy treść informacyjną na jedną z drugiej, ale dlaczego daje nam to słowo długości? jak już powiedziałem, jestem trochę zardzewiały, więc przepraszam, że pytam o oczywistość (N.B. ma coś wspólnego z limitem shannon - od wyjścia z kodu) - Mike H-R
@ MikeH-R Linia lambda to I(⍵) równanie zostało poprawione.I(⍵) to 32 (bity) i |⍵| okazuje się być 5 (symbole). - iceman


Napisałem szybki program, aby znaleźć te nasiona:

import java.lang.*;
import java.util.*;
import java.io.*;

public class RandomWords {
    public static void main (String[] args) {
        Set<String> wordSet = new HashSet<String>();
        String fileName = (args.length > 0 ? args[0] : "/usr/share/dict/words");
        readWordMap(wordSet, fileName);
        System.err.println(wordSet.size() + " words read.");
        findRandomWords(wordSet);
    }

    private static void readWordMap (Set<String> wordSet, String fileName) {
        try {
            BufferedReader reader = new BufferedReader(new FileReader(fileName));
            String line;
            while ((line = reader.readLine()) != null) {
                line = line.trim().toLowerCase();
                if (isLowerAlpha(line)) wordSet.add(line);
            }
        }
        catch (IOException e) {
            System.err.println("Error reading from " + fileName + ": " + e);
        }
    }

    private static boolean isLowerAlpha (String word) {
        char[] c = word.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] < 'a' || c[i] > 'z') return false;
        }
        return true;
    }

    private static void findRandomWords (Set<String> wordSet) {
        char[] c = new char[256];
        Random r = new Random();
        for (long seed0 = 0; seed0 >= 0; seed0++) {
            for (int sign = -1; sign <= 1; sign += 2) {
                long seed = seed0 * sign;
                r.setSeed(seed);
                int i;
                for (i = 0; i < c.length; i++) {
                    int n = r.nextInt(27);
                    if (n == 0) break;
                    c[i] = (char)((int)'a' + n - 1);
                }
                String s = new String(c, 0, i);
                if (wordSet.contains(s)) {
                    System.out.println(s + ": " + seed);
                    wordSet.remove(s);
                }
            }
        }
    }
}

Mam go już teraz w tle, ale jest już wystarczająco dużo słów na klasyczny pangram:

import java.lang.*;
import java.util.*;

public class RandomWordsTest {
    public static void main (String[] args) {
        long[] a = {-73, -157512326, -112386651, 71425, -104434815,
                    -128911, -88019, -7691161, 1115727};
        for (int i = 0; i < a.length; i++) {
            Random r = new Random(a[i]);
            StringBuilder sb = new StringBuilder();
            int n;
            while ((n = r.nextInt(27)) > 0) sb.append((char)('`' + n));
            System.out.println(sb);
        }
    }
}

(Demo o idee.)

Ps. -727295876, -128911, -1611659, -235516779.


65
2018-03-03 18:33



class R{ public static void main(String[] a) { System.out.println("-229985452, -147909649"); } także wykonuje pracę. - djechlin


Byłem tym zaintrygowany, uruchomiłem ten losowy generator słów na słownikowej liście słów. Zakres: Integer.MIN_VALUE na Integer.MAX_VALUE

Mam 15131 trafień.

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

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

Wydruki

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



Zrobiłeś mój dzień: DI próbowałem z Long.Min / Max i szukam nazwisk moich kolegów i tylko znalazłem petera: (peter 4611686018451441623 peter 24053719 peter -4611686018403334185 peter -9223372036830722089 peter -4611686017906248127 peter 521139777 peter 4611686018948527681 peter -9223372036333636031 peter - 4611686017645756173 peter 781631731 peter 4611686019209019635 peter -9223372036073144077 peter -4611686017420317288 peter 1007070616 peter -9223372035847705192) - Marcel


Większość generatorów liczb losowych jest w rzeczywistości "pseudolosowa". Są to Linearne Generatory Kontraktowe lub LCG (http://en.wikipedia.org/wiki/Linear_congruential_generator)

LCG są dość przewidywalne, biorąc pod uwagę stałe nasiona. Zasadniczo, użyj nasienia, które daje ci pierwszą literę, a następnie napisz aplikację, która kontynuuje generowanie następnej int (char), aż uderzysz w następną literę w ciągu docelowym i zapiszesz ile razy musiałeś przywołać LCG. Kontynuuj, dopóki nie wygenerujesz każdej litery.


26
2018-03-04 10:59



jaki jest przykład generatora liczb pseudolosowych - chiliNUT
@chiliNUT Takie generatory to zewnętrzne gadżety. Niektóre lampy elektroniczne. Lub źle napisany bit, który jest odczytywany 0 lub 1. Nie można zrobić czystego cyfrowego generatora liczb losowych, algorytmy cyfrowe NIE są przypadkowe, są absolutnie precyzyjne. - Gangnus
@chiliNUT Zbieraj wiele systemów operacyjnych entropia. Na przykład. w Linuksie możesz użyć /dev/urandom urządzenie do odczytu losowych danych. Jest to jednak rzadki zasób. Tak więc takie losowe dane są zwykle używane do wysiewania PRNG. - Adrian W
@AdrianW Wikipedia mówi urandom jest nadal pseudolosowy en.wikipedia.org/wiki//dev/random - chiliNUT
Tak, ale jest to kryptograficznie bezpieczne, co oznacza, że ​​nie można wykonywać brutalnych ataków (jak znaleźć nasienie dla "losowej" sekwencji "hello world") z losowymi sekwencjami utworzonymi od /dev/random. Artykuł cytowany powyżej mówi Jądro Linuksa generuje entropię z taktowania klawiatury, ruchów myszy i taktów IDE i udostępnia losowe dane znakowe innym procesom systemu operacyjnego za pomocą specjalnych plików / dev / random i / dev / urandom. Pozwól mi uwierzyć, że to jest naprawdę przypadkowe. Być może nie jest to w pełni poprawne. Ale /dev/random przynajmniej zawiera pewna entropia. - Adrian W