Re: easy way to get random key from hash?

You can do it without an array, but you will still have to pay the cost of scanning all the keys once. The idea is that you choose the first element if rand() < 1 (which it always will be), the second element if rand() < 1/2 (which it will be half of the time), the third element if rand() < 1/3 (which will be one third of the time, which leave 2/3 for the first two elements, and we've already seen that they get chosen 50/50)...

You can see where this is going: choose the nth element if rand() < 1 / n. Translated to Perl this gives something like:

sub choose {
  my $count = 0;
  my $result = undef;
  for( @_ ) {
    $result = $_ if rand() < 1 / ++$count;
  }
  $result;
}

my $jokekey = choose( keys %knockknocks );
[download]

This actually chooses from a list, but then that's what the keys of a hash are, so everything is fine.

The beauty of this approach is that you don't need to know beforehand how many elements you have to choose from. That is, the array in question may shrink or grow in the course of the program's run, and the algorithm will compensate. In fact, you may be able to skip loading the hash in the first place, depending on system load. Just read through the file fortune-at-a-time, and cache the file pointer offset instead. Then, at the end of the file seek back to the cached position and read from there. This means you will be able to add fortunes without having to restart the process.

I first heard about this technique in a book by Jon Bentley, either _Programming Pearls_ or _More Programming Perls_. They are probably verging on the edge of being out of print, but if you can track them down, they are absolute gems.

print@_{sort keys %_},$/if%_=split//,'= & *a?b:e\f/h^h!j+n,o@o;r$s-t%t#u'

Comment on Re: easy way to get random key from hash? Download Code

Replies are listed 'Best First'.
Re: Re: easy way to get random key from hash? by jsprat (Curate) on Aug 05, 2002 at 19:53 UTC
Hey! I was about to post the same algorithm (written slightly differently), found in perlfaq5: "How do I select a random line from a file?" You can find the proof by induction here, by guess who. Mine looked like this: `my ($i, $jokekey); ++$i && rand($i) < 1 && ($jokekey = $_) for (keys %hash);` [download] Less readable than your sub, but same idea. However, I wouldn't use it this way in production. Like you said, it always iterates through all the keys of the hash before it returns the random key. The benefit you gain by not needing to know how many elements isn't really a benefit. The following snippet will give you the same benefit and it's easier to read, and (probably) more efficient: `sub choose { #assumes 1st param is \%knockknocks my $jokeref = shift; my @setups = keys %$jokeref; return $setups[rand @setups]; }` [download] Now if the jokes are kept in a separate file, that could change everything ;-)	[reply] [d/l] [select]
Re: Re: easy way to get random key from hash? by Aragorn (Curate) on Aug 05, 2002 at 19:38 UTC
I think the best technique depends on the size of your jokes hash. If you have lots of jokes, use a separate file with the technique grinder describes (that works very well for randomly selecting a line from a file). If there are just some tens of jokes, then `$joke = $knockknocks{(keys %knockknocks)[rand keys %knockknocks]};` [download] works just as well, IMHO. Keep the easy things easy, and all that :-)	[reply] [d/l]


Perl-Sensitive Sunglasses
	PerlMonks