Re: [問題] 從array中隨機取得n個不重複元素

[abliou (愚者)]

※ 引述《peter0726 (江 謝)》之銘言：
: 各為版友大家好
: 小弟有個問題，如標題所述
: 現在想寫一個功能
: 大致上就是隨機從n個數字中取出m個不重複的數字
: 目前寫出來的可以正確執行
: 可是當數字大的時候就會執行頗久的
: 想請教各位有沒有更有效率的寫法0.0?
: 目前的程式碼如下
: sub randpick {
:         my $max = shift;
:         my $need = shift;
:         my %pick;
:         my @picked = keys %pick;
          ^^^^^^^^^^^^^^^^^^^^^^^^ 看了半天 不知道這行在幹嘛 設定成空陣列?
:         while (@picked < $need) {
:                 my $num = int(rand($max));
:                 $pick{$num} = 1;
                  ^^^^^^^^^^^^^^^^ 效率不彰的根源就在這
                  你的"避免重複"的方法就是使用雜湊 但是當你數字多了
                  抽到一樣數字的機會就會變大 造成這個while迴圈跑不完
                  解決方法很簡單 先做出一個不重複的陣列 把這陣列打亂
                  然後切前面幾個就好了
:                 @picked = sort{$a <=> $b} (keys %pick);
:         }

:         return %pick;
: }


sub randpick {
         my $max = shift;
         my $need = shift;
         return @{[sort{rand()>0.5}(0..$max)]}[1..$need];
}

或者連宣告變數都免了

sub randpick {
         return @{[sort{rand()>0.5}(0..$_[0])]}[1..$_[1]];
}

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.113.112.71
※ 文章網址: http://www.ptt.cc/bbs/Perl/M.1415009492.A.4A1.html
推 xatier: 推 作法漂亮
推 CindyLinz: :D
→ abliou: 阿 是前輩們不嫌啦....
推 peter0726: 請教一下 sort裡面的「{rand()>0.5}」是甚麼意思?
→ peter0726: 我只會sort{$a cmp $b}這樣的
推 CindyLinz: 正常是放兩者的比較結果, 現在他說要用電風扇當比較結
→ CindyLinz: 果, 所以就變成亂排了.. XD
→ CindyLinz: rand() 會給一個 [0,1) 之間的隨機數
→ scwg: 還是冒出來說一下, 十年前從兔子那邊學到 sort{rand} 的
→ scwg: shuffle, 怎麼十年來這個又不快, 又不 random 的方法還沒死
→ scwg: 透啊...
推 CindyLinz: 不過為什麼如果寫 sort { rand - .5 } 就完全不亂了呢
→ scwg: 因為 rand - .5 被 parse 成 rand( -.5 ), 回傳 -0.5~0
→ scwg: 怪怪的, 就算 rand() - .5 也不亂
推 CindyLinz: 可是我寫 rand() - .5 也不亂啊 o.o
→ CindyLinz: 該不會要 -1, 0, 1 吧... orz
→ CindyLinz: 噢找到了.. perldoc -f sort 的說明裡面寫:
→ scwg: 啊, 因為 man page of sort: ... subroutine that returns
→ scwg:  an integer less than, equal to, or greater than 0 ...
→ CindyLinz: a subroutine that returns an integer less than, equ
→ CindyLinz: integer.. QQ
→ scwg: 不過 { rand > .5 } 還是不算是亂就是了 (fail chi^2 test)
→ CindyLinz: 嗯, 排 1~10 就感覺得出來了..