Date: Sat, 26 Jun 2004 02:22:11 -0400
Reply-To: sashole@bellsouth.net
Sender: "SAS(r) Discussion" <SAS-L@LISTSERV.UGA.EDU>
From: "Paul M. Dorfman" <sashole@BELLSOUTH.NET>
Organization: Sashole of Florida
Subject: Re: IF conditions and ARRAY subscripts
In-Reply-To: <20040626055034.JOLP23971.imf06aec.mail.bellsouth.net@malibu.cc.uga.edu>
Content-Type: text/plain; charset="us-ascii"
TMK,
My experience with the SAS functions is that they are efficient when called
in a nested manner: There must exist a very efficient internal mechanism
unrolling the recursion at the compile time. When they are called
iteratively at run-time, they tend to fare noticeably worse. So, if you are
determined on using the ORDINAL-based sort, you might consider assembling
the necessary number of recursive ORDINAL calls using a macro. I would
expect the iterative version of ORDINAL-based sort to perform in O(N**2)*C
time, though, but the constant might be rather large.
However, methinks the only reason the technique is mentioned in Ron's book
is not its performance, but rather the fact that the algorithm is
implemented by using a single SAS function, hence demonstrating how SAS
functions work, which is the main thrust of the opus. Roughly speaking, if
the array is short (a dozen entries or so), consider the insertion or bubble
sort. For several dozen entries, Quicksort may already make sense. If the
array keys are integers falling in a fairly short range (say, < 1e6), radix
sort is by far the fastest. For code, see the archives at
http://www.listserv@listserv.uga.edu/cgi-bin/wa?A2=ind9901C&L=sas-l&P=R1428
Kind regards,
----------------
Paul M. Dorfman
Jacksonville, FL
----------------
> -----Original Message-----
> From: Talbot Michael Katz [mailto:topkatz@MSN.COM]
> Sent: Saturday, June 26, 2004 1:51 AM
> To: SAS-L@LISTSERV.UGA.EDU; Paul M. Dorfman
> Cc: Talbot Michael Katz
> Subject: Re: IF conditions and ARRAY subscripts
>
> Thank you, Chang and Paul, for your helpful responses (and a
> continual thanks to all of you who take the time to answer my
> questions). I guess I won't presume OR condition
> short-circuiting any more.
>
> Paul, for some reason I couldn't access either of the SAS-L
> archive links you provided (I had no problem with the SUGI26
> paper), although I was able to find your SAS-L posting of the
> Qsort macro from three years ago (06/29/2001, "Re: Array sort
> algorithms wanted") by searching the archives myself.
> Question -- If the ordinal function sorting algorithm has to
> do a sort each time the ordinal function is called, it would
> be worse than O (N**2), wouldn't it be at best O(N*N*log(N))?
>
> Thanks!
>
> -- TMK --
>
| 
