Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl-Sensitive Sunglasses
 
PerlMonks  

Best way to sum an array?

by Anonymous Monk
on May 24, 2017 at 15:06 UTC ( [id://1191095]=perlquestion: print w/replies, xml ) Need Help??

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

How do I pick the "best way" to do something? In particular, I want the fastest way, using the fewest resources, to sum up the values in an array of arbitrary length. I could do it in a loop with a bucket, I could do it recursively, I could do it with a join and an eval, etc. What's the "best" way? Is there a "better" way? How do I measure? How do I pick?
# Iterative sub SumArryItr { my $agg = 0; $agg += $_ for @_; return $agg } # Recursive use feature 'current_sub'; sub SumArryRcs { 1==@_?$_[0]:1>@_?die:shift(@_)+__SUB__->(@_) } # Eval Trick sub SumArryEvl { eval join "+", @_ } # Test my @array = ( -249, 0, 74, 65, 80, 72 ); print "Sum: ", join( ", ", @array ), "\n"; print "Itr: ", SumArryItr( @array ), "\n"; print "Rcs: ", SumArryRcs( @array ), "\n"; print "Evl: ", SumArryEvl( @array ), "\n";
merci

Replies are listed 'Best First'.
Re: Best way to sum an array?
by haukex (Archbishop) on May 24, 2017 at 15:45 UTC

    List::Util (the XS version) beats them all:

    Rate recursive recursive2 eval iterative list +util recursive 1244/s -- -4% -68% -97% - +100% recursive2 1297/s 4% -- -67% -97% - +100% eval 3930/s 216% 203% -- -91% +-99% iterative 42708/s 3332% 3192% 987% -- +-85% listutil 281788/s 22544% 21622% 7071% 560% + --

    The recursive approach is not a good solution, as I had to disable warnings on deep recursion and as the array gets longer it really blows up... only for short arrays does it outperform the eval version.

      > as I had to disable warnings on deep recursion and as the array gets longer it really blows up...

      FWIW tailcall with goto &sub

      it's also 30% faster than normal recursion

      Rate recursive recursive2 recursive3 eval iterativ +e listutil recursive 184/s -- -4% -24% -46% -98 +% -100% recursive2 192/s 5% -- -20% -43% -98 +% -100% recursive3 240/s 31% 25% -- -29% -98 +% -100% eval 339/s 84% 76% 41% -- -97 +% -100% iterative 10240/s 5472% 5225% 4159% 2923% - +- -95% listutil 205922/s 111960% 106979% 85548% 60701% 1911 +% --

      I had a version which used $_[0] instead of aggregating in a closure, but it destroyed the aliased array and made the cmpthese() impossible.

      Cheers Rolf
      (addicted to the Perl Programming Language and ☆☆☆☆ :)
      Je suis Charlie!

      Nice. That module does the work in native compiled code, so of course it's fastest. I didn't know about that module. This is clearly best.
      #1053
      merci

        Then you should immediately familiarise yourself with it, and its sister module Scalar::Util. They are two of the most useful modules included in the Perl core.

        A module is almost always a good solution, if not the best, for any problem. This is especially true if you consider your own time as one of the resources you want to minimize.
        Bill
      > The recursive approach is not a good solution, as I had to disable warnings on deep recursion and as the array gets longer it really blows up... only for short arrays does it outperform the eval version.

      The beauty of recursions come into play if you can split into several branches.

      Deep recursion becomes very unlikely and eval is outperformed.

      Perl Version: 5.016003 Array Length: 10000 Expected result: 50005000 Rate recursive recursive3 eval rec_split iterative + listutil recursive 7.44/s -- -19% -89% -91% -100% + -100% recursive3 9.16/s 23% -- -86% -89% -100% + -100% eval 67.6/s 808% 638% -- -19% -97% + -100% rec_split 83.8/s 1026% 815% 24% -- -96% + -100% iterative 2145/s 28722% 23322% 3073% 2461% -- + -94% listutil 36669/s 492642% 400327% 54142% 43678% 1610% + --

      Even that the total number of additions is still the same, this shows how sub-calls and copying arrays are braking in Perl.

      There is still room for more tuning:

      • don't copy arrays just indices
      • replace sub-calls with goto's/loop constructs and a result-stack
      • replace division by 2 with bit-shift

      But of course it's impossible to achieve the performance of the C version in this particular case!

      Cheers Rolf
      (addicted to the Perl Programming Language and ☆☆☆☆ :)
      Je suis Charlie!

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 15:14 UTC

    How do I measure?

    «The Crux of the Biscuit is the Apostrophe»

    Furthermore I consider that Donald Trump must be impeached as soon as possible

      Nice. This gets me the following chart, but I'm not sure I understand what it means.
               Rate   Evl   Rcs   Itr                                                                                                                                                
      Evl  115745/s    --  -84%  -93%                                                                                                                                                
      Rcs  729138/s  530%    --  -55%                                                                                                                                                
      Itr 1612898/s 1293%  121%    --
      

      I think that means the Itr version is an order of magnitude (16x) better than the Rcs version, right? And that the Rcs version is 7 times better than the Evl version. If so, then the answer is clear.
      merci

        Left column sorted from slow to fast. It shows the number of iterations.

        «The Crux of the Biscuit is the Apostrophe»

        Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 16:01 UTC

    Or just say:

    use Time::HiRes qw( time ); my $start = time; # your code here printf "Took %.3f seconds\n", time - $start;

    For deeper insights see Devel::NYTProf

    Good advice was given above.

    Regards, Karl

    «The Crux of the Biscuit is the Apostrophe»

    Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by thanos1983 (Parson) on May 24, 2017 at 15:59 UTC
Re: Best way to sum an array?
by vrk (Chaplain) on May 25, 2017 at 12:34 UTC

    There's a great discussion about summation algorithms in Accuracy and Stability of Numerical Algorithms by Nicholas Higham (2002), chapter 4. The focus is naturally on numerical accuracy, but there are lots of ideas and references for recursive, parallel and distributed summation algorithms. Or have a look at some of the CUDA resources by nVidia on speedy summation algorithms on GPUs.

    I would say you really don't need to worry about either speed or accuracy of summation in "normal" circumstances. It becomes an issue only in a few special cases: 1) very large volumes of data (say array size of gigabytes or terabytes) typical in supercomputing and high-performance scientific or financial computing; 2) very strict numerical accuracy requirements (accuracy and speed are often opposites); 3) very resource limited computing environment (like a microcontroller). Of course, if you're summing four billion floating point numbers subject to relative error of the order of machine epsilon on a microcontroller, then you need to worry about these things...

      I would say you really don't need to worry about either speed or accuracy of summation in "normal" circumstances.

      Often the question "Which is the fastest way" can be translated into "The way I doing it now is really slow; how can I improve it."

      With List::Util::sum() running 100x faster than the best pure perl equivalent, why wouldn't you use it even if you don't need the speed; and for some of the methods attempted by beginners and even experienced programmers new to Perl -- eg. the recursive solution in the OP -- sum() can be almost 1000 times faster. Perl sucks at recursion.


      With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority". The enemy of (IT) success is complexity.
      In the absence of evidence, opinion is indistinguishable from prejudice. Suck that fhit
        With List::Util::sum() running 100x faster than the best pure perl equivalent, why wouldn't you use it even if you don't need the speed

        It's a good question. The only answer which springs to mind is that you want to avoid loading List::Util in the first place because:

        • You're in a constrained environment and don't have the RAM to spare
        • You are actually concerned about speed but it's faster to run a short script without loading List::Util if the arrays being summed are tiny
        • You are in some environment where XS isn't feasible so you're stuck with the PP version (although this still isn't really a reason not to use it on its own)

        They are all edge cases anyway. And of course if you are one of the 99% who do have enough RAM etc. to load List::Util you get all the other good stuff in that module other than sum() essentially for free.

        In summary: yes, I'd use it everywhere unless there's a demonstrable penalty.

Re: Best way to sum an array?
by karlgoethebier (Abbot) on May 24, 2017 at 16:12 UTC

    See also Re^6: Question on Regex about the output of Benchmark.

    «The Crux of the Biscuit is the Apostrophe»

    Furthermore I consider that Donald Trump must be impeached as soon as possible

Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 16:32 UTC
Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 15:21 UTC
    That recursive sub is ugly. Could be cleaner:
    sub SumArryRcs { @_ ? shift(@_) + __SUB__->(@_) : 0 }
Re: Best way to sum an array?
by Anonymous Monk on May 24, 2017 at 17:35 UTC
    'How do I pick the "best way" to do something?'

    You wait until it becomes a problem. No really, this isn't a zombie invasion. Your need is part of some greater need, and that is you what you focus on. When the time comes to optimize, you Benchmark your candidates because THEN AND ONLY THEN will you have a concrete reason. Everything else is theoretical and probably will be rendered MOOT when reality rears its head at a much later date.

      I'm working on Acme::GlasgowKiss.

      «The Crux of the Biscuit is the Apostrophe»

      Furthermore I consider that Donald Trump must be impeached as soon as possible

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://1191095]
Approved by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others lurking in the Monastery: (4)
As of 2024-04-18 04:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found