C ++ bit magic
0.84ms dengan RNG sederhana, 1.67ms dengan c ++ 11 std :: knuth
0.16ms dengan sedikit modifikasi algoritmik (lihat edit di bawah)
Implementasi python berjalan dalam 7,97 detik di rig saya. Jadi ini 9488 hingga 4772 kali lebih cepat tergantung pada RNG apa yang Anda pilih.
#include <iostream>
#include <bitset>
#include <random>
#include <chrono>
#include <stdint.h>
#include <cassert>
#include <tuple>
#if 0
// C++11 random
std::random_device rd;
std::knuth_b gen(rd());
uint32_t genRandom()
{
return gen();
}
#else
// bad, fast, random.
uint32_t genRandom()
{
static uint32_t seed = std::random_device()();
auto oldSeed = seed;
seed = seed*1664525UL + 1013904223UL; // numerical recipes, 32 bit
return oldSeed;
}
#endif
#ifdef _MSC_VER
uint32_t popcnt( uint32_t x ){ return _mm_popcnt_u32(x); }
#else
uint32_t popcnt( uint32_t x ){ return __builtin_popcount(x); }
#endif
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
uint32_t s1 = S % ( 1 << n );
uint32_t s2 = (S >> 1) % ( 1 << n );
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
// calculate which bits in the expression S * F evaluate to +1
unsigned firstPosBits = ((s1 & posBits) | (~s1 & negBits));
// idem for -1
unsigned firstNegBits = ((~s1 & posBits) | (s1 & negBits));
if ( popcnt( firstPosBits ) == popcnt( firstNegBits ) )
{
firstZero++;
unsigned secondPosBits = ((s2 & posBits) | (~s2 & negBits));
unsigned secondNegBits = ((~s2 & posBits) | (s2 & negBits));
if ( popcnt( secondPosBits ) == popcnt( secondNegBits ) )
{
bothZero++;
}
}
}
}
return std::make_pair(firstZero, bothZero);
}
int main()
{
typedef std::chrono::high_resolution_clock clock;
int rounds = 1000;
std::vector< std::pair<unsigned, unsigned> > out(rounds);
// do 100 rounds to get the cpu up to speed..
for( int i = 0; i < 10000; i++ )
{
convolve();
}
auto start = clock::now();
for( int i = 0; i < rounds; i++ )
{
out[i] = convolve();
}
auto end = clock::now();
double seconds = std::chrono::duration_cast< std::chrono::microseconds >( end - start ).count() / 1000000.0;
#if 0
for( auto pair : out )
std::cout << pair.first << ", " << pair.second << std::endl;
#endif
std::cout << seconds/rounds*1000 << " msec/round" << std::endl;
return 0;
}
Kompilasi dalam 64-bit untuk register tambahan. Saat menggunakan generator acak sederhana, loop di convolve () berjalan tanpa akses memori apa pun, semua variabel disimpan dalam register.
Cara kerjanya: alih-alih menyimpan S
dan F
sebagai array dalam memori, ia disimpan sebagai bit dalam uint32_t.
Untuk S
, n
bit paling signifikan digunakan di mana bit set menunjukkan +1 dan bit unset menunjukkan -1.
F
membutuhkan setidaknya 2 bit untuk membuat distribusi [-1, 0, 0, 1]. Ini dilakukan dengan menghasilkan bit acak dan memeriksa 16 bit paling signifikan (disebut r
) dan 16 bit paling signifikan (disebut l
). Jika l & ~r
kita menganggap bahwa F adalah +1, jika ~l & r
kita menganggap itu F
-1. Kalau F
tidak 0. Ini menghasilkan distribusi yang kita cari.
Sekarang kita miliki S
, posBits
dengan set bit pada setiap lokasi di mana F == 1 dan negBits
dengan bit set pada setiap lokasi di mana F == -1.
Kami dapat membuktikan bahwa F * S
(di mana * menunjukkan perkalian) mengevaluasi ke +1 dalam kondisi tersebut (S & posBits) | (~S & negBits)
. Kami juga dapat membuat logika yang sama untuk semua kasus yang F * S
dievaluasi menjadi -1. Dan akhirnya, kita tahu bahwa sum(F * S)
mengevaluasi ke 0 jika dan hanya jika ada jumlah yang sama dengan -1 dan +1 di hasilnya. Ini sangat mudah untuk dihitung hanya dengan membandingkan jumlah +1 bit dan -1 bit.
Implementasi ini menggunakan 32 bit int, dan maksimum yang n
diterima adalah 16. Dimungkinkan untuk menskalakan implementasi hingga 31 bit dengan memodifikasi kode menghasilkan acak, dan menjadi 63 bit dengan menggunakan uint64_t alih-alih uint32_t.
sunting
Fungsi berbelit-belit berikut:
std::pair<unsigned, unsigned> convolve()
{
const uint32_t n = 6;
const uint32_t iters = 1000;
unsigned firstZero = 0;
unsigned bothZero = 0;
uint32_t fmask = (1 << n) -1; fmask |= fmask << 16;
static_assert( n < 16, "packing of F fails when n > 16.");
for( unsigned i = 0; i < iters; i++ )
{
// generate random bit mess
uint32_t F;
do {
F = genRandom() & fmask;
} while ( 0 == ((F % (1 << n)) ^ (F >> 16 )) );
// Assume F is an array with interleaved elements such that F[0] || F[16] is one element
// here MSB(F) & ~LSB(F) returns 1 for all elements that are positive
// and ~MSB(F) & LSB(F) returns 1 for all elements that are negative
// this results in the distribution ( -1, 0, 0, 1 )
// to ease calculations we generate r = LSB(F) and l = MSB(F)
uint32_t r = F % ( 1 << n );
// modulo is required because the behaviour of the leftmost bit is implementation defined
uint32_t l = ( F >> 16 ) % ( 1 << n );
uint32_t posBits = l & ~r;
uint32_t negBits = ~l & r;
assert( (posBits & negBits) == 0 );
uint32_t mask = posBits | negBits;
uint32_t totalBits = popcnt( mask );
// if the amount of -1 and +1's is uneven, sum(S*F) cannot possibly evaluate to 0
if ( totalBits & 1 )
continue;
uint32_t adjF = posBits & ~negBits;
uint32_t desiredBits = totalBits / 2;
uint32_t S = (1 << (n+1));
// generate all possible N+1 bit strings
// 1 = +1
// 0 = -1
while ( S-- )
{
// calculate which bits in the expression S * F evaluate to +1
auto firstBits = (S & mask) ^ adjF;
auto secondBits = (S & ( mask << 1 ) ) ^ ( adjF << 1 );
bool a = desiredBits == popcnt( firstBits );
bool b = desiredBits == popcnt( secondBits );
firstZero += a;
bothZero += a & b;
}
}
return std::make_pair(firstZero, bothZero);
}
memotong runtime menjadi 0,160-0,161ms. Buka gulungan manual (tidak digambarkan di atas) membuat 0,150. Semakin sedikit sepele n = 10, iter = 100000 case berjalan di bawah 250ms. Saya yakin saya bisa mendapatkannya di bawah 50 ms dengan memanfaatkan core tambahan tapi itu terlalu mudah.
Ini dilakukan dengan membuat cabang loop dalam bebas dan menukar loop F dan S.
Jika bothZero
tidak diperlukan saya dapat mengurangi waktu berjalan ke 0,02 ms dengan jarang perulangan semua kemungkinan array S
-std=c++0x -mpopcnt -O2
dan membutuhkan 1,01ms untuk berjalan dalam mode 32 bit (saya tidak memiliki versi GCC 64-bit di tangan).Python2.7 + Numpy 1.8.1: 10.242 s
Fortran 90+:
0,029 s0,003 s0,022 s0,010 sSialan Anda kehilangan taruhan! Bukan setetes paralelisasi di sini juga, cukup lurus Fortran 90+.
EDIT Saya telah mengambil algoritma Guy Sirton untuk permutasi array
S
(good find: D). Saya rupanya juga memiliki-g -traceback
flag compiler aktif yang memperlambat kode ini menjadi sekitar 0,017. Saat ini, saya menyusun ini sebagaiBagi yang belum punya
ifort
, bisa Anda gunakanEDIT 2 : Penurunan run-time adalah karena saya melakukan sesuatu yang salah sebelumnya dan mendapat jawaban yang salah. Melakukannya dengan cara yang benar tampaknya lebih lambat. Saya masih tidak percaya bahwa C ++ lebih cepat dari milik saya, jadi saya mungkin akan menghabiskan beberapa waktu minggu ini mencoba untuk mengubah omong kosong dari ini untuk mempercepatnya.
EDIT 3 : Dengan hanya mengubah bagian RNG menggunakan yang didasarkan pada RNG BSD (seperti yang disarankan oleh Sampo Smolander) dan menghilangkan pembagian konstan
m1
, saya memotong run-time sama dengan jawaban C ++ oleh Guy Sirton . Menggunakan array statis (seperti yang disarankan oleh Sharpie) menjatuhkan run-time di bawah run-time C ++! Yay Fortran! : DEDIT 4 Rupanya ini tidak mengkompilasi (dengan gfortran) dan berjalan dengan benar (nilai yang salah) karena bilangan bulat melampaui batas-batas mereka. Saya telah membuat koreksi untuk memastikannya berfungsi, tetapi ini mengharuskan seseorang untuk memiliki ifort 11+ atau gfortran 4.7+ (atau kompiler lain yang memungkinkan
iso_fortran_env
danint64
jenis F2008 ).Ini kodenya:
Saya kira pertanyaannya sekarang adalah apakah Anda akan berhenti menggunakan Python slow-as-molasses dan menggunakan Fortran;)
sumber
integer(int64) :: b = 3141592653_int64
untuk semua int64. Ini adalah bagian dari standar fortran dan diharapkan oleh programmer dalam bahasa pemrograman tipe-dinyatakan. (perhatikan bahwa pengaturan default tentu saja dapat mengesampingkan ini)Python 2.7 -
0.882s0.283s(Asli OP: 6.404d)
Sunting: Optimalisasi Steven Rumbalski dengan mengkomputasi nilai F. Dengan optimasi ini, cpython akan mengalahkan 0,365-an pypy.
Kode asli OP menggunakan array kecil seperti itu tidak ada manfaatnya untuk menggunakan Numpy, seperti yang ditunjukkan oleh implementasi python murni ini. Tetapi lihat juga implementasi numpy ini yang tiga kali lebih cepat dari kode saya.
Saya juga mengoptimalkan dengan melewatkan sisa konvolusi jika hasil pertama tidak nol.
sumber
F
karena hanya ada 4032 di antaranya. Tentukan dichoicesF = filter(any, itertools.product([-1, 0, 0, 1], repeat=n))
luar loop. Kemudian di innerloop tentukanF = random.choice(choicesF)
. Saya mendapatkan speedx 3x dengan pendekatan seperti itu.range(iters)
loop. Secara keseluruhan, saya mendapatkan speedup sekitar 7% atas jawaban Anda yang sangat bagus.Karat: 0,011s
Python Asli: 8.3
Terjemahan langsung dari Python asli.
--opt-level=3
rustc 0.11-pre-nightly (eea4909 2014-04-24 23:41:15 -0700)
tepatnya)sumber
a
dan sayab
terlibat dalam belitan; diperbaiki (tidak mengubah runtime secara nyata).C ++ (VS 2012) -
0,026s0,015sPython 2.7.6 / Numpy 1.8.1 - 12s
Speedup ~ x800.
Kesenjangan akan jauh lebih kecil jika array yang berbelit-belit sangat besar ...
Beberapa catatan:
S[0]
sebagai digit "paling tidak signifikan".Tambahkan fungsi utama ini untuk contoh yang lengkap:
sumber
advance
fungsi Anda , jadi kode saya sekarang lebih cepat daripada milik Anda: P (tapi persaingan yang sangat bagus!)C
Membawa 0,015 detik pada mesin saya, dengan kode asli OP mengambil ~ 7,7 detik. Mencoba mengoptimalkan dengan membuat array acak dan berbelit-belit dalam loop yang sama, tetapi tampaknya tidak membuat banyak perbedaan.
Array pertama dihasilkan dengan mengambil integer, menuliskannya dalam biner, dan mengubah semua 1 menjadi -1 dan semua 0 menjadi 1. Selebihnya harus sangat mudah.
Sunting: alih-alih memiliki
n
sebagaiint
, sekarang kita memilikin
konstanta yang didefinisikan secara makro, jadi kita dapat menggunakannyaint arr[n];
sebagai gantimalloc
.Sunting2: Alih-alih
rand()
fungsi bawaan, ini sekarang mengimplementasikan PRNG xorshift. Juga, banyak pernyataan bersyarat dihapus ketika membuat array acak.Kompilasi instruksi:
Kode:
sumber
do{}while(!flag)
atau sesuatu dengan efek itu. Saya tidak berharap ini akan banyak mengubah run-time (dapat membuatnya lebih cepat).continue;
pernyataan saya ditugaskan-1
untukk
, sehinggak
akan loop dari 0 lagi.-=
bukan=-
:-) Suatu saat loop akan lebih mudah dibaca.J
Saya tidak berharap untuk mengalahkan bahasa yang dikompilasi, dan sesuatu mengatakan kepada saya bahwa ini akan membutuhkan mesin ajaib untuk mendapatkan kurang dari 0,09 detik dengan ini, tetapi saya tetap ingin mengirimkan J ini, karena itu cukup apik.
Ini membutuhkan waktu sekitar 0,5 detik pada laptop dari dekade sebelumnya, hanya sekitar 20 kali lebih cepat dari Python dalam jawabannya. Sebagian besar waktu dihabiskan
conv
karena kami menulisnya dengan malas (kami menghitung seluruh lilitan) dan secara umum sepenuhnya.Karena kita mengetahui banyak hal
S
danF
, kita dapat mempercepat dengan membuat optimasi khusus untuk program ini. Yang terbaik yang bisa saya dapatkan adalah —conv =: ((num, num+1) { +//.)@:(*/)"1
pilih secara khusus dua angka yang sesuai dari jumlah diagonal hingga elemen terpanjang dari konvolusi — yang kira-kira mengurangi separuh waktu.sumber
Perl - 9.3X lebih cepat ... 830% peningkatan
Di netbook kuno saya, kode OP membutuhkan waktu 53 detik untuk dijalankan; Versi Alistair Buxton membutuhkan waktu sekitar 6,5 detik, dan versi Perl berikut membutuhkan waktu sekitar 5,7 detik.
sumber
Python 2.7 - numpy 1.8.1 dengan binding mkl - 0.086s
(Asli OP: 6.404s) (python murni Buxton: 0.270s)
Seperti yang ditunjukkan Buxton, kode asli OP menggunakan array sekecil itu, tidak ada manfaatnya menggunakan Numpy. Implementasi ini memanfaatkan numpy dengan melakukan semua kasus F dan S sekaligus dengan cara yang berorientasi array. Ini dikombinasikan dengan binding mkl untuk python mengarah ke implementasi yang sangat cepat.
Perhatikan juga bahwa hanya memuat pustaka dan memulai interpreter memerlukan waktu 0,076s sehingga perhitungan sebenarnya memakan waktu ~ 0,01 detik, mirip dengan solusi C ++.
sumber
python -c "import numpy; numpy.show_config()"
akan menunjukkan kepada Anda jika versi numpy Anda dikompilasi dengan blas / atlas / mkl, dll. ATLAS adalah paket matematika akselerasi gratis yang numpy dapat dihubungkan , Intel MKL yang biasanya harus Anda bayar (kecuali Anda seorang akademisi) dan dapat dihubungkan dengan numpy / scipy .MATLAB 0,024s
Komputer 1
Komputer 2
Saya memutuskan untuk mencoba Matlab yang sangat lambat. Jika Anda tahu caranya, Anda dapat menghilangkan sebagian besar loop (di Matlab), yang membuatnya cukup cepat. Namun, persyaratan memori lebih tinggi daripada untuk solusi looped tetapi ini tidak akan menjadi masalah jika Anda tidak memiliki array yang sangat besar ...
Inilah yang saya lakukan:
Saya berasumsi Anda tidak memiliki matlab, yang terlalu buruk karena saya benar-benar ingin melihat bagaimana membandingkannya ...
(Fungsi ini bisa lebih lambat saat pertama kali Anda menjalankannya.)
sumber
Julia: 0,30 dtk
Op's Python: 21.36 s (Core2 duo)
Kecepatan 71x
Saya melakukan beberapa modifikasi dari jawaban Arman Julia: Pertama-tama, saya membungkusnya dalam suatu fungsi, karena variabel global menyulitkan inferensi tipe Julia dan JIT: Sebuah variabel global dapat mengubah tipenya kapan saja, dan harus diperiksa setiap operasi . Kemudian, saya menyingkirkan fungsi anonim dan pemahaman array. Mereka tidak benar-benar diperlukan, dan masih sangat lambat. Julia lebih cepat dengan abstraksi tingkat rendah sekarang.
Ada banyak cara untuk membuatnya lebih cepat, tetapi ini melakukan pekerjaan yang layak.
sumber
Ok saya memposting ini hanya karena saya merasa Jawa perlu diwakili di sini. Saya buruk dengan bahasa lain dan saya mengaku tidak mengerti masalah sebenarnya, jadi saya perlu bantuan untuk memperbaiki kode ini. Saya mencuri sebagian besar contoh kode ace's C, dan kemudian meminjam beberapa cuplikan dari yang lain. Saya harap itu bukan ...
Satu hal yang ingin saya tunjukkan adalah bahwa bahasa yang dioptimalkan pada waktu berjalan perlu dijalankan beberapa kali untuk mencapai kecepatan penuh. Saya pikir dibenarkan untuk mengambil kecepatan yang sepenuhnya dioptimalkan (atau setidaknya kecepatan rata-rata) karena kebanyakan hal yang Anda khawatirkan dengan berlari cepat akan berjalan beberapa kali.
Kode masih perlu diperbaiki, tetapi saya menjalankannya untuk melihat berapa kali saya akan mendapatkan.
Berikut adalah hasil dari CPU Intel (R) Xeon (R) E3-1270 V2 @ 3.50GHz di Ubuntu yang menjalankannya 1000 kali:
server: / tmp # time java8 -cp. Penguji
firstzero 40000
bothzero 20000
run time pertama: 41 ms run time terakhir: 4 ms
0m5.014s nyata pengguna 0m4.664s sys 0m0.268s
Ini kode jelek saya:
Dan saya mencoba menjalankan kode python setelah memutakhirkan python dan menginstal python-numpy tetapi saya mendapatkan ini:
sumber
currentTimeMillis
untuk pembandingan (gunakan versi nano dalam Sistem) dan 1k menjalankan mungkin tidak cukup untuk melibatkan JIT (1.5k untuk klien dan 10k untuk server akan menjadi default, meskipun Anda cukup sering memanggil myRand sehingga akan menjadi JITed yang seharusnya menyebabkan beberapa fungsi di callstack untuk dikompilasi yang dapat bekerja di sini). Terakhir namun tidak sedikit PNRG yang lemah curang, tetapi begitu juga solusi C ++ dan lainnya, jadi saya kira itu tidak terlalu tidak adil.gettimeofday(&time, NULL)
untuk miliSeconds yang tidak monoton dan tidak memberikan jaminan akurasi (jadi pada beberapa platform / kernel persis sama. masalah sebagai implementasi Windows currentTimeMillis - sehingga yang baik juga atau tidak adalah). nanoTime di sisi lain menggunakanclock_gettime(CLOCK_MONOTONIC, &tp)
yang jelas juga merupakan hal yang tepat untuk digunakan ketika melakukan benchmarking di Linux.Versi 45X python Golang pada mesin saya di bawah ini kode Golang:
dan kode python di bawah ini disalin dari atas:
dan waktu di bawah ini:
sumber
"github.com/yanatan16/itertools"
? Anda juga akan mengatakan ini akan bekerja dengan baik di beberapa goroutine?C # 0.135s
C # berdasarkan pada python polos Alistair Buxton : 0.278s
Parallelised C #: 0.135s
Python dari pertanyaan: 5.907s
python polos Alistair: 0.853s
Saya tidak benar-benar yakin implementasi ini benar - outputnya berbeda, jika Anda melihat hasilnya di bagian bawah.
Tentu saja ada algoritma yang lebih optimal. Saya baru saja memutuskan untuk menggunakan algoritma yang sangat mirip dengan yang Python.
Utas tunggal C
Paralel C #:
Output tes:
Windows (.NET)
C # jauh lebih cepat di Windows. Mungkin karena .NET lebih cepat daripada mono.
Waktu pengguna dan sistem tampaknya tidak berfungsi (digunakan
git bash
untuk menghitung waktu).Linux (mono)
sumber
Haskell: ~ 2000x speedup per core
Kompilasi dengan 'ghc -O3 -funbox-strict-fields -threaded -fllvm', dan jalankan dengan '+ RTS -Nk' di mana k adalah jumlah core pada mesin Anda.
sumber
Rubi
Ruby (2.1.0) 0.277s
Ruby (2.1.1) 0.281s
Python (Alistair Buxton) 0.330s
Python (alemi) 0.097s
sumber
utas tidak akan lengkap tanpa PHP
6.6x lebih cepat
PHP v5.5.9 -
1.2230.646 dtk;vs.
Python v2.7.6 - 8.072 dtk
convolve
fungsinya disederhanakan sedikit agar lebih cepat$F
dan$FS
periksa).Output:
Sunting. Skrip versi kedua hanya berfungsi untuk
0.646 sec
:sumber
Solusi F #
Runtime adalah 0,030s ketika dikompilasi ke x86 pada CLR Core i7 4 (8) @ 3,4 Ghz
Saya tidak tahu apakah kodenya benar.
sumber
Q, 0,296 segmen
Q adalah bahasa berorientasi koleksi (kx.com)
Kode ditulis ulang untuk mengeluarkan Q idiomatik, tetapi tidak ada optimisasi pintar lainnya
Bahasa scripting mengoptimalkan waktu programmer, bukan waktu eksekusi
Usaha pengkodean pertama = bukan pemenang, tetapi waktu yang wajar (kira-kira 30x percepatan)
CATATAN.-
\S seed
\t sentence
mesures waktu dikonsumsi oleh kalimat itusumber
Julia:
12.149 6.929sTerlepas dari klaim mereka untuk mempercepat , waktu kompilasi JIT awal menahan kita!
Perhatikan bahwa kode Julia berikut ini secara efektif merupakan terjemahan langsung dari kode Python asli (tidak ada optimisasi yang dibuat) sebagai demonstrasi bahwa Anda dapat dengan mudah mentransfer pengalaman pemrograman ke bahasa yang lebih cepat;)
Sunting
Menjalankan dengan
n = 8
membutuhkan waktu 32,935 s. Menimbang bahwa kompleksitas dari algoritma iniO(2^n)
, maka4 * (12.149 - C) = (32.935 - C)
,C
adalah konstanta yang mewakili waktu kompilasi JIT. Memecahkan untukC
kami menemukan ituC = 5.2203
, menunjukkan bahwa waktu eksekusi aktualn = 6
adalah 6,929 dtk.sumber
Rust, 6,6 ms, speedup 1950x
Cukup banyak terjemahan langsung kode Alistair Buxton ke Rust. Saya mempertimbangkan untuk menggunakan beberapa core dengan rayon (concurrency tanpa rasa takut!), Tetapi ini tidak meningkatkan kinerja, mungkin karena itu sudah sangat cepat.
Dan Cargo.toml, karena saya menggunakan dependensi eksternal:
Perbandingan kecepatan:
6625608 ns adalah sekitar 6,6 ms. Ini berarti speedup 1950 kali. Ada banyak optimasi yang mungkin dilakukan di sini, tetapi saya lebih memilih keterbacaan daripada kinerja. Salah satu optimasi yang mungkin adalah menggunakan array bukan vektor untuk menyimpan pilihan, karena mereka akan selalu memiliki
n
elemen. Ini juga memungkinkan untuk menggunakan RNG selain XorShift, karena sementara Xorshift lebih cepat dari HC-128 CSPRNG default, ini lebih lambat dari naivest dari algoritma PRNG.sumber