понедельник, 16 ноября 2009 г.

Weighted Random

На протяжении многих лет время от времени приходилось использовать код, выбирающий из списка случайные элементы. При этом в большинстве случаев желательно было учитывать веса. Но поскольку требование о взвешивании было желательно, а не обязательно, то лень побеждала, тем более, что эти требования были моими. :-)

Но вот настал момент, когда я наконец-то победил лень и написал подпрограмму, которая создает замыкание, возвращающие случайный элемент из списка с учетом весов элементов:

sub wrand($) {
my $data = shift;

my $total = 0;
$total += $_ foreach values %$data;

my @dist = ();
while (my ($value, $weight) = each %$data) {
push @dist, [$value, $weight / $total];
}

return sub {
my $rand = rand;
foreach (@dist) {
return $$_[0] if ($rand -= $$_[1]) < 0;
}
return $dist[-1][0];
}
}

Пример использования:

my %foo = (
# value => weight
"one" => 3,
"two" => 2,
"three" => 1,
);

my $wrand = wrand(\%foo);
print $wrand->(), "\n" for 1 .. 10;

Если веса являются целыми числами, то можно использовать более быструю версию:

sub iwrand($) {
my $data = shift;
my %dist = ();
while (my ($value, $weight) = each %$data) {
$dist{keys %dist} = $value foreach 1 .. $weight;
}
return sub {
$dist{int rand keys %dist};
};
}

Смотрите также модуль Math::Random - Random Number Generators.

1 комментарий:

Eugene комментирует...

Еще один подход к этой задаче

http://doer.name/2009/09/20/perl-weighted-random/