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.