Buat fungsi yang akan menampilkan sekumpulan angka acak berbeda yang diambil dari suatu rentang. Urutan elemen dalam himpunan tidak penting (mereka bahkan dapat diurutkan), tetapi harus mungkin untuk isi himpunan berbeda setiap kali fungsi dipanggil.
Fungsi akan menerima 3 parameter dalam urutan apa pun yang Anda inginkan:
- Hitungan angka dalam output yang ditetapkan
- Batas bawah (inklusif)
- Batas atas (inklusif)
Asumsikan semua angka adalah bilangan bulat dalam kisaran 0 (inklusif) hingga 2 31 (eksklusif). Output dapat dikirimkan kembali dengan cara apa pun yang Anda inginkan (tulis ke konsol, sebagai array, dll.)
Menilai
Kriteria termasuk 3 R
- Run-time - diuji pada mesin Windows 7 quad-core dengan kompiler apa pun yang tersedia secara bebas atau mudah (berikan tautan jika perlu)
- Robustness - apakah fungsi menangani kasus sudut atau akan jatuh ke loop tak terbatas atau menghasilkan hasil yang tidak valid - pengecualian atau kesalahan pada input yang tidak valid valid
- Keacakan - ini harus menghasilkan hasil acak yang tidak mudah diprediksi dengan distribusi acak. Menggunakan generator bilangan acak bawaan baik-baik saja. Tetapi seharusnya tidak ada bias yang jelas atau pola yang dapat diprediksi. Perlu lebih baik daripada generator angka acak yang digunakan oleh Departemen Akuntansi di Dilbert
Jika itu kuat dan acak maka turun ke run-time. Gagal menjadi kuat atau acak sangat menyakitkan kedudukannya.
code-challenge
fastest-code
number
random
Jim McKeeth
sumber
sumber
Jawaban:
Python
Saya mungkin baru saja menemukan kembali beberapa algoritma yang terkenal, tetapi idenya adalah untuk (secara konseptual) melakukan shuffle Fisher-Yates parsial dari kisaran
lower..upper
untuk mendapatkann
awalan panjang rentang yang dikocok secara seragam.Tentu saja, menyimpan seluruh jajaran akan lebih mahal, jadi saya hanya menyimpan lokasi di mana elemen telah ditukar.
Dengan cara ini, algoritme harus berkinerja baik baik dalam kasus di mana Anda sampel angka dari kisaran ketat (misalnya 1000 angka dalam kisaran 1..1000), serta kasus di mana Anda mengambil sampel angka dari rentang besar .
Saya tidak yakin tentang kualitas keacakan dari generator built-in di Python, tetapi relatif mudah untuk menukar generator apa pun yang dapat menghasilkan bilangan bulat secara seragam dari beberapa rentang.
sumber
python 2.7
tidak yakin apa posisi Anda saat menggunakan metode acak bawaan, tapi begini saja. bagus dan pendek
sunting: cukup perhatikan bahwa rentang () tidak suka membuat daftar besar. menyebabkan kesalahan memori. akan melihat apakah ada cara lain untuk melakukan ini ...
sunting2: range adalah fungsi yang salah, xrange berfungsi. Bilangan bulat maksimum sebenarnya
2**31-1
untuk pythonuji:
sumber
C
Mengembalikan array yang berisi x int acak unik antara min dan maks. (penelepon harus bebas)
Bekerja dengan menghasilkan bilangan bulat acak berurutan dalam kisaran, lalu mengocoknya. Tambahkan
seed(time)
penelepon di suatu tempat jika Anda tidak ingin hasil yang sama setiap kali dijalankan.sumber
Ruby> = 1.8.7
sumber
R
sumber
Pertanyaannya tidak benar. Apakah Anda perlu pengambilan sampel yang seragam atau tidak? Dalam pengambilan sampel kasus seragam diperlukan Saya memiliki kode berikut di R, yang memiliki rata-rata kompleksitas O ( s log s ), di mana s adalah ukuran sampel.
Tentu saja, seseorang dapat menulis ulang dalam C untuk kinerja yang lebih baik. Kompleksitas dari algoritma ini dibahas dalam: Rouzankin, PS; Voytishek, AV Pada biaya algoritma untuk pemilihan acak. Metode Monte Carlo Appl. 5 (1999), no. 1, 39-54. http://dx.doi.org/10.1515/mcma.1999.5.1.39
Anda dapat melihat melalui makalah ini untuk algoritma lain dengan kompleksitas rata-rata yang sama.
Tetapi jika Anda tidak perlu pengambilan sampel yang seragam, hanya mengharuskan semua nomor sampel berbeda, maka situasinya berubah secara dramatis. Tidak sulit untuk menulis algoritma yang memiliki kompleksitas rata-rata O ( s ).
Lihat juga untuk pengambilan sampel yang seragam: P. Gupta, GP Bhattacharjee. (1984) Algoritma yang efisien untuk pengambilan sampel acak tanpa penggantian. Jurnal Internasional Matematika Komputer 16: 4, halaman 201-209. DOI: 10.1080 / 00207168408803438
Teuhola, J. dan Nevalainen, O. 1982. Dua algoritma yang efisien untuk pengambilan sampel acak tanpa penggantian. / IJCM /, 11 (2): 127-140. DOI: 10.1080 / 00207168208803304
Dalam makalah terakhir penulis menggunakan tabel hash dan mengklaim bahwa algoritma mereka memiliki kompleksitas O ( s ). Ada satu lagi algoritma tabel hash yang lebih cepat, yang akan segera diimplementasikan dalam pqR (R cukup cepat): https://stat.ethz.ch/pipermail/r-devel/2017-October/075012.html
sumber
APL,
1822 byteMenyatakan fungsi anonim yang mengambil dua argumen
⍺
dan⍵
.⍺
adalah jumlah angka acak yang Anda inginkan,⍵
adalah vektor yang berisi batas bawah dan atas, dalam urutan itu.a?b
mengambila
nomor acak antara 0b
tanpa penggantian. Dengan mengambil,⍵[1]-⍵[0]
kami mendapatkan ukuran kisaran. Lalu kami memilih⍺
angka (lihat di bawah) dari rentang itu dan menambahkan batas bawah. Dalam C, ini akan menjadi⍺
kali tanpa penggantian. Kurung tidak diperlukan karena APL beroperasi dari kanan ke kiri.Dengan asumsi saya sudah memahami kondisinya dengan benar, ini gagal kriteria 'kekokohan' karena fungsinya akan gagal jika diberikan argumen yang tidak tepat (misal, meneruskan vektor alih-alih skalar⍺
).Dalam hal itu
⍺
adalah vektor daripada skalar,1↑⍺
ambil elemen pertama⍺
. Untuk skalar, ini adalah skalar itu sendiri. Untuk vektor, itu elemen pertama. Ini harus membuat fungsi memenuhi kriteria 'ketahanan'.Contoh:
sumber
{⍵+⍺?⎕-⍵}
cukuplah, di mana prompt adalah untuk batas atas dan arg kanan adalah batas bawahScala
kompilasi dan jalankan:
Baris kedua akan menjalankan 200 tes dengan 15 nilai dari 0 hingga 100, karena Scala menghasilkan bytecode cepat tetapi membutuhkan waktu startup. Jadi 200 dimulai dengan 15 nilai dari 0 hingga 100 akan menghabiskan lebih banyak waktu.
Sampel pada Core Tunggal 2 Ghz:
Logika:
Menggunakan built-in angka acak dan rekursif dalam rentang (maks-mnt), menambahkan min dan memeriksa, jika ukuran set adalah ukuran yang diharapkan.
Kritik:
sumber
Skema
Tidak yakin mengapa Anda perlu 3 parameter lulus atau mengapa saya perlu mengasumsikan kisaran apa pun ...
sumber
R
sumber
C ++
Kode ini paling baik ketika menggambar banyak sampel dari kisaran.
sumber
max-min
lebih besar darin
. Juga, urutan output meningkat secara monoton, sehingga Anda mendapatkan keacakan kualitas yang sangat rendah tetapi masih membayar biaya panggilanrand()
beberapa kali per hasil. Acak acak array mungkin sebanding dengan run-time tambahan.Q (19 karakter)
Kemudian gunakan f [x; y; z] sebagai [jumlah angka dalam output yang ditetapkan; titik awal; ukuran kisaran]
misalnya f [5; 10; 10] akan menampilkan 5 angka acak berbeda antara 10 dan 19 inklusif.
Hasil di atas menunjukkan kinerja pada 100.000 iterasi memilih 100 angka acak antara 1 & 10.000.
sumber
R, 31 atau 40 byte (tergantung pada arti kata "rentang")
Jika input memiliki 3 angka,,
a[1], a[2], a[3]
dan "range" yang Anda maksudkan adalah "deret integer dari [2] ke [3]", maka Anda memiliki ini:Jika Anda memiliki larik
n
yang akan Anda coba sampel ulang, tetapi di bawah batasan batas bawah dan atas, seperti "nilai ulang sampel larik yang diberikann
dari rentanga[1]...a[2]
", maka gunakan ini:Saya cukup terkejut mengapa hasil sebelumnya tidak golf mengingat sampel bawaan dengan fasilitas pengganti! Kami membuat vektor yang memenuhi kondisi rentang dan sampel ulang itu.
sumber
0:(2^31)
menyebabkanError: cannot allocate a vector of size 16.0 Gb
Javascript (menggunakan perpustakaan eksternal) (64 byte / 104 byte ??)
Tautan ke lib: https://github.com/mvegh1/Enumerable/
Penjelasan kode: Ekspresi Lambda menerima min, maks, hitung sebagai argumen. Buat koleksi ukuran n, dan petakan setiap elemen ke angka acak yang sesuai dengan kriteria min / maks. Konversikan ke array JS asli dan kembalikan. Saya menjalankan ini juga pada input ukuran 5.000.000, dan setelah menerapkan transformasi yang berbeda masih menunjukkan 5.000.000 elemen. Jika disetujui bahwa ini tidak cukup aman untuk jaminan perbedaan, saya akan memperbarui jawabannya
Saya memasukkan beberapa statistik pada gambar di bawah ini ...
EDIT: Gambar di bawah ini menunjukkan kode / kinerja yang menjamin setiap elemen akan berbeda. Ini jauh lebih lambat (6,65 detik untuk 50.000 elemen) vs kode asli di atas untuk args yang sama (0,012 detik)
sumber
K (oK) , 14 byte
Larutan:
Cobalah online!
Contoh:
Penjelasan:
Membawa 3 input implisit per spec:
x
, hitung angka dalam output yang ditetapkan,y
, batas bawah (inklusif)z
, batas atas (inklusif)Catatan:
Juga polyglot
q/kdb+
dengan set kurung tambahan:{y+((-)x)?1+z-y}
(16 byte).sumber
Aksioma + perpustakaannya
Fungsi f () di atas mengembalikan kesalahan daftar kosong, dalam kasus f (n, a, b) dengan a> b. Dalam kasus lain dari input yang tidak valid, itu tidak berjalan dengan satu pesan kesalahan di jendela aksioma, karena argumen tidak akan menjadi tipe yang tepat. Contohnya
sumber