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});
}

[download]
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]});
}

[download]
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] };
}

[download]
I'd be glad to hear any ideas.

$monks{japhy}++ while $posting;

In reply to Efficient random hash stuff by japhy

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.