I'm trying to get around the possible slowness of:
# ($k,$v) = rhe_1(%hash);
sub rhe_1 (\%) {
my $key = (keys %{ $_[0] })[rand keys %{ $_[0] }];
return ($key, delete $_[0]{$key});
}
Now, this is obviously inefficient, because it must rebuild
a list of keys each time, which can be bad for large hashes
(like a hash representing a dictionary). Now, one possible
solution is an array and a hash working together:
# @keys = keys %hash; # done ONCE
# ($k,$v) = rhe_2(%hash,@keys);
sub rhe_2 (\%\@) {
my $key;
do {
$key = rand @keys
} until exists $_[0]{$_[1][$key]};
return ($_[0]{$_[1][$key]}, delete $_[0]{$_[1][$key]});
}
That trades the slowness of
splice() for the possible
slowness of having to reselect a random index. However, this
requires an extra N amount of memory allocated.
What can I do? Is there any work on making such an operation
efficient?
Here's a possible solution, which needs extra space, but not
much (on average), and uses an array instead of a hash:
# %seen = (); # done ONCE
# @array = ([k,v], [k,v], ...);
# ($k,$v) = rhe_3(@array,%seen);
sub rhe_3 (\@\%) {
my $idx;
do { $idx = rand @{ $_[0] } } while $_[1]{int $idx}++;
return @{ $_[0][$idx] };
}
I'd be glad to hear any ideas.
$monks{japhy}++ while $posting;
