Re^2: Code Interpretation

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 = 1x10⁵.

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

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

N = 1x10⁵

                 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 = 1x10⁶

                  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]

Comment on Re^2: Code Interpretation Select or Download Code

Replies are listed 'Best First'.
Re^3: Code Interpretation by soonix (Chancellor) on Jul 30, 2014 at 08:45 UTC
Your code will not produce the same output as the OP's. As long as grep doesn't change the order of `0..$#allrefs`, I'd expect the result to be in the same order as by the OP. About the performance point, this depends on wether `%uni_refs` has the same size as `@allrefs`, or not. If `%uni_refs` is just a small part of `@allrefs`, ikegami's solution is faster even with the additional sort... Update: Oops, I should take a course in reading benchmarks ... map+grep is slower, anyway. Yet I'm not completely convinced. There must be an edge case where it is faster :-)	[reply] [d/l] [select]
Re^4: Code Interpretation by wanna_code_perl (Friar) on Jul 30, 2014 at 11:30 UTC
As long as grep doesn't change the order of 0..$#allrefs, I'd expect the result to be in the same order as by the OP. It wouldn't of course. You are right; I grossly misread ikegami's code thinking that he was iterating over the unsorted result of keys (`%keep`), when in fact he was iterating over the indicies of the original array. (Sorry, ikegami, I should've known better!) And the rest of this node has nothing to do with that. At least my own mistake did encourage me to do some potentially enlightening benchmarking. It's always interesting to me when even though O(N) beats O(N log N) on a graph when N is large, how large N needs to be depends on the smaller powers of the function (never shown in big-O notation, big-Theta, yes). The bigger the constant, the bigger N must be to overcome it for the "faster" algorithm to win out, especially in Perl, which as I found out years ago, has some pretty huge constants in even the simplest of operations (but much smaller constants for many of the more complex operations like sort, which are heavily optimized in C). What I'm saying is, performance is cute, performance is fun, and performance is often irrelevant (within a few orders of magnitude, anyway), but for me personally, obtaining surprising results about performance is one thing that played a significant part in pushing me to learn how to write better Perl code, and not just more C code translated to run in the `perl` interpreter.	[reply] [d/l] [select]