Benchmarks

[Kai-Uwe Bux]

Re: Benchmarks

Jerry Coffin wrote:

In article <49163374.B0380 220@yahoo.com>, cbfalconer@yaho o.com says...
>
[ ... ]
>

>The result is that for most cases quicksort will be the fastest
>sort. Right behind it are other O(nLOGn) methods. I prefer
>mergesort and data input in lists, because then I don't have to
>worry about the size to be sorted. In addition, mergesort is
>stable (quicksort is not).

>
The most common implementation of Quicksort for arrays is unstable --
but a Quicksort on an array _can_ be written to be stable if you want to
badly enough, and for a linked list, it's quite easy to make it stable.

My linguistic intuitions differ: Quicksort _is_ the algorithm published as
Algorithm 64 (and 63) by C.A.R. Hoare in the Communications of the ACM.
That algorithm sorts a sequence in place and is not stable. It makes
2n*log(n) comparisons on average and (1/3)n*log(n) exchanges on average.
Anything that is stable or deals with linked lists is an implementation of
a _different_ algorithm (and probably has different average complexities).

I am not saying that there are no refinements or other algorithms based on
similar ideas. Some of these algorithms are stable and some apply to linked
lists. Also, I am not a native speaker of English. Nonetheless, I feel that
algorithms have a certain identity (which makes it meaningfull to say that
a certain sorting algorithm is stable); and that implementations of an
algorithm must preserve that identity and the associated characteristics to
count as implementations _of_ that algorithm.


Best

Kai-Uwe Bux

[Juha Nieminen]

Re: Benchmarks

CBFalconer wrote:

>For example quicksort is O(n^2). (Don't believe what people say.
>It *is* O(n^2), period.)

>
I suspect you know what you are talking about, but you are leaving
the wrong impression. The sort of sequence that produces O(n*n)
quicksort performance is extremely rare, and very slight controls
make it even rarer (such as selecting the median of 3 items as the
value to partition about).

The purpose of the big-O notation is not to tell how well an algorithm
behaves in average or in most cases. It's a pure upper bound to the
asymptotic behavior of the algorithm.

Of course if we get completely technical, the big-O notation assumes
that the input can have any size. If you put an upper limit to the size
of the input (for example an amount relative to the amount of memory
addressable by the CPU, eg. 2^64 bytes), all algorithms which end at
some point (ie. don't go into an infinite loop) immediately become O(1).

Of course saying "all terminating algorithms are O(1) in my computer"
is not very informative, which is why it's always implicitly assumed
that there is no set limit.

[Juha Nieminen]

Re: Benchmarks

Richard Harter wrote:

As others have pointed out, this is seriously misinformed. This
bit of folklore pops up every once in a while. Where does it
come from?

No, what is folklore is the custom of using the big-O notation to
describe *all* possible asymptotic behaviors of an algorithm. While that
may work colloquially, it's technically incorrect.

The big-O notation specifies the asymptotic upper bound for the
behavior of the algorithm. It does not specify anything else.

If the big-O notation could be used to describe *any* asymptotic
behavior for a given algorithm, then please explain to me how it differs
from the big-Omega and big-Theta notations. Wouldn't the big-O make
those obsolete?

[Juha Nieminen]

Re: Benchmarks

James Kanze wrote:

On Nov 8, 12:27 am, user923005 <dcor...@connx. comwrote:

>On Nov 7, 2:47 pm, Juha Nieminen <nos...@thanks. invalidwrote:
>Sure. If hash(x) == return 1; then bad behavior is to be
>expected. The assumption is of maximally cascade free hash
>functions like UMAC or Bob Jenkin's hash.

>
Do you have any references on those, particularly with an
implementation? All I found for UMAC was a reference to book,
and Bob Jenkin's seems more concerned with cryptographic hashing
than anything else. If these are standard and widely used
algorithms for look-up hashing, I'd like to add them to my set
of hashing benchmarks.
>
(Note that cryptographic hashing and look-up hashing have very
different constraints, and a good hash function for one isn't
necessarily a good hash function for the other. Also, in
look-up hashing, speed counts. Taking 10 times more time to get
1% better distribution on the average is a loss.)

I'm pretty sure Jenkin's hashing function (which uses the same
algorithm as his ISAAC random number generator) is faster than anything
you could ever create yourself, having even a fraction of the same quality.

[Andre Kostur]

Re: Benchmarks

Juha Nieminen <nospam@thanks. invalidwrote in news:64%Rk.149$ O41.3
@read4.inet.fi:

CBFalconer wrote:

>>For example quicksort is O(n^2). (Don't believe what people say.
>>It *is* O(n^2), period.)

>>
>I suspect you know what you are talking about, but you are leaving
>the wrong impression. The sort of sequence that produces O(n*n)
>quicksort performance is extremely rare, and very slight controls
>make it even rarer (such as selecting the median of 3 items as the
>value to partition about).

>
The purpose of the big-O notation is not to tell how well an algorithm
behaves in average or in most cases. It's a pure upper bound to the
asymptotic behavior of the algorithm.

Not necessarily true. The big-O could refer to best-case, average, worst-
case, or anything in between. You just need to specify it. As I recall,
quicksort is O(n lg n) in the average case, O(n^2) worst case. Both say
something interesting about the algorithm.

[Juha Nieminen]

Re: Benchmarks

Andre Kostur wrote:

Not necessarily true. The big-O could refer to best-case, average, worst-
case, or anything in between. You just need to specify it. As I recall,
quicksort is O(n lg n) in the average case, O(n^2) worst case. Both say
something interesting about the algorithm.

While you can say that colloquially, it's formally quite shaky.

In computational complexity theory big-O is not a generic notation
used to describe some asymptotic behavior of an algorithm. It's used to
specify an upper bound to the asymptotic behavior of an algorithm.

Saying, for example, "insertion sort is O(2^n)" is completely valid.
O(n^100) is equally valid. The big-O notation does not even require for
the upper bound to be tight. Any upper bound is valid as long as the
algorithm never behaves slower than that. However, saying "insertion
sort is O(n)" is not valid because with some inputs insertion sort
performs asymptotically more steps than that.

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

Likewise the big-Omega notation is used to set a lower bound to the
asymptotic behavior of an algorithm. For example if you say "insertion
sort is Omega(n)", you are telling that insertion sort never performs
less steps than an amount linearly relative to the size of the input.

Saying "the best case for insertion sort is O(n)" is exactly as silly
as saying "the worst case for insertion sort is Omega(n^2)". They don't
make sense as bounds in these sentences. They are misused to describe
some special cases.

[Pete Becker]

Re: Benchmarks

On 2008-11-10 14:43:06 -0500, Juha Nieminen <nospam@thanks. invalidsaid:

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

You can't ignore the qualifier "on average", which implies some
constraints on input sequences. Yes, it's O(n^2) for some input
sequences, but if you rule out those input sequences, then it's
O(nlogn), and that's all that "on average" means. Big-oh notation tells
you what happens when the input sequence gets long. It doesn't tell you
anything about the contents of input sequences.

--
Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com) Author of "The
Standard C++ Library Extensions: a Tutorial and Reference
(www.petebecker.com/tr1book)

[Richard Harter]

Re: Benchmarks

On Mon, 10 Nov 2008 18:36:00 GMT, Juha Nieminen
<nospam@thanks. invalidwrote:

>Richard Harter wrote:

>As others have pointed out, this is seriously misinformed. This
>bit of folklore pops up every once in a while. Where does it
>come from?

>
No, what is folklore is the custom of using the big-O notation to
>describe *all* possible asymptotic behaviors of an algorithm. While that
>may work colloquially, it's technically incorrect.
>
The big-O notation specifies the asymptotic upper bound for the
>behavior of the algorithm. It does not specify anything else.
>
If the big-O notation could be used to describe *any* asymptotic
>behavior for a given algorithm, then please explain to me how it differs
>from the big-Omega and big-Theta notations. Wouldn't the big-O make
>those obsolete?

Please read the wikipedia article on big O notation at

http://en.wikipedia.org/wiki/Big_O_notation

The fundamental error in your understanding is that you are
thinking about the big-o etc notation as statements about
algorithms; they are statements about functions. Here are some
of the functions associated with an algorithm:

The minimum time used for an input data set of size n.
The maximum time used for an input data set of size n.
The average time used for an input data set of size n, averaged
over all inputs.

The minimum space used for an input data set of size n.
The maximum space used for an input data set of size n.
The average space used for an input data set of size n, averaged
over all inputs.

These are all separate functions. We can make separate
statements about their asymptotic behaviours. Thus we can say
that the average time used by the quicksort algorithm is
O(n*log(n)) and the worst case is O(n^2).

The big-O notation says that the function inside O() is an
asymptotic bound; it isn't necessarily a best bound. In fact it
is quite proper to say that the average time for quicksort is
O(n^2), O(n^3), O(n^4), etc, as these are all valid upper bounds.

Big-O does not make big omega or big theta obsolete. Big omega
is any function asymptotically below the function of interest.
Big theta says (loosely) that big theta function has the same
asymptotic behaviour as the function it is being compared to.

Please, you are seriously misinformed, and are being very
dogmatic about your misunderstandin g. Please read the wikipedia
article; I appreciate that it is a little dense, but it is clear
enough.


Richard Harter, cri@tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.

[Richard Tobin]

Re: Benchmarks

In article <e90Sk.195$O41. 164@read4.inet. fi>,
Juha Nieminen <nospam@thanks. invalidwrote:

In computational complexity theory big-O is not a generic notation
>used to describe some asymptotic behavior of an algorithm. It's used to
>specify an upper bound to the asymptotic behavior of an algorithm.

I think you are conflating two different upper bounds here. If we say
the function f(n) is O(n) is we mean that there is a k such that
|f(n)| <= kn for sufficiently large n. That is, kn bounds f(n) over
the range of sufficiently large n.

When we apply this to sort algorithms, what is the function f? It
might be the worst-case time to sort a set of size n, or the average
time. So it's perfectly reasonable to say that quicksort is
O(n log(n)) on average and O(n^2) in the worst case, meaning that the
average time to sort a set of n elements is O(n log(n)) and the
worst-case time is O(n^2).

Or f might be the time to sort a set S, in which case we can say that
it is O(|S|^2), since now we are taking a bound over all the sets.
If we implicitly take n to be |S|, we can reasonably say that quicksort
is O(n^2).

-- Richard
--
Please remember to mention me / in tapes you leave behind.

[Antoninus Twink]

Re: Benchmarks

On 10 Nov 2008 at 21:11, Richard Harter wrote:

On Mon, 10 Nov 2008 18:36:00 GMT, Juha Nieminen <nospam@thanks. invalidwrote:

> The big-O notation specifies the asymptotic upper bound for the
>>behavior of the algorithm. It does not specify anything else.
>>

Please read the wikipedia article on big O notation at

http://en.wikipedia.org/wiki/Big_O_notation

>
The fundamental error in your understanding is that you are thinking
about the big-o etc notation as statements about algorithms; they are
statements about functions.

[snip]

Please, you are seriously misinformed, and are being very dogmatic
about your misunderstandin g. Please read the wikipedia article

He is *so* misinformed and *so* dogmatic that he might decide that the
Wikipedia article is wrong and he's right, and vandalize the article.
It might be worth keeping an eye on it.

[Phil Carmody]

Re: Benchmarks

Juha Nieminen <nospam@thanks. invalidwrites:

Even if you say "quicksort is O(n lg n) in average", the upper bound
is still not correct. Even when measuring average behavior quicksort
will behave slower than (n lg n) with some inputs, and thus the given
upper bound is incorrect.

There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[CBFalconer]

Re: Benchmarks

Jerry Coffin wrote:

cbfalconer@yaho o.com says...
>
[ ... ]
>

>The result is that for most cases quicksort will be the fastest
>sort. Right behind it are other O(nLOGn) methods. I prefer
>mergesort and data input in lists, because then I don't have to
>worry about the size to be sorted. In addition, mergesort is
>stable (quicksort is not).

>
The most common implementation of Quicksort for arrays is unstable
-- but a Quicksort on an array _can_ be written to be stable if
you want to badly enough, and for a linked list, it's quite easy
to make it stable.

Not so. Extending Quicksort to include multiple fields does not
count. Mergesort remains simple. For an example, look at the
usage examples in hashlib (on my site).

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home .att.net>
Try the download section.

[Juha Nieminen]

Re: Benchmarks

Phil Carmody wrote:

Juha Nieminen <nospam@thanks. invalidwrites:

> Even if you say "quicksort is O(n lg n) in average", the upper bound
>is still not correct. Even when measuring average behavior quicksort
>will behave slower than (n lg n) with some inputs, and thus the given
>upper bound is incorrect.

>
There are no "some inputs" being forgotten about when such a
statement is being made. "On average" has included all inputs
(weighted by their probability).

But in that case the given upper bound is incorrect.

Perhaps if you say "quicksort is amortized (n lg n)-time", that might
be closer to the truth.

[Phil Carmody]

Re: Benchmarks

Juha Nieminen <nospam@thanks. invalidwrites:

Phil Carmody wrote:

>Juha Nieminen <nospam@thanks. invalidwrites:

>> Even if you say "quicksort is O(n lg n) in average", the upper bound
>>is still not correct. Even when measuring average behavior quicksort
>>will behave slower than (n lg n) with some inputs, and thus the given
>>upper bound is incorrect.

>>
>There are no "some inputs" being forgotten about when such a
>statement is being made. "On average" has included all inputs
>(weighted by their probability).

>
But in that case the given upper bound is incorrect.

Bound of _what_? Define _precisely_ what function you are
talking about. It appears you've never heard the concept
of averaging. If so, you're going to be well out of depth
in this thread.

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.

[Phil Carmody]

Re: Benchmarks

Juha Nieminen <nospam@thanks. invalidwrites:

However, what is "average" input in the case of quicksort?

ARGH! There is not an average input. That's crank speak.
I've seen your type on sci.math, and you'll be talking about
"infinite numbers" or the "probabilit y of a number N being
prime". There is no average input, there's an average over
all inputs (with appropriate weightings, in this case
presumably uniform).

If you are lead to conclusions that seem to not make sense,
then it might just be that your premises and preconceptions
are all messed up.

Phil
--
I tried the Vista speech recognition by running the tutorial. I was
amazed, it was awesome, recognised every word I said. Then I said the
wrong word ... and it typed the right one. It was actually just
detecting a sound and printing the expected word! -- pbhj on /.