Pembuatan bilangan acak di C ++ 11: Bagaimana cara menghasilkan, bagaimana cara kerjanya? [Tutup]

Saya baru-baru ini menemukan cara baru untuk menghasilkan bilangan acak di C ++ 11, tetapi tidak dapat mencerna makalah yang saya baca tentangnya (apa itu mesin , istilah matematika seperti distribusi , "di mana semua bilangan bulat yang dihasilkan kemungkinannya sama ").

Jadi adakah yang bisa menjelaskan

• Apakah mereka?
• apa yang mereka maksud
• bagaimana menghasilkan?
• bagaimana mereka bekerja?
• dll

Anda dapat memanggil semuanya dalam satu FAQ tentang pembuatan nomor acak.

Pertanyaannya terlalu luas untuk jawaban lengkap, tetapi izinkan saya memilih beberapa poin menarik:

Mengapa "sama mungkinnya"

Misalkan Anda memiliki generator angka acak sederhana yang menghasilkan angka 0, 1, ..., 10 masing-masing dengan probabilitas yang sama (anggap ini sebagai klasik rand()). Sekarang Anda menginginkan nomor acak dalam kisaran 0, 1, 2, masing-masing dengan probabilitas yang sama. Reaksi spontan Anda akan mengambil rand() % 3. Tapi tunggu, sisa 0 dan 1 muncul lebih sering daripada sisa 2, jadi ini tidak benar!

Inilah mengapa kita membutuhkan distribusi yang tepat , yang mengambil sumber bilangan bulat acak yang seragam dan mengubahnya menjadi distribusi yang kita inginkan, seperti Uniform[0,2]pada contoh. Sebaiknya serahkan ini ke perpustakaan yang bagus!

Mesin

Jadi, inti dari semua keacakan adalah generator bilangan pseudo-acak yang menghasilkan urutan bilangan yang didistribusikan secara seragam selama interval tertentu, dan yang idealnya memiliki periode yang sangat lama. Penerapan standar rand()sering kali bukanlah yang terbaik, dan karena itu ada baiknya untuk memiliki pilihan. Linear-kongruensial dan twister Mersenne adalah dua pilihan yang baik (LG sebenarnya juga sering digunakan oleh rand()); sekali lagi, sebaiknya biarkan perpustakaan yang menanganinya.

Bagaimana itu bekerja

Mudah: pertama, siapkan mesin dan lakukan seed. Benih sepenuhnya menentukan seluruh urutan nomor "acak", jadi a) gunakan nomor yang berbeda (misalnya diambil dari /dev/urandom) setiap kali, dan b) simpan benih jika Anda ingin membuat ulang urutan pilihan acak.

#include <random>

typedef std::mt19937 MyRNG;  // the Mersenne Twister with a popular choice of parameters
uint32_t seed_val;           // populate somehow

MyRNG rng;                   // e.g. keep one global instance (per thread)

void initialize()
{
  rng.seed(seed_val);
}

Sekarang kita dapat membuat distribusi:

std::uniform_int_distribution<uint32_t> uint_dist;         // by default range [0, MAX]
std::uniform_int_distribution<uint32_t> uint_dist10(0,10); // range [0,10]
std::normal_distribution<double> normal_dist(mean, stddeviation);  // N(mean, stddeviation)

... Dan gunakan mesin untuk membuat angka acak!

while (true)
{
  std::cout << uint_dist(rng) << " "
            << uint_dist10(rng) << " "
            << normal_dist(rng) << std::endl;

}

Konkurensi

Satu lagi alasan penting untuk memilih <random>daripada yang tradisional rand()adalah bahwa sekarang sangat jelas dan jelas bagaimana membuat pembuatan nomor acak aman untuk benang: Baik menyediakan setiap utas dengan mesin lokal-utasnya sendiri, diunggulkan pada benih lokal-utas, atau akses sinkronisasi ke objek mesin.

Misc

• Sebuah artikel menarik tentang TR1 acak pada CodeGuru.
• Wikipedia memiliki ringkasan yang bagus (terima kasih, @Justin).
• Pada prinsipnya, setiap mesin harus mengetikef a result_type, yang merupakan tipe integral yang benar untuk digunakan benih. Saya pikir saya pernah mengalami implementasi buggy yang memaksa saya untuk memaksa seed untuk std::mt19937ke uint32_tx64, akhirnya ini harus diperbaiki dan Anda dapat mengatakan MyRNG::result_type seed_valdan dengan demikian membuat mesin sangat mudah diganti.

Generator angka acak adalah persamaan yang, jika diberi angka, akan memberi Anda angka baru. Biasanya Anda memberikan nomor pertama atau ditarik dari sesuatu seperti waktu sistem.

Setiap kali Anda meminta bilangan baru, ia menggunakan bilangan sebelumnya untuk menjalankan persamaan.

Generator bilangan acak tidak dianggap sangat baik jika memiliki kecenderungan untuk menghasilkan bilangan yang sama lebih sering daripada bilangan lain. yaitu jika Anda menginginkan nomor acak antara satu dan 5 dan Anda memiliki distribusi angka ini:

• 1: 1%
• 2: 80%
• 3: 5%
• 4: 5%
• 5: 9%

2 dihasilkan JAUH lebih sering daripada nomor lain, sehingga lebih mungkin dihasilkan daripada nomor lain. Jika semua angka sama seperti Anda akan memiliki peluang 20% ​​untuk mendapatkan setiap angka setiap saat. Dengan kata lain, distribusi di atas sangat tidak merata karena 2 disukai. Distribusi dengan semua 20% akan merata.

Biasanya, jika Anda menginginkan bilangan acak yang sebenarnya, Anda akan menarik data dari sesuatu seperti cuaca atau sumber alam lain daripada generator bilangan acak.