Perl / 技術情報 / アルゴリズム / ルーレット選択

  • ある集合の要素はそれぞれ重みを持っている。
  • 例えばそれぞれの重みが @rate = (60,30,10) だとして、それぞれに対して累計 @total = (60,90,100) を求める。
  • それぞれの累計の値は、それぞれの要素の数直線上の値を表すと考えると良い。
  • 次に累計の範囲内でランダムな値を決め、それぞれの累計の値と比較すれば、対応する要素が求まる。
  • 以下のroulette1()/roulette2()はその実装。

#!/usr/local/bin/perl

use strict;
use warnings;
use Data::Dumper;

my @rate = (60,30,10);

my @result1;
foreach ( 1 .. 100000 ) {
 my $idx = roulette1(@rate);
 $result1[$idx]++;
}
print Dumper \@result1;

my @result2;
foreach ( 1 .. 100000 ) {
 my $idx = roulette2(@rate);
 $result2[$idx]++;
}
print Dumper \@result2;

sub roulette1 {
 my @rate = @_;
 my @total;
 $total[0] = $rate[0];
 for ( my $i = 1 ; $i < @rate ; $i++ ) {
     $total[$i] = $total[ $i - 1 ] + $rate[$i];
 }
 my $rand = int( rand( $total[ @total - 1 ] ) ) + 1;
 my $idx  = 0;
 while ( $rand > $total[$idx] ) {
     $idx++;
 }
 return $idx;
}

sub roulette2 {
 my @rate = @_;
 my $total;
 foreach my $n (@rate) {
     $total += $n;
 }
 my $rand = int( rand($total) ) + 1;
 my $idx = 0;
 for ( ; $idx < @rate ; $idx++ ) {
     $rand -= $rate[$idx];
     if ( $rand <= 0 ) {
         last;
     }
 }
 return $idx;
}

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)