Sunday, September 20, 2009

Perl: выбор случайных элементов из списка с учетом веса

Понадобилось написать функцию, выбирающую случайные элементы из списка с учетом веса (целое число). Привожу один из вариантов решения.

В perlfaq5 содержится простой до безобразия однострочник, который выбирает случайную строку в файле:
rand($.) < 1 && ($line = $_) while <>;

Этот алгоритм применим к задаче. Все что нам надо - это сделать выбор объектов с большим весом более вероятным:
sub pickAnObject {
my ($hObjects) = @_; # хэш, связывающий ID объекта и его вес
my ($total, $result);

while (my ($objectID, $weight) = each %$hObjects) {
rand($total += $weight) < $weight and $result = $objectID;
}
return $result;
}


Алгоритм хорошо подходит для случаев, когда число элементов невелико.

No comments:

Post a Comment