Bagaimana saya harus menguji keacakan?

Pertimbangkan metode untuk mengacak elemen secara acak dalam array. Bagaimana Anda menulis unit test yang sederhana namun kuat untuk memastikan bahwa ini berhasil?

Saya telah datang dengan dua ide, yang keduanya memiliki kelemahan nyata:

• Kocok array, lalu pastikan urutannya berbeda dari sebelumnya. Ini kedengarannya bagus, tetapi gagal jika shuffle terjadi secara acak dalam urutan yang sama. (Tidak mungkin, tetapi mungkin.)
• Kocok array dengan seed konstan, dan periksa terhadap output yang telah ditentukan. Ini bergantung pada fungsi acak yang selalu mengembalikan nilai yang sama dengan seed yang sama. Namun, ini terkadang merupakan asumsi yang tidak valid .

Pertimbangkan fungsi kedua yang mensimulasikan gulungan dadu dan mengembalikan angka acak. Bagaimana Anda menguji fungsi ini? Bagaimana Anda menguji bahwa fungsi ...

• tidak pernah mengembalikan nomor di luar batas yang diberikan?
• mengembalikan angka dalam distribusi yang valid? (Seragam untuk satu mati, normal untuk sejumlah besar dadu.)

Saya mencari jawaban yang menawarkan wawasan pengujian tidak hanya contoh-contoh ini tetapi elemen kode acak secara umum. Apakah tes unit bahkan solusi yang tepat di sini? Jika tidak, tes seperti apa itu?

Hanya untuk menenangkan pikiran semua orang, saya tidak menulis generator nomor acak saya sendiri.

Saya tidak berpikir unit test adalah alat yang tepat untuk menguji keacakan. Tes unit harus memanggil metode dan menguji nilai yang dikembalikan (atau keadaan objek) terhadap nilai yang diharapkan. Masalah dengan pengujian keacakan adalah bahwa tidak ada nilai yang diharapkan untuk sebagian besar hal yang ingin Anda uji. Anda dapat menguji dengan seed yang diberikan, tetapi itu hanya menguji pengulangan . Itu tidak memberi Anda cara untuk mengukur seberapa acak distribusi itu, atau apakah itu bahkan acak sama sekali.

Untungnya, ada banyak tes statistik yang dapat Anda jalankan, seperti Diehard Battery of Tests of Randomness . Lihat juga:

1. Bagaimana cara menguji generator nomor acak semu?

   • Steve Jessop merekomendasikan agar Anda menemukan implementasi teruji dari algoritma RNG yang sama yang Anda gunakan dan membandingkan hasilnya dengan biji yang dipilih terhadap implementasi Anda sendiri.
   • Greg Hewgill merekomendasikan rangkaian uji statistik THT .
   • John D. Cook merujuk pembaca ke artikel CodeProject-nya, Simple Random Number Generation , yang mencakup implementasi uji Kolmogorov-Smirnov yang disebutkan dalam Donald Knuth's volume 2, Algoritma Seminumerik.
   • Beberapa orang merekomendasikan pengujian bahwa distribusi angka yang dihasilkan adalah seragam, uji Chi-squared, dan pengujian bahwa mean dan standar deviasi berada dalam kisaran yang diharapkan. (Perhatikan bahwa pengujian distribusi saja tidak cukup. [1,2,3,4,5,6,7,8] adalah distribusi yang seragam, tetapi tentu saja tidak acak.)

2. Unit Testing dengan fungsi yang mengembalikan hasil acak

   • Brian Genisio menunjukkan bahwa mengejek RNG Anda adalah salah satu opsi untuk membuat tes Anda berulang, dan memberikan kode sampel C #.
   • Sekali lagi, beberapa orang menunjuk penggunaan nilai benih tetap untuk pengulangan dan tes sederhana untuk distribusi yang seragam, kuadrat-kuadrat, dll.

3. Unit Testing Randomness adalah artikel wiki yang membahas tentang banyak tantangan yang telah disentuh ketika mencoba menguji apa yang, menurut sifatnya, tidak dapat diulang. Satu hal menarik yang saya dapat dari sana adalah sebagai berikut:

   Saya telah melihat winzip digunakan sebagai alat untuk mengukur keacakan file nilai sebelumnya (jelas, semakin kecil dapat mengkompres file semakin sedikit acak itu).

1. Unit uji algoritma Anda

Untuk pertanyaan pertama saya akan membangun kelas palsu yang Anda beri makan urutan angka acak yang Anda tahu hasil dari algoritma Anda. Dengan begitu Anda memastikan algoritma yang Anda bangun di atas fungsi acak Anda berfungsi. Jadi sesuatu seperti:

Random r = new RandomStub([1,3,5,3,1,2]);
r.random(); //returns 1
r.random(); //returns 3
...

2. Lihat apakah fungsi acak Anda masuk akal

Untuk tes unit Anda harus menambahkan tes yang berjalan beberapa kali dan menyatakan hasilnya

• berada dalam batas yang Anda tetapkan (jadi, dadu roll berada di antara 1 dan 6) dan
• menunjukkan distribusi yang masuk akal (lakukan beberapa tes berjalan dan lihat apakah distribusi berada dalam x% dari yang Anda harapkan, misalnya untuk dadu roll Anda akan melihat 2muncul antara 10% dan 20% (1/6 = 16,67%) dari waktu mengingat Anda menggulirkannya 1000 kali).

3. Tes integrasi untuk algoritma dan fungsi acak

Seberapa sering Anda berharap array Anda diurutkan dalam penyortiran asli? Sortir beberapa ratus kali dan nyatakan bahwa hanya x% dari waktu penyortiran tidak berubah.

Ini sebenarnya sudah merupakan tes integrasi, Anda menguji algoritma bersama dengan fungsi acak. Setelah Anda menggunakan fungsi acak nyata, Anda tidak bisa lagi berjalan dengan tes tunggal.

Dari pengalaman (saya menulis algoritma genetika) saya akan mengatakan menggabungkan tes unit algoritma Anda, tes distribusi fungsi acak Anda dan tes integrasi adalah cara untuk pergi.

Aspek PRNG yang tampaknya dilupakan adalah bahwa semua propertinya bersifat statistik: Anda tidak dapat berharap bahwa pengocokan array akan menghasilkan permutasi yang berbeda dari permulaan yang Anda mulai. Pada dasarnya, jika Anda menggunakan PRNG normal, satu-satunya hal yang Anda jamin adalah bahwa ia tidak menggunakan pola sederhana (mudah-mudahan) dan bahwa ia bahkan memiliki distribusi di antara set angka yang dikembalikan.

Tes yang tepat untuk PRNG akan melibatkan menjalankannya setidaknya 100 kali dan kemudian memeriksa distribusi output (yang merupakan jawaban langsung untuk bagian kedua dari pertanyaan).

Jawaban untuk pertanyaan pertama hampir sama: jalankan tes sekitar 100 kali dengan {1, 2, ..., n} dan hitung berapa kali setiap elemen berada di setiap posisi. Semuanya harus sama kasarnya jika metode shuffle bagus.

Hal yang sama sekali berbeda adalah bagaimana menguji PRNGs kriptografi. Ini adalah masalah di mana Anda mungkin tidak boleh tinggal, kecuali Anda benar-benar tahu apa yang Anda lakukan. Orang-orang diketahui menghancurkan (baca: membuka lubang bencana di) cryptosystems yang baik hanya dengan beberapa 'optimasi' atau pengeditan sepele.

EDIT: Saya sudah membaca ulang pertanyaan, jawaban teratas dan saya sendiri. Sementara poin yang saya buat masih bertahan, saya akan meminta jawaban Bill The Lizard. Tes unit bersifat Boolean - mereka gagal, atau berhasil, dan karenanya tidak cocok untuk menguji "seberapa baik" sifat-sifat PRNG (atau metode menggunakan PRNG), karena jawaban apa pun untuk pertanyaan ini akan bersifat kuantitatif , bukannya kutub.

Ada dua bagian untuk ini: menguji pengacakan dan menguji hal-hal yang menggunakan pengacakan.

Pengujian pengacakan relatif mudah. Anda memeriksa bahwa periode generator angka acak adalah seperti yang Anda harapkan (untuk beberapa sampel menggunakan beberapa benih agak acak, dalam beberapa ambang batas) dan bahwa distribusi output di atas ukuran sampel besar adalah seperti yang Anda harapkan itu menjadi (dalam batas tertentu).

Menguji hal-hal yang menggunakan pengacakan terbaik dilakukan dengan generator angka psuedo-acak deterministik. Karena output dari pengacakan diketahui berdasarkan pada seed (inputnya), maka Anda dapat menguji unit secara normal berdasarkan input vs output yang diharapkan. Jika RNG Anda tidak deterministik, mengejeknya dengan yang deterministik (atau tidak acak). Uji pengacakan secara terpisah dari kode yang mengkonsumsinya.

Biarkan berjalan beberapa kali dan visualisasikan data Anda .

Berikut ini contoh shuffle dari Coding Horror , Anda dapat melihat bahwa algoritmenya OK atau tidak:

Sangat mudah untuk melihat bahwa setiap item yang mungkin dikembalikan setidaknya satu kali (batasnya OK) dan distribusinya OK.

Pointer umum yang saya temukan berguna ketika berhadapan dengan kode yang mengambil input acak: Periksa kasus tepi dari keacakan yang diharapkan (nilai max dan min, dan nilai max + 1 dan min-1 jika berlaku). Periksa tempat (pada, di atas, dan di bawah) di mana angka memiliki titik belok (yaitu -1, 0, 1, atau lebih besar dari 1, kurang dari 1 dan non-negatif untuk kasus di mana nilai fraksional dapat mengacaukan fungsi). Periksa beberapa tempat sepenuhnya di luar input yang diizinkan. Periksa beberapa kasus khas. Anda juga dapat menambahkan input acak, tetapi untuk tes unit yang memiliki efek samping yang tidak diinginkan bahwa nilai yang sama tidak diuji setiap kali tes dijalankan (pendekatan seed dapat bekerja, tes 1.000 angka acak pertama dari seed S atau semacamnya).

Untuk menguji keluaran fungsi acak, penting untuk mengidentifikasi tujuan. Dalam hal kartu, apakah tujuan untuk menguji keseragaman generator acak 0-1, untuk menentukan apakah semua 52 kartu muncul dalam hasil, atau beberapa tujuan lain (mungkin semua daftar ini dan banyak lagi)?

Dalam contoh spesifik, Anda harus mengasumsikan generator angka acak Anda buram (sama seperti itu tidak masuk akal untuk menguji unit syscall OS atau malloc- kecuali Anda menulis OS). Mungkin berguna untuk mengukur generator angka acak, tetapi tujuan Anda bukan untuk menulis generator acak, hanya untuk memastikan bahwa Anda mendapatkan 52 kartu setiap kali, dan bahwa mereka mengubah urutan.

Itu adalah cara yang panjang untuk mengatakan bahwa sebenarnya ada dua tugas pengujian di sini: menguji bahwa RNG menghasilkan distribusi yang tepat, dan memeriksa bahwa kode pengocokan kartu Anda menggunakan RNG untuk menghasilkan hasil acak. Jika Anda menulis RNG, gunakan analisis statistik untuk membuktikan distribusi Anda, jika Anda menulis pengocok kartu, pastikan ada 52 kartu yang tidak diulang di setiap output (ini adalah kasus yang lebih baik untuk pengujian dengan inspeksi yang Anda gunakan RNG).

Anda dapat mengandalkan generator nomor acak yang aman

Saya baru saja memiliki pemikiran yang mengerikan: Anda tidak menulis generator nomor acak Anda sendiri, bukan?

Dengan asumsi Anda tidak, maka Anda harus menguji kode yang menjadi tanggung jawab Anda , bukan kode orang lain (seperti SecureRandomimplementasi kerangka kerja Anda).

Menguji kode Anda

Untuk menguji bahwa kode Anda merespons dengan benar, adalah normal untuk menggunakan metode visibilitas rendah untuk menghasilkan angka acak sehingga dapat dengan mudah diganti oleh kelas uji unit. Metode yang diganti ini secara efektif mengejek generator angka acak dan memberi Anda kontrol penuh atas apa yang diproduksi dan kapan. Karenanya, Anda dapat sepenuhnya menjalankan kode yang merupakan tujuan pengujian unit.

Jelas Anda akan memeriksa kondisi tepi dan memastikan bahwa pengocokan berlangsung tepat seperti yang ditentukan oleh algoritma Anda dengan input yang sesuai.

Menguji generator nomor acak aman

Jika Anda tidak yakin bahwa penghasil angka acak yang aman untuk bahasa Anda tidak benar-benar acak atau buggy (memberikan nilai di luar kisaran dll), maka Anda perlu melakukan analisis statistik terperinci dari output selama beberapa ratus juta iterasi. Plot frekuensi kemunculan setiap angka dan itu harus muncul dengan probabilitas yang sama. Jika hasilnya condong ke satu arah atau lain cara Anda harus melaporkan temuan Anda ke desainer kerangka. Mereka pasti akan tertarik untuk memperbaiki masalah karena generator nomor acak aman adalah dasar bagi banyak algoritma enkripsi.

Ya, Anda tidak akan pernah 100% pasti, jadi yang terbaik yang dapat Anda lakukan adalah kemungkinan jumlahnya acak. Pilih probabilitas - katakan bahwa sampel angka atau item akan muncul x kali diberikan satu juta sampel, dalam margin kesalahan. Jalankan benda itu jutaan kali, dan lihat apakah itu ada dalam margin. Untungnya, komputer membuat hal semacam ini mudah dilakukan.

Untuk menguji bahwa sumber nomor acak adalah menghasilkan sesuatu yang setidaknya memiliki penampilan keacakan, saya akan memiliki tes menghasilkan urutan yang cukup besar dari byte, menulis mereka ke file sementara, dan kemudian keluar ke Fourmilab ini ent alat. Berikan sakelar -t (terse) sehingga akan menghasilkan CSV yang mudah diurai. Kemudian periksa berbagai nomor untuk melihat bahwa mereka "baik."

Untuk memutuskan angka mana yang baik, gunakan sumber acak yang dikenal untuk mengkalibrasi tes Anda. Tes harus hampir selalu lulus ketika diberikan satu set angka acak yang baik. Karena bahkan urutan yang benar-benar acak pun memiliki kemungkinan menghasilkan urutan yang tampaknya non-acak, Anda tidak bisa mendapatkan tes yang pasti akan lulus. Anda cukup memilih ambang yang membuatnya tidak mungkin bahwa urutan acak akan menyebabkan kegagalan pengujian. Bukankah keacakan itu menyenangkan?

Catatan: Anda tidak dapat menulis tes yang menunjukkan bahwa PRNG menghasilkan urutan "acak". Anda hanya dapat menulis tes yang, jika lulus, menunjukkan beberapa probabilitas bahwa urutan yang dihasilkan oleh PRNG adalah "acak." Selamat datang di kegembiraan keacakan!

Kasus 1: Menguji shuffle:

Pertimbangkan Array [0, 1, 2, 3, 4, 5], kocok, apa yang salah? Hal-hal yang biasa: a) tidak ada pengocokan sama sekali, b) pengocokan 1-5 tetapi tidak 0, pengocokan 0-4 tetapi tidak 5, pengocokan, dan selalu menghasilkan pola yang sama, ...

Satu tes untuk menangkap semuanya:

Kocok 100 kali, tambahkan nilai di setiap slot. Jumlah setiap slot harus sama dengan masing-masing slot lainnya. Rata-rata / Stddev dapat dihitung. (5 + 0) /2=2.5, 100 * 2.5 = 25. Nilai yang diharapkan sekitar 25, misalnya.

Jika nilainya di luar kisaran, ada kemungkinan kecil, bahwa Anda mendapat negatif palsu. Anda bisa menghitung, seberapa besar peluang itu. Ulangi tes ini. Ya - tentu saja ada kemungkinan kecil, bahwa tes gagal 2 kali berturut-turut. Tetapi Anda tidak memiliki rutinitas yang secara otomatis menghapus sumber Anda, jika unit-test gagal, bukan? Jalankan lagi!

Itu bisa gagal 3 kali berturut-turut? Mungkin Anda harus mencoba keberuntungan Anda di lotere.

Kasus 2: Gulung dadu

Pertanyaan dadu-roll adalah pertanyaan yang sama. Lempar dadu 6000 kali.

for (i in 0 to 6000) 
    ++slot [Random.nextInt (6)];
return (slot.max - slot.min) < threshold;