java यादृच्छिक तारों का उपयोग करके यह कोड "हैलो वर्ल्ड" प्रिंट क्यों करता है?




string random (12)

जावा दस्तावेज़ों से, यह यादृच्छिक वर्ग के लिए बीज मान निर्दिष्ट करते समय एक जानबूझकर विशेषता है।

यदि रैंडम के दो उदाहरण एक ही बीज के साथ बनाए जाते हैं, और प्रत्येक के लिए विधि कॉल का एक ही अनुक्रम बनाया जाता है, तो वे संख्याओं के समान अनुक्रम उत्पन्न और वापस कर देंगे। इस संपत्ति की गारंटी के लिए, श्रेणी रैंडम के लिए विशेष एल्गोरिदम निर्दिष्ट हैं। जावा कार्यान्वयन को जावा कोड की पूर्ण पोर्टेबिलिटी के लिए क्लास रैंडम के लिए यहां दिखाए गए सभी एल्गोरिदम का उपयोग करना होगा।

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

अजीब हालांकि, आपको लगता है कि अनुमानित 'यादृच्छिक' संख्याओं में अंतर्निहित सुरक्षा समस्याएं हैं।

निम्नलिखित प्रिंट स्टेटमेंट "हैलो वर्ल्ड" प्रिंट करेगा। क्या कोई इसे समझा सकता है?

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

और randomString() इस तरह दिखता है:

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

मैं इसे यहाँ छोड़ दूंगा। जिनके पास बहुत कुछ (सीपीयू) समय है, वे प्रयोग करने के लिए स्वतंत्र महसूस करते हैं :) इसके अलावा, अगर आपने कुछ फोर्क-जॉइन-फू को महारत हासिल कर लिया है ताकि यह सब कुछ सीपीयू कोर जलाए जा सके (केवल थ्रेड उबाऊ हो, है ना?), कृपया साझा करें तुम्हारा कोड। मुझे इसकी तारीफ़ करने में गर्व है।

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

आउटपुट:

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

डेनिस तुलस्की के उत्तर से व्युत्पन्न, यह विधि बीज उत्पन्न करती है।

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 :/");
}

सबसे यादृच्छिक संख्या जनरेटर वास्तव में, "छद्म यादृच्छिक" हैं। वे रैखिक संगठनात्मक जेनरेटर हैं, या एलसीजी ( http://en.wikipedia.org/wiki/Linear_congruential_generator )

एलसीजी एक निश्चित बीज के बाद काफी अनुमानित हैं। असल में, एक बीज का उपयोग करें जो आपको अपना पहला अक्षर देता है, फिर एक ऐप लिखें जो अगली int (char) उत्पन्न करता है जब तक कि आप अपनी लक्ष्य स्ट्रिंग में अगला अक्षर नहीं दबाते और लिखते हैं कि आपको एलसीजी कितनी बार आमंत्रित करना था। तब तक जारी रखें जब तक आप प्रत्येक अक्षर उत्पन्न नहीं कर लेते।


यादृच्छिक हमेशा एक ही अनुक्रम लौटते हैं। इसका उपयोग क्रमिकरण के रूप में सरणी और अन्य परिचालनों को घुमाने के लिए किया जाता है।

विभिन्न अनुक्रम प्राप्त करने के लिए, "बीज" नामक कुछ स्थिति में अनुक्रम प्रारंभ करना आवश्यक है।

यादृच्छिक सेटिंग को "यादृच्छिक" क्रम के i स्थिति (बीज = -229985452) में यादृच्छिक संख्या मिलती है। फिर बीज स्थिति के बाद अनुक्रम में अगले 27 वर्ण के लिए ASCII कोड का उपयोग करता है जब तक कि यह मान 0 के बराबर न हो। यह "हैलो" लौटाता है। "दुनिया" के लिए एक ही ऑपरेशन किया जाता है।

मुझे लगता है कि कोड किसी अन्य शब्द के लिए काम नहीं करता था। वह व्यक्ति जो प्रोग्राम किया गया है जो यादृच्छिक अनुक्रम को बहुत अच्छी तरह से जानता है।

यह बहुत अच्छा गीक कोड है!


प्रिंसिपल एक ही बीज के साथ निर्मित रैंडम क्लास हर बार संख्याओं का एक ही पैटर्न उत्पन्न करेगा।


यह "बीज" के बारे में है। वही बीज एक ही परिणाम देते हैं।


यहां हर किसी ने यह बताने का एक अच्छा काम किया है कि कोड कैसे काम करता है और दिखाता है कि आप अपने उदाहरण कैसे बना सकते हैं, लेकिन यहां एक सूचना सैद्धांतिक उत्तर दिखा रहा है कि क्यों हम उचित रूप से समाधान की उम्मीद कर सकते हैं कि ब्रूट फोर्स सर्च अंततः मिल जाएगी।

26 अलग-अलग निचले केस अक्षर हमारे वर्णमाला Σ बनाते हैं। विभिन्न लंबाई के शब्दों को उत्पन्न करने की अनुमति देने के लिए, हम विस्तारित वर्णमाला Σ' := Σ ∪ {⊥} उत्पन्न करने के लिए एक टर्मिनेटर प्रतीक Σ' := Σ ∪ {⊥}

α को एक प्रतीक बनें और एक्स को Σ' पर समान रूप से वितरित यादृच्छिक चर दें। उस प्रतीक को प्राप्त करने की संभावना, P(X = α) , और इसकी सूचना सामग्री, I(α) , इनके द्वारा दी गई हैं:

पी (एक्स = α) = 1 / | Σ '| = 1/27

मैं (α) = -log₂ [पी (एक्स = α)] = -log₂ (1/27) = log₂ (27)

एक शब्द ω ∈ Σ* और इसके ⊥- समाप्त समकक्ष ω' := ω · ⊥ ∈ (Σ')* , हमारे पास है

मैं (ω): = मैं (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * log₂ (27)

चूंकि छद्म यादृच्छिक संख्या जेनरेटर (पीआरएनजी) 32-बिट बीज के साथ शुरू किया गया है, इसलिए हम लंबाई के अधिकांश शब्दों की अपेक्षा कर सकते हैं

λ = मंजिल [32 / log₂ (27)] - 1 = 5

कम से कम एक बीज द्वारा उत्पन्न किया जाना है। भले ही हम 6-वर्ण वाले शब्द की खोज कर रहे हों, फिर भी हम उस समय के 41.06% के बारे में सफल होंगे। जर्जर भी नहीं।

7 अक्षरों के लिए हम 1.52% के करीब देख रहे हैं, लेकिन मुझे एहसास नहीं हुआ कि इसे आज़माने से पहले:

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

आउटपुट देखें: http://ideone.com/JRGb3l


मैं इससे चिंतित था, मैंने एक शब्दकोष शब्द सूची पर इस यादृच्छिक शब्द जनरेटर को चलाया। रेंज: Integer.MIN_VALUE को Integer.MAX_VALUE में

मुझे 15131 हिट मिलीं।

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

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

प्रिंटों

the quick browny fox jumps over a lazy dog 

डेनिस तुलस्की के answer लिए यहां मामूली सुधार है। यह समय आधे से कटौती करता है

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 :/");
}

मैंने इन बीजों को खोजने के लिए एक त्वरित कार्यक्रम लिखा:

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

मेरे पास अब पृष्ठभूमि में चल रहा है, लेकिन क्लासिक पंग्राम के लिए यह पहले से ही पर्याप्त शब्द पाए गए हैं:

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

( विचारधारा पर डेमो। )

Ps। -727295876, -128911, -1611659, -235516779


जब java.util.Random का एक उदाहरण एक विशिष्ट बीज पैरामीटर (इस मामले में -229985452 या -147909649 9 -147909649 9 -147909649 9) के साथ बनाया गया है, तो यह उस बीज मान से शुरू होने वाली यादृच्छिक संख्या पीढ़ी एल्गोरिदम का पालन करता है।

एक ही बीज के साथ निर्मित प्रत्येक Random हर बार संख्याओं के समान पैटर्न उत्पन्न करेगा।





random