This Week's Contribution to Perl 6 Week 9: Implement Hash.pick for Rakudo

For this week's contribution to Perl 6 we ask you to implement the Hash.pick method (which does a weighted random selection) for Rakudo.

(Introduction to this series of challenges)

Background

In Perl 6 the List class has a method called pick, which randomly selects one item from a list. It has a few more options too:

<a b c>.pick;       # pick one random element
<a b c>.pick(2);    # pick two distinct, random elements
<a b c>.pick(2, :replace); # pick two random elements, it's ok
                           # if they are the same
<a b c>.pick(*);    # return a random permutation of the elements
<a b c>.pick(*, :replace); # infinite, random stream of elements

This is already implemented through several multi methods in Rakudo.

Now the specification describes such a method for hashes too (actually it talks about Bags, but Rakudo doesn't have Bags yet. Pretend it says "Hash" instead). It assumes that each value in the hash is numeric, and that the value is a weight that determines the probability of picking one value. For example

{a => 1, b => 2}.pick;  # returns 'a' with probability 1/3
                        # and 'b' with probability 2/3

{a => 1, b => 2}.pick(*);  # <a b b> with probability 1/3
                           # <b a b> with probability 1/3
                           # <b b a> with probability 1/3
{a => 1, b => 0.5}.pick(*) # dies, because the weights aren't all integers
{a => 1, b => 0.5}.pick(*, :replace)  # ok 

What you can do

Implement Hash.pick. It's ok if your patch doesn't cover all cases. It would be nice if it supported non-integer weights.

Hint: this could be done by storing a list of accumulated weights, and a list of keys.

{a => 1, b => 2.5, c => 1}

# could translate to 
my @keys = ('a', 'b', 'c');
my @accumulated_weights = (1, 3.5, 4.5);

# now pick a random number between 0 and 4.5,
# find the next-highest index in @accumulated_weights
# with a binary search, and then use that to obtain the key.

Of course other schemes are fine too.

Second hint: because it takes quite some time to recompile Rakudo, it is probably easier to implement the actual logic in a function in a normal source file first, and only later move it into src/core/Hash.pm.

Submission

Please submit your source code to the perl6-compiler@perl.org mailing list (and put moritz@faui2k3.org on CC, because the mailing list sometimes lack quite a bit).

Update: there's one submission on the perl6-compiler mailing list already, which looks pretty good.