Re: [問題] 從0-99999選出一千個不重覆的亂數?
看板Programming作者charleshu (Analog Engineer)時間14年前 (2010/05/27 14:17)推噓1(1推 0噓 0→)留言1則, 1人參與討論串5/9 (看更多)
※ 引述《qeagle (神啊請讓我失戀吧)》之銘言：
: 請問這題要怎麼著手
: 我想產生一些亂數序列以供測試排序功能用
: 產生亂數簡單,但要保持其亂數產生順序,又不能有重覆..
: 不知道大家會怎麼寫好,先產生1000個,再一個個檢查有無重覆嗎...
關於這個問題, 沒有完美的通解, 要看你的亂數值的範圍, 與你要產生的亂數個數來決定
1.假如你的值的範圍不大, 比如說撲克牌洗牌, 或從 0~幾十萬的數值範圍(m)裡取(n)個
不重複的亂數值, 最有效率的方法是陣列取值法, 虛擬碼如下
for(i in 0..m-1)
e[i]=i;
for(i in n-1..0) {
r=亂數 0..i
out(e[r]);
e[r]=e[i];
}
它需要O(m)的儲存空間與O(n)的執行時間.
但因迴圈內每次的亂數範圍會變, 有些亂數產生器可能會有輸出不均勻問題.
假如你有足夠的記憶體空間, 且上面問題可以解決, 它是一個很好的選擇.
2.但假如你的值的範圍很大. 比如說要從 0~2^64 裡面選出1萬個不重複的數字, 方法1 就
有執行上的困難, 因為你難以找出那麼大的儲存空間 ( 記憶體 ), 那先取值然後檢查是
否已出現過就是比較可行的方案了, 虛擬碼如下
set<int64> oUsed;
for(int i=0;i<10000;i++) {
int64 r= 某亂數函數
if (!oUsed.insert(r).second)
continue;
out(r);
}
當然用 hashset 通常會更快, 這裡只討論方法.
當然實際情況下, 問題可能介於兩者之間, 選擇就要評經驗與智慧了.
--
Do not depend on others without effort...
當我年輕時,請教別人問題時常聽到上面那句話. 當時心裏偶而會有些小小抱怨.
當時間過去,我偶而會想到上面那句話, 心中十分感謝當初告訴我那句話的人.
當發現問題時,最有價值的不是問題的答案,
而是找到解決的方向,並在努力的過程裡具備解決問題的能力.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 211.74.232.254
推
06/03 20:05, , 1F
06/03 20:05, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 5 之 9 篇)：