Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Re^4: minimum, maximum and average of a list of numbers at the same time

by LucaPette (Friar)
on Nov 10, 2005 at 17:04 UTC ( #507463=note: print w/replies, xml ) Need Help??


in reply to Re^3: minimum, maximum and average of a list of numbers at the same time
in thread minimum, maximum and average of a list of numbers at the same time

thank you BrowserUk your replies are all very helpful for me, especially about testing the input parameter. Only a little disappointment... regarding the number of comparisons i believe that your code doesn't agree with my way of counting comparisons only why it counts also the comparisons in the while condition, the number 3(n/2) refers to comparisons among elements of the input list.
  • Comment on Re^4: minimum, maximum and average of a list of numbers at the same time

Replies are listed 'Best First'.
Re^5: minimum, maximum and average of a list of numbers at the same time
by BrowserUk (Patriarch) on Nov 10, 2005 at 17:38 UTC
    Only a little disappointment... regarding the number of comparisons i believe that your code doesn't agree with my way of counting comparisons only why it counts also the comparisons in the while condition, the number 3(n/2) refers to comparisons among elements of the input list.

    I understand your point, but it is still a comparison, and it costs just as much as the other comparisons, and if other algorithms don't require that extra comparison (in the while loop), it has to count against the overall algorithm costs.

    If you re-coded that part of your algorithm to be

    # while( $i < @{ $ref } ) { for my $i ( 0 .. $#$ref ) {

    Then you would avoid that comparison.

    Or rather, the comparison still exists, the loop has to be terminated somehow (as is true of the other algorithms), but the comparison is being made at the C/assembler level rather than the Perl level. The difference is that perfroming the comparison at the Perl level requires a lot of extra processing to extract the values from Perl variables and getting them into appropriate registers for the comparison to be made, whereas doing at the C-level, the values are probably in registers already, or can be more cheaply loaded from local stack temporaries.

    Efficiency in Perl is nearly always about allowing or pursuading Perl to do as much of the work as possible, which generally means using as few opcodes as possible.

    For your algorithm to be beneficial, you would really need to code it in C, XS or maybe even assember. Comparisons are simply too cheap relative to memory accesses and stack manipulations for the 25% reduction in comparisons to be significant if achieving requires even a moderate increase of either.


    Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
    Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
    "Science is about questioning the status quo. Questioning authority".
    In the absence of evidence, opinion is indistinguishable from prejudice.
      It seems to me that Knuth's discussion of the algorithm was actually talking about floating point comparisons. That's why the loop control comparison was ignored by him.

        That makes sense, although it would be an interesting exercise to compare both algorithms, written in C, with a good optimising compiler (Intel's on x86 for example).

        With ubiquitous FP processors on-board modern cpus, the difference in costs between FP and integer operations has narrowed considerably, esp. when pipelining can be used to good advantage.

        I've read some articles that make the case for dropping the distinctions between integer, float, & double in programming languages and just using the FP processors native size (80-bit on Intel) for all program-level numerical quantities. The slight drop in performance for heavy integer math can be more than compensated for, by removing all the decision points--what type of number is this? Does it need to be extended? Will it/did it overflow? etc.

        Perl threw the float away years ago, why not bin the (internal) integers as well, and make full use of the hardwares FP precision saving all the conversions that take place converting between 64-bit doubles and 80-bit internals.

        Makes perfect sense to me.


        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (3)
As of 2022-01-23 09:13 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    In 2022, my preferred method to securely store passwords is:












    Results (63 votes). Check out past polls.

    Notices?