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

How is a O(NlogN) substitute for a O(2N) operation the "logical conclusion" of a thread that started out attempting to reduce the latter to O(3N/2)?

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.

Comment on Re^3: minimum, maximum and average of a list of numbers at the same time Download Code

Replies are listed 'Best First'.
Re^4: minimum, maximum and average of a list of numbers at the same time by Aristotle (Chancellor) on Nov 10, 2005 at 21:57 UTC
It’s not. Imagine an “of your approach” at the end of that sentence. Besides, it may well be that this O(N + N long N) algorithm implemented in C is so much faster per step than the O(3N/2) approach implemented in Perl that you’ll need very long arrays before the “fast” algorithm beats the “slow” one. But I haven’t bothered to benchmark, so this guess is probably wrong (as a lot of my guesses about performance have been in the past). Not that I care too much. If I had a desire to do this quickly, I’d patch List::MoreUtils. It’s a numbercrunch-ish problem, and I find that trying to solve those in Perl is rarely intuitive or particularly didactic (other than in learning about the particular quirks of the implementation of `perl` that we happen to have). In contrast, doing them in C is often straightforwardly optimisable on the abstract algorithmic level without surprises in implementation. At most, I have a vague desire to see is where the breakeven point between the O(N log N) sort vs the O(2N) `min`+`max` approaches is. Makeshifts last the longest.	[reply]

Replies are listed 'Best First'.

Re^4: minimum, maximum and average of a list of numbers at the same time
by Aristotle (Chancellor) on Nov 10, 2005 at 21:57 UTC

It’s not. Imagine an “of your approach” at the end of that sentence.

Besides, it may well be that this O(N + N long N) algorithm implemented in C is so much faster per step than the O(3N/2) approach implemented in Perl that you’ll need very long arrays before the “fast” algorithm beats the “slow” one. But I haven’t bothered to benchmark, so this guess is probably wrong (as a lot of my guesses about performance have been in the past).

Not that I care too much. If I had a desire to do this quickly, I’d patch List::MoreUtils. It’s a numbercrunch-ish problem, and I find that trying to solve those in Perl is rarely intuitive or particularly didactic (other than in learning about the particular quirks of the implementation of perl that we happen to have). In contrast, doing them in C is often straightforwardly optimisable on the abstract algorithmic level without surprises in implementation.

At most, I have a vague desire to see is where the breakeven point between the O(N log N) sort vs the O(2N) min+max approaches is.

Makeshifts last the longest.

[reply]