Cara tercepat untuk menghasilkan boolean acak

87

Jadi ada beberapa cara membuat bool acak di C #:

  • Menggunakan Random.Next (): rand.Next(2) == 0
  • Menggunakan Random.NextDouble (): rand.NextDouble() > 0.5

Apakah benar-benar ada perbedaan? Jika ya, mana yang sebenarnya memiliki performa lebih baik? Atau apakah ada cara lain yang tidak saya lihat, yang mungkin lebih cepat?

c# performance random boolean waktunya
sumber
17
ericlippert.com/2012/12/17/performance-rant
Austin Salonen
7
Apakah ini benar-benar penghambat?
Brian Rasmussen
2
Tanpa benar-benar menjalankannya (karena metode apa pun akan sangat cepat), tebakan saya akan digunakan NextBytesuntuk mempopulasikan array byte, gunakan BitArrayuntuk mengubahnya menjadi kumpulan boolean, dan mengambil boolean itu dari Queuesampai kosong, lalu ulangi proses. Dengan metode ini, Anda hanya menggunakan pengacak satu kali, jadi overhead apa pun yang dibuatnya hanya terjadi saat Anda mengisi ulang antrian. Ini bisa berguna ketika berurusan dengan generator nomor acak yang aman daripada Randomkelas biasa .
Joe Enos
2
@JoeEnos MS mengacaukan penerapannya NextBytes, jadi ternyata sangat lambat
CodesInChaos
1
@CodesInChaos Wow, itu menarik - Saya baru saja mencarinya di disassembler untuk melihat apa yang Anda maksud: buffer[i] = (byte)(this.InternalSample() % 256);- Saya berasumsi itulah yang Anda bicarakan, bahwa mereka dapat mengambil bilangan bulat acak itu dan membaginya menjadi 3 byte , mengisi array byte dengan sekitar 1/3 pekerjaan. Saya ingin tahu apakah ada alasan untuk itu atau apakah itu hanya pengawasan oleh pengembang.
Joe Enos

Jawaban:

72

The Opsi pertama - rand.Next(2)mengeksekusi belakang layar kode berikut:

if (maxValue < 0)
{
    throw new ArgumentOutOfRangeException("maxValue",
        Environment.GetResourceString("ArgumentOutOfRange_MustBePositive", new object[] { "maxValue" }));
}
return (int) (this.Sample() * maxValue);

dan untuk opsi kedua - rand.NextDouble():

return this.Sample();

Karena opsi pertama berisi maxValuevalidasi, perkalian, dan casting, opsi kedua mungkin lebih cepat .

Aviran Cohen
sumber
Terima kasih, hanya itu yang ingin saya ketahui.
waktunya tanggal
5
Pengaturan waktu saya sendiri mengatakan bahwa opsi kedua sekitar 5% lebih cepat daripada yang pertama.
ClickRick
61

Peningkatan kecil untuk opsi kedua :

Menurut MSDN

public virtual double NextDouble()

kembali

Angka floating point presisi ganda lebih besar dari atau sama dengan 0,0, dan kurang dari 1,0.

Jadi jika Anda ingin bool acak tersebar merata Anda harus menggunakan >= 0.5

rand.NextDouble() >= 0.5

Rentang 1: [0,0 ... 0,5 [
Rentang 2: [0,5 ... 1,0 [
| Rentang 1 | = | Rentang 2 |

DaRich
sumber
10

Tercepat. Memanggil metode Random.Nextmemiliki overhead yang lebih sedikit. Metode ekstensi di bawah ini berjalan 20% lebih cepat dari Random.NextDouble() > 0.5, dan 35% lebih cepat dari Random.Next(2) == 0.

public static bool NextBoolean(this Random random)
{
    return random.Next() > (Int32.MaxValue / 2);
    // Next() returns an int in the range [0..Int32.MaxValue]
}

Lebih cepat dari yang tercepat. Dimungkinkan untuk menghasilkan boolean acak dengan Randomkelas lebih cepat, dengan menggunakan trik. 31 bit signifikan yang dihasilkan intdapat digunakan untuk 31 produksi boolean berikutnya. Implementasi di bawah ini 40% lebih cepat dari yang sebelumnya dinyatakan sebagai yang tercepat.

public class RandomEx : Random
{
    private uint _boolBits;

    public RandomEx() : base() { }
    public RandomEx(int seed) : base(seed) { }

    public bool NextBoolean()
    {
        _boolBits >>= 1;
        if (_boolBits <= 1) _boolBits = (uint)~this.Next();
        return (_boolBits & 1) == 0;
    }
}
Theodor Zoulias
sumber
Terima kasih! Bagi mereka yang menggunakan UnityEngine untuk menulis skrip, pastikan untuk menggunakan System.Random dan bukan UnityEngine.Random, karena keduanya bukan hal yang sama!
DonCarleone
6

Saya menjalankan tes dengan stopwatch. 100.000 iterasi:

System.Random rnd = new System.Random();
if (rnd.Next(2) == 0)
     trues++;

CPU menyukai integer, jadi metode Next (2) lebih cepat. 3.700 versus 7.500ms, yang cukup substansial. Juga: Saya pikir angka acak bisa menjadi penghambat, saya membuat sekitar 50 setiap frame di Unity, bahkan dengan adegan kecil yang secara nyata memperlambat sistem saya, jadi saya juga berharap menemukan metode untuk membuat bool acak. Jadi saya juga mencoba

if (System.DateTime.Now.Millisecond % 2 == 0)
       trues++;

tetapi memanggil fungsi statis bahkan lebih lambat dengan 9.600ms. Layak dicoba. Akhirnya saya melewatkan perbandingan dan hanya membuat 100.000 nilai acak, untuk memastikan perbandingan int vs. double tidak mempengaruhi waktu yang telah berlalu, tetapi hasilnya hampir sama.

Frederik Steinmetz
sumber
1
DateTime.Now terkenal lambat. Idealnya solusi yang bergantung pada perangkat keras atau setidaknya bergantung pada OS harus digunakan untuk membuatnya cepat.
Lakukan-baru
Gunakan DateTime.UtcNow, ini jauh lebih cepat dari DateTime.Now.
Theodor Zoulias