Edit: Apologies to ikegami for misreading his code. While the benchmark still more or less stands, my assertion that the output would differ was incorrect.

Your code will not produce the same output as the OP's. You indeed removed an O(N log N) loop, but at the cost of the sort. Even then, thanks to the grep and extra hash loop versus slice, the OP's (sorted) performance is 300% better than your unsorted code. Both unsorted, the gap widens to nearly 1000% with N = 1x105.

With N = 1x106, the gap shrinks a bit to 214% and 738%, respectively.

Perhaps I'm missing your point, though? Edit: Yup!

N = 1x105

                 Rate ikegami_sort   ikegami         op op_nosort
ikegami_sort   4.68/s           --       -1%       -75%%      -91%
ikegami        4.72/s           1%        --       -75%%      -91%
op             19.1/s         308%      304%         --%      -62%
op_nosort      50.6/s         981%      970%       165%        --

[download]

N = 1x106

                  Rate ikegami_sort   ikegami        op op_nosort
ikegami_sort   0.345/s           --       -1%      -68%      -88%
ikegami        0.348/s           1%        --      -68%      -88%
op              1.08/s         214%      212%        --      -63%
op_nosort       2.90/s         738%      733%      167%        --

[download]

Test program:

use Benchmark qw/cmpthese timethese :hireswallclock/;

my $N = 1e6; # N

my @allrefs = map { 1e5 + int rand 9e5 } 1..$N;
my %uni_refs = map { 1e6 + int rand 9e6 => $_ } 1..$N;

cmpthese(timethese(-10, {
    op  => \&op,
    op_nosort => \&op_nosort,
    ikegami => \&ikegami,
    ikegami_sort => \&ikegami,
}));

sub op { 
    my @refs = @allrefs[ sort { $a <=> $b } values %uni_refs ]
}
sub op_nosort { 
    my @refs = @allrefs[ values %uni_refs ]
}
sub ikegami {
    my %keep = map { $_ => 1 } values %uni_refs;
    my @refs = @allrefs[ grep $keep{$_}, 0..$#allrefs ];
}
sub ikegami_sort {
    my %keep = map { $_ => 1 } values %uni_refs;
    my @refs = @allrefs[ sort { $a <=> $b } grep $keep{$_}, 0..$#allre
+fs ];
}

[download]

In reply to Re^2: Code Interpretation by wanna_code_perl
in thread Code Interpretation by Perl_Ally

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.