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 );
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' | [reply]
[d/l] |
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);
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];
}
Now if the jokes are kept in a separate file, that could change everything ;-) | [reply]
[d/l]
[select] |
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]};
works just as well, IMHO. Keep the easy things easy, and all that :-) | [reply]
[d/l] |
This is ugly, but it seems to "work":
#!/usr/bin/perl -w
use strict;
my %hash = (foo=>1, bar=>2, baz=>3);
print $hash{[keys %hash]->[int rand keys %hash]};
However, it still creates the "temporary array", it just makes it anonymous, inline, and therefore impossible to reuse (so, you go through all that trouble for no really good reason.) If you plan to, in your code, retrieve random keys more than once, I suggest just keeping the array around to save the cost of recreation. That is, until one of the more perl-gifted monks gives you a better answer than this :) | [reply]
[d/l] |
Keep your jokes in an array, and have a separate hash for an index. You can still use the array directly by number, or use the index.
Or, vice-versa: make an array of hash keys that you reuse, or an array of references to the individual joke records.
A tie can provide you a collection that has all the properties you need, with all that under the covers.
—John | [reply] |
