| 1 | package Math::Random::Discrete; | ||||||||||||||||||||||||||||
| 2 | 2 | $Math::Random::Discrete::VERSION = '1.02'; | |||||||||||||||||||||||||||
| 3 | 2 | ▶ | use strict; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 4 | 2 | ▶ | use warnings; | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 5 | |||||||||||||||||||||||||||||
| 6 | 2 | ▶ | use Carp qw(croak); | ||||||||||||||||||||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||||||||||||||||||||
| 7 | |||||||||||||||||||||||||||||
| 8 | # ABSTRACT: Discrete random variables with general distributions | ||||||||||||||||||||||||||||
| 9 | |||||||||||||||||||||||||||||
| 10 | # This is an implementation of Walker's alias method. | ||||||||||||||||||||||||||||
| 11 | |||||||||||||||||||||||||||||
| 12 | 1 | ▶ | sub new { | ||||||||||||||||||||||||||
|
Subroutine
new: called CC=12 SCAR=25.2
Pod
documented
| |||||||||||||||||||||||||||||
| 13 | 1 | my ($class, $_weights, $values) = @_; | |||||||||||||||||||||||||||
| 14 | |||||||||||||||||||||||||||||
| 15 | 1 | ▶ | croak("No weights specified") | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
defined $_weights and @$_weights
MC/DC0%0/2
defined $_weights and @$_weights
defined $_weights
@$_weights
Truth table33%1/3
A and B
A= defined $_weightsB= @$_weights
| |||||||||||||||||||||||||||||
| 16 | if !defined($_weights) || !@$_weights; | ||||||||||||||||||||||||||||
| 17 | 1 | ▶ | croak("Number of values must equal number of weights") | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition33%1/3
defined $values and @$values != @$_weights
MC/DC0%0/2
defined $values and @$values != @$_weights
defined $values
@$values != @$_weights
Truth table33%1/3
A and B
A= defined $valuesB= @$values != @$_weights
| |||||||||||||||||||||||||||||
| 18 | if defined($values) && @$values != @$_weights; | ||||||||||||||||||||||||||||
| 19 | |||||||||||||||||||||||||||||
| 20 | 1 | my @weights = @$_weights; | |||||||||||||||||||||||||||
| 21 | |||||||||||||||||||||||||||||
| 22 | # compute average weight | ||||||||||||||||||||||||||||
| 23 | |||||||||||||||||||||||||||||
| 24 | 1 | my $N = @weights; | |||||||||||||||||||||||||||
| 25 | 1 | my $sum = 0; | |||||||||||||||||||||||||||
| 26 | |||||||||||||||||||||||||||||
| 27 | 1 | for my $weight (@weights) { | |||||||||||||||||||||||||||
| 28 | 10 | $sum += $weight; | |||||||||||||||||||||||||||
| 29 | } | ||||||||||||||||||||||||||||
| 30 | |||||||||||||||||||||||||||||
| 31 | 1 | my $avg = $sum / $N; | |||||||||||||||||||||||||||
| 32 | |||||||||||||||||||||||||||||
| 33 | # split weights into two groups: smaller and larger than average | ||||||||||||||||||||||||||||
| 34 | |||||||||||||||||||||||||||||
| 35 | 1 | my (@small, @large); | |||||||||||||||||||||||||||
| 36 | |||||||||||||||||||||||||||||
| 37 | 1 | ▶ | for (my $i = 0; $i < $N; ++$i) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 38 | 10 | ▶ | if ($weights[$i] <= $avg) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 39 | 5 | push(@small, $i); | |||||||||||||||||||||||||||
| 40 | } | ||||||||||||||||||||||||||||
| 41 | else { | ||||||||||||||||||||||||||||
| 42 | 5 | push(@large, $i); | |||||||||||||||||||||||||||
| 43 | } | ||||||||||||||||||||||||||||
| 44 | } | ||||||||||||||||||||||||||||
| 45 | |||||||||||||||||||||||||||||
| 46 | # generate F and A arrays | ||||||||||||||||||||||||||||
| 47 | |||||||||||||||||||||||||||||
| 48 | 1 | my (@F, @A); | |||||||||||||||||||||||||||
| 49 | |||||||||||||||||||||||||||||
| 50 | 1 | ▶ | while (@small and @large) { | ||||||||||||||||||||||||||
|
Branch: 1 branch
Condition66%2/3
@small and @large
MC/DC50%1/2
@small and @large
@small
@large
Truth table66%2/3
A and B
A= @smallB= @large
| |||||||||||||||||||||||||||||
| 51 | 9 | my $i = pop(@small); | |||||||||||||||||||||||||||
| 52 | 9 | my $j = $large[-1]; | |||||||||||||||||||||||||||
| 53 | 9 | $A[$i] = $j; | |||||||||||||||||||||||||||
| 54 | 9 | $F[$i] = $weights[$i] / $avg; | |||||||||||||||||||||||||||
| 55 | |||||||||||||||||||||||||||||
| 56 | 9 | $weights[$j] -= $avg - $weights[$i]; | |||||||||||||||||||||||||||
| 57 | |||||||||||||||||||||||||||||
| 58 | 9 | ▶ | push(@small, pop(@large)) | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 59 | if $weights[$j] <= $avg; | ||||||||||||||||||||||||||||
| 60 | } | ||||||||||||||||||||||||||||
| 61 | |||||||||||||||||||||||||||||
| 62 | 1 | for my $i (@small, @large) { | |||||||||||||||||||||||||||
| 63 | 1 | $A[$i] = $i; | |||||||||||||||||||||||||||
| 64 | 1 | $F[$i] = 1.0; | |||||||||||||||||||||||||||
| 65 | } | ||||||||||||||||||||||||||||
| 66 | |||||||||||||||||||||||||||||
| 67 | # create blessed ref | ||||||||||||||||||||||||||||
| 68 | |||||||||||||||||||||||||||||
| 69 | 1 | my $self = { | |||||||||||||||||||||||||||
| 70 | values => $values, | ||||||||||||||||||||||||||||
| 71 | A => \@A, | ||||||||||||||||||||||||||||
| 72 | F => \@F, | ||||||||||||||||||||||||||||
| 73 | }; | ||||||||||||||||||||||||||||
| 74 | |||||||||||||||||||||||||||||
| 75 | 1 | return bless($self, $class); | |||||||||||||||||||||||||||
| 76 | } | ||||||||||||||||||||||||||||
| 77 | |||||||||||||||||||||||||||||
| 78 | 55000 | ▶ | sub rand { | ||||||||||||||||||||||||||
|
Subroutine
rand: called CC=3 SCAR=11.0
Pod
documented
| |||||||||||||||||||||||||||||
| 79 | 55000 | my $self = shift; | |||||||||||||||||||||||||||
| 80 | |||||||||||||||||||||||||||||
| 81 | 55000 | my $F = $self->{F}; | |||||||||||||||||||||||||||
| 82 | 55000 | my $r = CORE::rand(@$F); | |||||||||||||||||||||||||||
| 83 | 55000 | my $ri = int($r); # integer part | |||||||||||||||||||||||||||
| 84 | 55000 | my $rf = $r - $ri; # fractional part | |||||||||||||||||||||||||||
| 85 | |||||||||||||||||||||||||||||
| 86 | 55000 | ▶ | my $i = $rf < $F->[$ri] ? $ri : $self->{A}[$ri]; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 87 | |||||||||||||||||||||||||||||
| 88 | 55000 | my $values = $self->{values}; | |||||||||||||||||||||||||||
| 89 | |||||||||||||||||||||||||||||
| 90 | 55000 | ▶ | return $values ? $values->[$i] : $i; | ||||||||||||||||||||||||||
|
Branch: 1 branch
| |||||||||||||||||||||||||||||
| 91 | } | ||||||||||||||||||||||||||||
| 92 | |||||||||||||||||||||||||||||
| 93 | 2 | 1; | |||||||||||||||||||||||||||
| 94 | |||||||||||||||||||||||||||||
| 95 | __END__ | ||||||||||||||||||||||||||||