Re: A riddle with QSORT

Path	csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail
From	"Rod Pemberton" <dont_use_email@xnohavenotit.cnm>
Newsgroups	comp.lang.forth
Subject	Re: A riddle with QSORT
Date	Mon, 30 Dec 2013 19:29:19 -0500
Organization	Aioe.org NNTP Server
Lines	43
Message-ID	<op.w8xky5lm5zc71u@localhost> (permalink)
References	<52c15d7d$0$2921$e4fe514c@dreader36.news.xs4all.nl>
NNTP-Posting-Host	CNsg4fVcCsvs3UaOgZtQCw.user.speranza.aioe.org
Mime-Version	1.0
Content-Type	text/plain; charset=us-ascii; format=flowed; delsp=yes
Content-Transfer-Encoding	7bit
X-Complaints-To	abuse@aioe.org
User-Agent	Opera Mail/12.16 (Linux)
X-Notice	Filtered by postfilter v. 0.8.2
Xref	csiph.com comp.lang.forth:27554

Show key headers only | View raw

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

Back to comp.lang.forth | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

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

csiph-web