Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #27524 > unrolled thread

A riddle with QSORT

Back to article view | Back to comp.lang.forth

Contents

  A riddle with QSORT albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-12-30 11:48 +0000
    Re: A riddle with QSORT mhx@iae.nl - 2013-12-30 06:00 -0800
      Re: A riddle with QSORT anton@mips.complang.tuwien.ac.at (Anton Ertl) - 2013-12-30 15:55 +0000
    Re: A riddle with QSORT Pablo Hugo Reda <pabloreda@gmail.com> - 2013-12-30 12:24 -0800
    Re: A riddle with QSORT "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-12-30 19:29 -0500

#27524 — A riddle with QSORT

I'm sorting an array of 10 million and it takes 87 sec with qsort.
Using a comparison xt ' n<

    \ For the integers from the s array at INDEX1 and INDEX2:
    \ " s at index1 IS less than s at index2"
    \ For the diehards ( n1,n2 -- fl)
    : n<   s[] @ SWAP s[] @ >   ;

Now I make n< more complicated, forcing a stable sort by taking the
addresses into account:

: n<   s[] DUP >R @ SWAP s[] DUP >R @ >   R> R> < OR ;

The running time goes down to 57 secs.

How come?

(I know the answer, hence riddle.)

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [next] | [standalone]

#27526

On Monday, December 30, 2013 12:48:14 PM UTC+1, Albert van der Horst wrote:
> I'm sorting an array of 10 million and it takes 87 sec with qsort.
> [..]
> The running time goes down to 57 secs.
[..]
> How come?
[..]
> (I know the answer, hence riddle.)

The logical thing is to suspect that your array contains many duplicates? 
As this is a riddle, I expect a more exciting reason.

-marcel

[toc] | [prev] | [next] | [standalone]

#27527

mhx@iae.nl writes:
>On Monday, December 30, 2013 12:48:14 PM UTC+1, Albert van der Horst wrote:
>> I'm sorting an array of 10 million and it takes 87 sec with qsort.
>> [..]
>> The running time goes down to 57 secs.
>[..]
>> How come?
>[..]
>> (I know the answer, hence riddle.)
>
>The logical thing is to suspect that your array contains many duplicates? 

It's a bad implementation of quicksort if duplicates slow it down; in
a decent implementation duplicates produce a speedup.

My first guess would be cache effects, and given that there is not
enough code shown to make any sense of it (including the claim that
the second N< makes the sort stable), I won't make a second guess.

- anton
-- 
M. Anton Ertl  http://www.complang.tuwien.ac.at/anton/home.html
comp.lang.forth FAQs: http://www.complang.tuwien.ac.at/forth/faq/toc.html
     New standard: http://www.forth200x.org/forth200x.html
   EuroForth 2013: http://www.euroforth.org/ef13/

[toc] | [prev] | [next] | [standalone]

#27552

I not understand why compare the adress too

the sorting array is correct in the second version ? I guess not

[toc] | [prev] | [next] | [standalone]

#27554

On Mon, 30 Dec 2013 06:48:14 -0500, Albert van der Horst  
<albert@spenarnc.xs4all.nl> wrote:

> I'm sorting an array of 10 million and it takes 87 sec with qsort.
> Using a comparison xt ' n<
>
>     \ For the integers from the s array at INDEX1 and INDEX2:
>     \ " s at index1 IS less than s at index2"
>     \ For the diehards ( n1,n2 -- fl)
>     : n<   s[] @ SWAP s[] @ >   ;
>
> Now I make n< more complicated, forcing a stable sort by taking the
> addresses into account:
>
> : n<   s[] DUP >R @ SWAP s[] DUP >R @ >   R> R> < OR ;
>
> The running time goes down to 57 secs.
>
> How come?
>

I have no idea how qsort is implemented in C anymore, and I'm totally
unfamiliar with Forth's version(s).  For now, I'm assuming s[] adds
the base address of the s[] array to the index.

ISTM that you've changed the 'true' flag for n< to make some of the
expected failures for n< to succeed based on their location, instead
of their value.  Having more true results from n< likely reduces the
number of comparisons or swaps, if and when the extra true result is
correct.  I'm assuming that your change has the result of always making
comparisons from lower to higher addresses in the array.  This could
possibly prevent thrashing of the sort routine by ensuring that small
values always move in one direction of the array and large values in
the other, whereas without the change it could partially sort in one
direction, then reverse itself and sort in the other.  Hence, this
would reduce the total sort time, when the change to n< works correctly.
It's likely this only works for an array already biased, partially
sorted in the expected direction for the change to n<.  If the array
is heavily biased in the other direction, it could cause the sort
to take much longer.


Rod Pemberton

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web