Beefy Boxes and Bandwidth Generously Provided by pair Networks
Clear questions and runnable code
get the best and fastest answer
 
PerlMonks  

Re: Best way to sum an array?

by vrk (Chaplain)
on May 25, 2017 at 12:34 UTC ( #1191207=note: print w/replies, xml ) Need Help??


in reply to Best way to sum an array?

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...

Replies are listed 'Best First'.
Re^2: Best way to sum an array?
by BrowserUk (Patriarch) on May 25, 2017 at 12:43 UTC
    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.

        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

        Hm.

        1. constrained environment: I guess 600k might make a difference somewhere.

          Hard to see where though. Most phones have 4GB and even the original Raspberry Pi had 512MB.

        2. "faster ... without loading List::Util: Given WithListUtil.pl:
          #! perl -sl use List::Util qw[ sum ]; our $N //= 10; print sum( 1 .. $N );

          And WithoutListUtil.pl:

          #! perl -sl #use List::Util qw[ sum ]; our $N //= 10; my $t = 0; $t += $_ for 1 .. $N; print $t;

          Darned if I can find any significant difference for as few as 3 numbers to add. Pretty consistently 4-5/100ths for both to start perl, count the numbers and return to the prompt:

          [16:27:32.60] C:\test>for /l %i in (1,1,10) do WithListUtil.pl -N=3 [16:27:55.68] C:\test>WithListUtil.pl -N=3 [16:27:55.73] C:\test>WithListUtil.pl -N=3 [16:27:55.79] C:\test>WithListUtil.pl -N=3 [16:27:55.85] C:\test>WithListUtil.pl -N=3 [16:27:55.90] C:\test>WithListUtil.pl -N=3 [16:27:55.95] C:\test>WithListUtil.pl -N=3 [16:27:56.00] C:\test>WithListUtil.pl -N=3 [16:27:56.05] C:\test>WithListUtil.pl -N=3 [16:27:56.10] C:\test>WithListUtil.pl -N=3 [16:27:56.15] C:\test>WithListUtil.pl -N=3 [16:27:56.20] C:\test>for /l %i in (1,1,10) do WithoutListUtil.pl -N=3 [16:28:22.44] C:\test>WithoutListUtil.pl -N=3 [16:28:22.49] C:\test>WithoutListUtil.pl -N=3 [16:28:22.54] C:\test>WithoutListUtil.pl -N=3 [16:28:22.59] C:\test>WithoutListUtil.pl -N=3 [16:28:22.63] C:\test>WithoutListUtil.pl -N=3 [16:28:22.67] C:\test>WithoutListUtil.pl -N=3 [16:28:22.71] C:\test>WithoutListUtil.pl -N=3 [16:28:22.76] C:\test>WithoutListUtil.pl -N=3 [16:28:22.80] C:\test>WithoutListUtil.pl -N=3 [16:28:22.84] C:\test>WithoutListUtil.pl -N=3 [16:28:22.88] C:\test>

          It's hard to see the loading time of List::Util being a significant factor in any real code.

        3. XS isn't feasible so you're stuck with the PP version:

          I thought it came with the core for most distributions. I 'spose someone somewhere might be running a bastardized, cut-down version.


        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
      • You want to learn about algorithms and Perl's limitations?

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others romping around the Monastery: (5)
As of 2023-02-01 16:39 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    I prefer not to run the latest version of Perl because:







    Results (11 votes). Check out past polls.

    Notices?