Mục Java hiệu quả 47: Biết và sử dụng thư viện của bạn - Ví dụ về phương pháp số nguyên ngẫu nhiên

Question

Trong ví dụ Josh đưa ra phương thức ngẫu nhiên sai lệch tạo ra số ngẫu nhiên dương với giới hạn trên cho trước n, tôi không hiểu hai những sai sót mà anh nói.

Phương pháp từ cuốn sách là:

private static final Random rnd = new Random(); 

//Common but deeply flawed 
static int random(int n) { 
    return Math.abs(rnd.nextInt()) % n; 
} 

• Ông nói rằng nếu n là một điện nhỏ của 2, chuỗi các số ngẫu nhiên được tạo ra sẽ lặp lại bản thân sau một thời gian ngắn. Tại sao điều này là trường hợp? Các tài liệu cho Random.nextInt() nói Returns the next pseudorandom, uniformly distributed int value from this random number generator's sequence. Vì vậy, nó không phải là nếu n là một số nguyên nhỏ thì trình tự sẽ lặp lại chính nó, tại sao điều này chỉ áp dụng cho quyền hạn của 2?
• Tiếp theo, ông nói rằng nếu n không phải là công suất của 2, một số con số sẽ được trả về trung bình thường xuyên hơn những số khác. Tại sao điều này xảy ra, nếu Random.nextInt() tạo ra các số nguyên ngẫu nhiên được phân phối đồng đều? (Ông cung cấp một đoạn mã trong đó thể hiện rõ ràng điều này nhưng tôi không hiểu tại sao đây là trường hợp, và làm thế nào điều này liên quan đến n là một sức mạnh của 2).

Answer 1

Câu hỏi 1: nếu n là một điện nhỏ của 2, chuỗi các số ngẫu nhiên được tạo ra sẽ lặp lại bản thân sau một thời gian ngắn.

Đây không phải là một hệ quả của bất cứ điều gì Josh đang nói; thay vào đó, nó chỉ đơn giản là một tài sản được biết đến của linear congruential generators. Wikipedia có những điều sau đây để nói:

Một vấn đề nữa của LCG là các bit bậc thấp của chuỗi được tạo ra có thời gian ngắn hơn so với toàn bộ chuỗi nếu m được đặt thành lũy thừa là 2. Nói chung, chữ số quan trọng nhất thứ n trong biểu diễn b cơ bản của chuỗi đầu ra, trong đó b ^k = m đối với một số nguyên k, lặp lại với nhiều nhất là b ⁿ.

này cũng được ghi nhận trong Javadoc:

tuyến tính congruential máy phát điện số giả ngẫu nhiên như một thực hiện bởi lớp này được biết là có một thời gian ngắn trong chuỗi các giá trị của họ thấp bit đặt hàng.

Phiên bản khác của hàm, Random.nextInt(int), công trình này bằng cách sử dụng bit khác nhau trong trường hợp này (tôi nhấn mạnh):

Các thuật toán xử lý các trường hợp trong đó n là một sức mạnh của hai đặc biệt: nó trả về số chính xác của thứ tự cao bit từ trình tạo số giả ngẫu nhiên cơ bản.

Đây là lý do chính đáng để thích Random.nextInt(int) qua việc sử dụng Random.nextInt() và thực hiện chuyển đổi phạm vi của riêng bạn.

Câu hỏi 2: Tiếp theo, ông nói rằng nếu n không phải là một sức mạnh của 2, một số con số sẽ được trả trung bình thường xuyên hơn những người khác.

Có 2 các số riêng biệt có thể được trả lại bằng nextInt(). Nếu bạn cố gắng đặt chúng vào n nhóm bằng cách sử dụng % n và n không phải là sức mạnh của 2, một số nhóm sẽ có nhiều số hơn các nhóm khác. Điều này có nghĩa là một số kết quả sẽ xảy ra thường xuyên hơn các kết quả khác mặc dù phân phối ban đầu là thống nhất.

Hãy xem xét điều này bằng cách sử dụng các số nhỏ. Hãy nói rằng nextInt() trở bốn kết quả equiprobable, 0, 1, 2 và 3. Chúng ta hãy xem những gì sẽ xảy ra nếu chúng ta áp dụng % 3 với họ:

0 maps to 0 
1 maps to 1 
2 maps to 2 
3 maps to 0 

Như bạn có thể thấy, các thuật toán sẽ trở về 0 gấp đôi thường xuyên vì nó sẽ trả lại mỗi 1 và 2.

Điều này không xảy ra khi n là một lũy thừa của hai, vì một trong hai điện năng có thể chia hết cho nhau. Hãy xem xét n=2:

0 maps to 0 
1 maps to 1 
2 maps to 0 
3 maps to 1 

Ở đây, 0 và 1 xảy ra với cùng tần suất.

Tài nguyên bổ sung

Dưới đây là thêm một số - nếu chỉ tiếp tuyến có liên quan - tài nguyên liên quan đến LCGs:

• kiểm tra quang phổ là kiểm tra thống kê sử dụng để đánh giá chất lượng LCGs. Đọc thêm here và here.
• A collection of classical pseudorandom number generators with linear structures có một số phân tán khá (máy phát điện được sử dụng trong Java được gọi là DRAND48).
• Có một thú vị discussion trên crypto.SE về dự đoán giá trị từ trình tạo của Java.

Answer 2

1) Khi n là công suất 2, rnd % n tương đương với việc chọn một vài bit thấp hơn của bản gốc. Các bit dưới của các số được tạo ra bởi loại máy phát được sử dụng bởi java được biết là "ít ngẫu nhiên" hơn các bit cao hơn. Nó chỉ là tài sản của công thức được sử dụng để tạo ra các con số.

2) Hãy tưởng tượng, rằng giá trị lớn nhất có thể, được trả về bởi random() là 10 và n = 7. Bây giờ, hãy thực hiện n % 7 bản đồ số 7, 8, 9 và 10 thành 0, 1, 2, 3 tương ứng. Do đó, nếu số gốc được phân phối đồng đều, kết quả sẽ bị thiên vị nặng nề đối với các số thấp hơn, bởi vì chúng sẽ xuất hiện hai lần như 4, 5 và 6. Trong trường hợp này, điều này xảy ra bất kể là n là một hai hoặc không, nhưng, nếu thay vì 10 chúng tôi đã chọn, nói, 15 (đó là 2^4-1), thì bất kỳ n, đó là một sức mạnh của hai sẽ dẫn đến một phân phối thống nhất, bởi vì sẽ không có "dư thừa "các số còn lại ở cuối phạm vi gây ra sai lệch, bởi vì tổng số giá trị có thể sẽ chia hết cho số lần có thể có.