View mode: basic / threaded / horizontal-split · Log in · Help
May 12, 2004
Re: D performance compared with other languages
"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
Re: D performance compared with other languages
> 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
Re: D performance compared with other languages
"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
Re: D performance compared with other languages
"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
Re: D performance compared with other languages
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
Re: D performance compared with other languages
>
> 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
Re: D performance compared with other languages
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
Re: D performance compared with other languages
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
Re: D performance compared with other languages
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
Re: D performance compared with other languages
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.
1 2 3 4 5 6 7
Top | Discussion index | About this forum | D home