Câu hỏi Tại sao mã này sử dụng chuỗi ngẫu nhiên in “hello world”?


Bản in sau sẽ in "hello world". Bất cứ ai có thể giải thích điều này?

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

randomString() trông như thế này:

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


gốc


Vâng, những hạt giống đặc biệt như vậy xảy ra để làm việc hoàn hảo. Ngẫu nhiên không thực sự ngẫu nhiên, nó là giả ngẫu nhiên. - Doorknob
Nó hoạt động, như những người khác đã nói, bởi vì ngẫu nhiên là không. Đối với tôi, một câu hỏi thú vị hơn sẽ là người đã viết điều đó, bạo lực, hay có cách dễ dàng để dự đoán ngẫu nhiên nào sẽ tạo ra cho các giá trị N tiếp theo cho một hạt giống đã cho. Brute buộc là dễ dàng và với phần cứng hiện đại không nên mất quá lâu, do đó, đó là ceertain một cách khả thi để làm điều đó. Cho rằng nó là tĩnh, bạn thậm chí có thể dễ dàng phân phối tìm kiếm trên mạng. - jmoreno
Tôi tự hỏi mục đích của n trong for (int n = 0; ; n++). Họ có thể sử dụng for(;;) hoặc là while(true) thay thế! - Eng.Fouad
Trong một chuỗi ngẫu nhiên thực sự, mọi chuỗi có thể sẽ xuất hiện. Trong một chuỗi giả ngẫu nhiên chất lượng cao có thể mong đợi mọi chuỗi có thể có chiều dài (log_s (N) - n) bit (trong đó N là số bit trong trạng thái nội bộ PRNG và n là một số nhỏ, hãy chọn 8 để thuận tiện ) xuất hiện trong chu kỳ. Mã này nhận được một số trợ giúp từ việc sử dụng điểm bắt đầu được mã hóa tự do được lựa chọn (giá trị của dấu gạch chéo nhân vật), điều này sẽ trả lại gần 8 bit. - dmckee
người chiến thắng của cách kỳ lạ nhất để in "hello world" - osdamv


Các câu trả lời:


Khi một thể hiện của java.util.Random được xây dựng với một tham số hạt giống cụ thể (trong trường hợp này -229985452 hoặc là -147909649), nó theo thuật toán tạo số ngẫu nhiên bắt đầu với giá trị hạt giống đó.

Mỗi Random được xây dựng với cùng một hạt giống sẽ tạo ra cùng một mẫu số mỗi lần.


846
2018-03-03 04:40



@Vulcan - javadoc nói rằng hạt giống là 48 bit. docs.oracle.com/javase/7/docs/api/java/util/Random.html. Và bên cạnh đó, các hạt giống thực tế là các giá trị 32 bit. - Stephen C
Mỗi phần tử của chuỗi số ngẫu nhiên được lấy modulo 27 và có 6 phần tử trong mỗi "hello\0" và "world\0". Nếu bạn giả định một máy phát ngẫu nhiên thực sự, tỷ lệ cược sẽ là 1 trong 27 ^ 6 (387,420,489) nhận được chuỗi bạn đang tìm kiếm - vì vậy nó khá ấn tượng nhưng không hoàn toàn phiền phức! - Russell Borogove
@RussellBorogove: Nhưng với những tỷ lệ cược đó, và 2 ^ 64 hạt giống có thể, có một giá trị hạt giống dự kiến ​​là 47,6 tỷ cho chuỗi đó. Nó chỉ là vấn đề của việc tìm kiếm một. - dan04
@ dan04 - Tôi đã không hoàn toàn sẵn sàng để thực hiện ước tính đó; tùy thuộc vào việc thực hiện PRNG, kích thước của từ hạt giống có thể không bằng kích thước của tiểu bang và các đường dẫn trình tự có thể không được phân bố đồng đều. Nhưng vẫn còn, tỷ lệ cược chắc chắn là tốt, và nếu bạn không thể tìm thấy một cặp bạn có thể thử lại với vỏ khác nhau ("Hello"  "World"), hoặc sử dụng 122-k thay vì 96+k, hoặc là... - Russell Borogove
@ ThorbjørnRavnAndersen Javadoc xác định rằng "các thuật toán cụ thể được chỉ định cho lớp Random. Java triển khai phải sử dụng tất cả các thuật toán được hiển thị ở đây cho lớp Random, vì lợi ích của tính di động tuyệt đối của mã Java." - Vulcan


Các câu trả lời khác giải thích tại sao, nhưng đây là cách thức.

Cho một trường hợp Random:

Random r = new Random(-229985452)

6 số đầu tiên r.nextInt(27) tạo ra là:

8
5
12
12
15
0

và 6 số đầu tiên r.nextInt(27) tạo ra Random r = new Random(-147909649) là:

23
15
18
12
4
0

Sau đó, chỉ cần thêm các số đó vào biểu diễn số nguyên của ký tự ` (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



Về mặt đạo đức, new Random(-229985452).nextInt(27) luôn trả về 8. - immibis
@immibis tại sao? tôi có nghĩa là ngẫu nhiên () nên trả lại số ngẫu nhiên mỗi lần, không phải là một số đặt hàng sửa chữa đặt? - roottraveller
@rootTraveller Để bắt đầu, new Random() không trả về một con số nào cả. - immibis
@immibis 4 năm và một tháng trễ, nhưng cố định cho ya. ; D - jpmc26


Tôi sẽ để nó ở đây. Bất cứ ai có rất nhiều (CPU) thời gian rảnh rỗi, cảm thấy tự do để thử nghiệm :) Ngoài ra, nếu bạn đã làm chủ một số ngã ba-join-fu để làm điều này ghi tất cả các lõi CPU (chỉ là chủ đề nhàm chán, phải không?), Xin vui lòng chia sẻ ma cua ban. Tôi sẽ đánh giá cao về nó.

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

Đầu ra:

-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



@Một hai ba nextInt(27) có nghĩa là trong phạm vi [0, 26]. - Eng.Fouad
@Vulcan Hầu hết các hạt giống rất gần với giá trị tối đa, giống như nếu bạn chọn số ngẫu nhiên từ 1 đến 1000, hầu hết các số bạn chọn sẽ có ba chữ số. Nó không đáng ngạc nhiên, khi bạn nghĩ về nó :) - Thomas
@Vulcan Trong thực tế, nếu bạn làm toán, bạn sẽ thấy chúng gần bằng giá trị tối đa bằng không (tôi cho rằng hạt giống đang được hiểu là không dấu trong mã thế hệ). Nhưng vì số lượng chữ số chỉ phát triển lôgarit với giá trị thực tế, con số trông thực sự gần gũi khi nó thực sự không phải là. - Thomas
Một quy tắc thú vị và có liên quan là Luật của Benford, nói rằng trong nhiều nguồn dữ liệu tự nhiên, số đầu "1" và "2" xuất hiện thường xuyên hơn nhiều, vì lý do tương tự: đi từ 9 đến 10 có hệ số nhỏ hơn nhiều so với từ 10 đến 20. Trong trường hợp này, đi từ 0 đến int.max/10 mất ít hơn nhiều so với để đi từ int.max/10 đến int.max. - FeepingCreature
@ Marek: Tôi không nghĩ rằng các vị thần giả ngẫu nhiên sẽ chấp nhận hành vi như vậy. - Denis Tulskiy


Mọi người ở đây đã làm một công việc tuyệt vời để giải thích cách mã hoạt động và cho thấy cách bạn có thể xây dựng ví dụ của riêng mình, nhưng đây là câu trả lời lý thuyết thông tin cho thấy lý do tại sao chúng ta có thể mong đợi một giải pháp tồn tại mà tìm kiếm bạo lực cuối cùng sẽ tìm thấy.

26 chữ cái viết hoa khác nhau tạo thành bảng chữ cái của chúng tôi Σ. Để cho phép tạo các từ có độ dài khác nhau, chúng tôi tiếp tục thêm biểu tượng trình kết thúc  để mang lại một bảng chữ cái mở rộng Σ' := Σ ∪ {⊥}.

Để cho α là một biểu tượng và X là biến ngẫu nhiên được phân bố đều Σ'. Xác suất có được biểu tượng đó, P(X = α)và nội dung thông tin của nó, I(α), được đưa ra bởi:

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

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

Đối với một từ ω ∈ Σ* và nó ⊥-kết thúc đối tác ω' := ω · ⊥ ∈ (Σ')*, chúng ta có

I (ω): = I (ω ') = | ω' | * log₂ (27) = (| ω | + 1) * nhật ký (27)

Vì Trình tạo số giả ngẫu nhiên (PRNG) được khởi tạo với một hạt giống 32 bit, chúng ta có thể mong đợi hầu hết các từ có độ dài lên đến

λ = sàn [32 / log₂ (27)] - 1 = 5

được tạo ra bởi ít nhất một hạt giống. Ngay cả khi chúng tôi tìm kiếm từ có 6 ký tự, chúng tôi vẫn sẽ thành công khoảng 41,06% thời gian. Không quá xấu.

Đối với 7 chữ cái chúng tôi đang xem xét đến gần 1,52%, nhưng tôi đã không nhận ra rằng trước khi cho nó một thử:

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

Xem đầu ra: http://ideone.com/JRGb3l


248
2018-03-04 09:49



lý thuyết thông tin của tôi yếu đuối nhưng tôi thích bằng chứng này. ai đó có thể giải thích dòng lambda với tôi, rõ ràng chúng tôi đang chia nội dung thông tin của một với người khác, nhưng tại sao điều này lại cho chúng ta độ dài từ? như tôi đã nói, tôi rất tiếc vì vậy xin lỗi vì đã hỏi rõ ràng (N.B. là một điều gì đó liên quan đến giới hạn shannon-từ đầu ra mã) - Mike H-R
@ MikeH-R Dòng lambda là I(⍵) phương trình được sắp xếp lại.I(⍵) là 32 (bit) và |⍵| hóa ra là 5 (biểu tượng). - iceman


Tôi đã viết một chương trình nhanh để tìm những hạt giống này:

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

Tôi có nó chạy trong nền bây giờ, nhưng nó đã tìm thấy đủ từ cho một hình ảnh cổ điển:

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 trên ideone.)

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


65
2018-03-03 18:33



class R{ public static void main(String[] a) { System.out.println("-229985452, -147909649"); } thực hiện công việc đó. - djechlin


Tôi đã bị hấp dẫn bởi điều này, tôi chạy trình tạo từ ngẫu nhiên này trên một danh sách từ điển. Phạm vi: Integer.MIN_VALUE thành Integer.MAX_VALUE

Tôi có 15131 lượt truy cập.

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

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

Bản in

the quick browny fox jumps over a lazy dog 

31
2018-04-13 22:47



Bạn đã làm cho người đàn ông ngày của tôi: DI đã thử nó với Long.Min / Max và tìm kiếm tên của các đồng nghiệp của tôi và chỉ tìm thấy peter: (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


Hầu hết các trình tạo số ngẫu nhiên, trên thực tế, "giả ngẫu nhiên". Chúng là các máy phát điện tuyến tính, hoặc LCG (http://en.wikipedia.org/wiki/Linear_congruential_generator)

LCG khá khả thi với một hạt giống cố định. Về cơ bản, sử dụng một hạt giống cung cấp cho bạn chữ cái đầu tiên của bạn, sau đó viết một ứng dụng tiếp tục tạo int (char) tiếp theo cho đến khi bạn nhấn chữ cái tiếp theo trong chuỗi mục tiêu và ghi lại số lần bạn phải gọi LCG. Tiếp tục cho đến khi bạn đã tạo từng chữ cái.


26
2018-03-04 10:59



whats một ví dụ về một máy phát số ngẫu nhiên không giả - chiliNUT
@chiliNUT Máy phát điện như vậy là các tiện ích bên ngoài. Một số đèn điện tử. Hoặc bit viết xấu được đọc 0 hoặc 1. Bạn không thể làm máy phát điện số thuần túy của các số ngẫu nhiên, các thuật toán kỹ thuật số KHÔNG phải là ngẫu nhiên, chúng hoàn toàn chính xác. - Gangnus
@chiliNUT Nhiều hệ điều hành thu thập entropy. Ví dụ. trong Linux, bạn có thể sử dụng /dev/urandom thiết bị để đọc dữ liệu ngẫu nhiên. Đây là một nguồn tài nguyên khan hiếm, tuy nhiên. Vì vậy, dữ liệu ngẫu nhiên như vậy thường được sử dụng để tạo hạt giống PRNG. - Adrian W
@AdrianW Wikipedia nói urandom vẫn giả ngẫu nhiên en.wikipedia.org/wiki//dev/random - chiliNUT
Có, nhưng nó là an toàn mã hóa, có nghĩa là người ta không thể thực hiện các cuộc tấn công bạo lực (như tìm hạt giống cho chuỗi "ngẫu nhiên" "hello world") với các chuỗi ngẫu nhiên được tạo từ /dev/random. Bài viết tôi trích dẫn ở trên nói Nhân Linux tạo ra entropy từ các timings của bàn phím, các chuyển động của chuột và thời gian IDE và làm cho dữ liệu ký tự ngẫu nhiên có sẵn cho các tiến trình hệ điều hành khác thông qua các tệp đặc biệt / dev / random và / dev / urandom. Điều đó cho phép tôi tin rằng nó thực sự là ngẫu nhiên. Có thể điều đó không hoàn toàn chính xác. Nhưng /dev/random ít nhất chứa đựng một số entropy. - Adrian W


Ngẫu nhiên luôn luôn trả về cùng một chuỗi. Nó được sử dụng để xáo trộn mảng và các hoạt động khác như hoán vị.

Để có được trình tự khác nhau, nó cần thiết khởi tạo trình tự ở một số vị trí, được gọi là "hạt giống".

RandomSting lấy số ngẫu nhiên ở vị trí i (seed = -229985452) của chuỗi "ngẫu nhiên". Sau đó, sử dụng ASCII mã cho ký tự 27 tiếp theo trong chuỗi sau vị trí hạt giống cho đến khi giá trị này bằng 0. Điều này trả về "hello". Các hoạt động tương tự được thực hiện cho "thế giới".

Tôi nghĩ rằng mã không hoạt động cho bất kỳ từ nào khác. Anh chàng lập trình biết rằng trình tự ngẫu nhiên rất tốt.

Đó là mã geek rất tuyệt vời!


22
2018-03-03 04:54



Tôi nghi ngờ nếu anh ta "biết chuỗi ngẫu nhiên rất tốt". Nhiều khả năng, anh ta đã thử hàng tỷ hạt giống có thể cho đến khi tìm được một hạt giống có hiệu quả. - dan04
@ dan04 Các lập trình viên thực sự không chỉ sử dụng PRNG, họ còn nhớ toàn bộ thời gian bằng trái tim và liệt kê các giá trị khi cần thiết. - Thomas
"Ngẫu nhiên luôn trả về cùng một chuỗi" - put () sau Ngẫu nhiên hoặc hiển thị nó dưới dạng mã. Ngoài ra câu là sai. - Gangnus