•Re: selecting random key from hash

As you show it, that's the most efficient way to do it. So, you are saying that you want to do it less efficiently, but optimized for something else. What else is it that you're optimizing for? If memory space, then you can wander over the list of keys using each without ever extracting all the keys at once, selecting one at random:

my %hash = (populated somehow);
my ($victim_key, $victim_value);
for (0..int rand (scalar keys %hash)) { 
  ($victim_key, $victim_value) = each %hash;
}
scalar keys %hash; # reset the iterator
[download]

That'll get you the item without ever having built the entire list of keys in memory.

But if that's not what you are optimizing for, you should clarify your question. If it's simply "don't use an array", then I call homework on the question (usually signalled by a bizarre "don't use X" where "X" is the most efficient way to do something).

-- Randal L. Schwartz, Perl hacker
Be sure to read my standard disclaimer if this is a reply.

Comment on •Re: selecting random key from hash Download Code

Replies are listed 'Best First'.
Re^2: selecting random key from hash by Fletch (Bishop) on Jul 13, 2004 at 03:12 UTC
You could also use a variation on the random line from a file FAQ: `my( $key, $val ); my $ctr = 0; while( my( $k, $v ) = each %hash ) { rand( $ctr++ ) < 1 && do { $key = $k; $val = $v }; }` [download] Actually merlyn's is more efficient since it only reads up to the "victim" element, whereas this would hit all elements (which it has to for the original random line from a file version). Then again if this is a tied hash and FETCH had side-effects that might be what you want. At any rate see `perldoc -q "random line"` for more info.	[reply] [d/l] [select]
•Re^3: selecting random key from hash by merlyn (Sage) on Jul 13, 2004 at 03:20 UTC
Yeah, I actually thought of that first, and then discounted it for the reasons you mentioned. The big difference is that for the random-line solution, we have no cheap way of determining the entire set size, where with a hash, scalar-keys is cheap and tells us what we need to know. -- Randal L. Schwartz, Perl hacker Be sure to read my standard disclaimer if this is a reply.	[reply]
Re^2: selecting random key from hash by davidj (Priest) on Jul 13, 2004 at 04:12 UTC
Homework? I haven't had homework in almost 15 years. I didn't know it was the most efficient way. That's one of the reasons I asked the question. With the types of programs I typically write, I 1) use hashes store data in complex data structures and 2) have to randomly select data from the hash. I have always used the method I described in my post, but have been curious if there are other ways it could be done. (I started using Perl about a year ago, but not on a regular basis until about 5 months ago. So it is still pretty new to me). If the method I am using is the most efficient, then great. I will continue to use it. Thank you all for the input. davidj	[reply]