May 12, 2004
"Jan-Eric Duden" <jeduden@whisset.com> wrote in message news:c7sioo$cvh$1@digitaldaemon.com...
>
> > You're welcome. You should also note that arrays have a built-in sort property, which uses quicksort. It'll blow away heapsort <g>. Doing that cuts the sort time on my machine from 453 ms to 63 ms. Source attached.
> >
> I am wondering if the difference of execution time is the result of using different algorithms (quicksort or heapsort). Or can the code for the sort property be better optimized than a "normal" implementation of a sort algorithm?

I'd have to do testing to make sure, but I'm pretty sure it's due to quicksort being algorithmically superior. One of the reasons I built sort into arrays is because people implement inefficient sorts over and over, and I wanted to make it real easy to use the best algorithm. (A job I had once was to optimize a large program written by others; in poking around in it I found 3 different hacky implementations of bubblesort. Replaced them all with a call to C's qsort(), and I was an instant hero for the speedup <g>.)


May 12, 2004
> I'd have to do testing to make sure, but I'm pretty sure it's due to quicksort being algorithmically superior. One of the reasons I built sort into arrays is because people implement inefficient sorts over and over,
and
> I wanted to make it real easy to use the best algorithm. (A job I had once was to optimize a large program written by others; in poking around in it
I
> found 3 different hacky implementations of bubblesort. Replaced them all with a call to C's qsort(), and I was an instant hero for the speedup
<g>.)

I thought qsort and heapsort work about at the same speed.

I thought the most important difference between a heapsort and q-sort
implementation in C is the order of the algorithms:
- heapsort has roughly the same performance for all array instanciations
O(n*log n)
- qsort is a lot slower O(n^2) on some instanciations and a lot faster on
almost sorted arrays O(n). the average is of course: O(n*log n)

Maybe the difference is that the C q-sort implementation is highly
optimizied and the heapsort implementation that was
used is not?


May 12, 2004
"Jan-Eric Duden" <jeduden@whisset.com> wrote in message news:c7spim$n4h$1@digitaldaemon.com...
> > I'd have to do testing to make sure, but I'm pretty sure it's due to quicksort being algorithmically superior. One of the reasons I built
sort
> > into arrays is because people implement inefficient sorts over and over,
> and
> > I wanted to make it real easy to use the best algorithm. (A job I had
once
> > was to optimize a large program written by others; in poking around in
it
> I
> > found 3 different hacky implementations of bubblesort. Replaced them all with a call to C's qsort(), and I was an instant hero for the speedup
> <g>.)
>
> I thought qsort and heapsort work about at the same speed.
>
> I thought the most important difference between a heapsort and q-sort
> implementation in C is the order of the algorithms:
> - heapsort has roughly the same performance for all array instanciations
> O(n*log n)
> - qsort is a lot slower O(n^2) on some instanciations and a lot faster on
> almost sorted arrays O(n). the average is of course: O(n*log n)
>
> Maybe the difference is that the C q-sort implementation is highly
> optimizied and the heapsort implementation that was
> used is not?


Both quicksort and heapsort are O(n log n) on average but the constants involved in Quicksort are much better. Quicksort though depends a lot on whether the partitioning subroutine is balanced. The differences are discussed at length in Introduction to Algorithms by Cormen, Leiserson and Rivest ( http://theory.lcs.mit.edu/~clr/ )

-- 
Christopher Diggins
http://www.cdiggins.com
http://www.heron-language.com


May 12, 2004
"Kevin Bealer" <Kevin_member@pathlink.com> wrote in message news:c7rkjh$2216$1@digitaldaemon.com...
> In article <c7rhdv$1t4h$1@digitaldaemon.com>, christopher diggins says... ..
> >You are correct, but Vector2D is used to demonstrate a class that is run-time polymorphic but happens to be used in a non-polymorphic manner.
I
> >could easily add to the demo a modification that forces the issue of polymorphism, but I thought it would complicate things too much. Do you recommend that I change the demo to make this more explicit?
>
> Heron's approach of non-inheritance binding is interesting;  I take it
there is
> a global dispatch table with pointers to all methods appearing in
non-deduceable
> cases?

Close, there are lots of small tables created.

> I think the demo you have is good as far as it goes.  But I would be more interested to know what happens in both cases for both languages: i.e. C++ run-time and compile-time and Heron run-time and compile-time.  If Heron
can
> outperform in *both* cases, that would be much more impressive.

Good point.

> But in (performance oriented code) in a language like C++, virtual-ness is usually used only when compile time binding is difficult to achieve.

In retrospect, I am starting to be of the opinion that the example may fact rigged as you mentioned. There is no way that I can justify a design that uses ICompare as a class with virtual functions.

-- 
Christopher Diggins
http://www.cdiggins.com
http://www.heron-language.com


May 12, 2004
christopher diggins wrote:

<snip>
>> - qsort is a lot slower O(n^2) on some instanciations and a lot faster on almost sorted arrays O(n). the average is of course: O(n*log n)

Can you give an example of an O(n) case of quicksort?

>> Maybe the difference is that the C q-sort implementation is highly
>> optimizied and the heapsort implementation that was used is not?
> 
> Both quicksort and heapsort are O(n log n) on average
<snip>

Yes, but in the worst case, heapsort wins O(n log n) to O(n^2).

When benchmarking a sorting algorithm, it's helpful to try a number of random cases, as well as the control cases of already sorted and already sorted backwards.

If you're benchmarking algorithms, rather than compilers or languages, you should try to use the same compiler, the same language and the same compiler options.  As such, it makes limited sense to compare a ready-made C library function of one algorithm with your own implementation of another.

Of course, if you're comparing languages/compilers, you should compare implementations of the same algorithm, and set as similar levels of optimisation as possible (ITMS).

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.
May 12, 2004
>
> Can you give an example of an O(n) case of quicksort?
A sorted array. You only get O(n) in a slightly modified version of q-sort that quits if no swaps occured.

>
> >> Maybe the difference is that the C q-sort implementation is highly optimizied and the heapsort implementation that was used is not?
> >
> > Both quicksort and heapsort are O(n log n) on average
> <snip>
>
> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2).
Yep, that's why sometimes heapsort is preferred over quicksort.

My question was more related to the constants. I wasn't aware that heapsort is that much slower.


May 12, 2004
Jan-Eric Duden wrote:

>>Can you give an example of an O(n) case of quicksort?
> 
> A sorted array. You only get O(n) in a slightly modified version of q-sort
> that quits if no swaps occured.

By 'swaps' do you mean the swapping of an element with the hole into which the key element is to go?

How can one element being already in the right place imply that the whole array is sorted?

<snip>
> Yep, that's why sometimes heapsort is preferred over quicksort.
> 
> My question was more related to the constants. I wasn't aware that heapsort
> is that much slower.

What constants?

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.
May 12, 2004
Stewart Gordon wrote:
> 
> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2).

But some versions of heapsort need a considerable memory overhead to run.  In general, quicksort is the better choice for average sorting situations.  People with special needs generally also know how to code for those needs :)

Sean
May 12, 2004
Sean Kelly wrote:

> Stewart Gordon wrote:
>
>>
>> Yes, but in the worst case, heapsort wins O(n log n) to O(n^2).
>
>
> But some versions of heapsort need a considerable memory overhead to run.  In general, quicksort is the better choice for average sorting situations.  People with special needs generally also know how to code for those needs :)
>
> Sean

Right!  Even sort algorithms like short-circuit bubble sort can be useful if they are used in right application.  Short-circuit bubble sort is most useful when you know that most-of-the the array is sorted because then you get o(n). With standard quicksort you'd get O(n^2) for a sorted array.

-- 
-Anderson: http://badmama.com.au/~anderson/
May 12, 2004
J Anderson wrote:

<snip>
> Right!  Even sort algorithms like short-circuit bubble sort can be useful if they are used in right application.  Short-circuit bubble sort is most useful when you know that most-of-the the array is sorted because then you get o(n). With standard quicksort you'd get O(n^2) for a sorted array.

Even better for nearly sorted data is bidirectional short-circuit bubble sort.

Stewart.

-- 
My e-mail is valid but not my primary mailbox, aside from its being the unfortunate victim of intensive mail-bombing at the moment.  Please keep replies on the 'group where everyone may benefit.