[18832] in s-news-athena
RE: [S] Help eliminate a recursive function
daemon@ATHENA.MIT.EDU (David E. Moore)
Tue Aug 3 13:38:22 1999
From: "David E. Moore" <moordi@email.uc.edu>
To: "Prof Brian D Ripley" <ripley@stats.ox.ac.uk>,
"CHASALOW, SCOTT [AG/2165]" <SCOTT.CHASALOW@cereon.com>
Cc: <Bill.Venables@cmis.csiro.au>, "'S-NEWS'" <s-news@wubios.wustl.edu>
Date: Tue, 3 Aug 1999 13:37:01 -0400
Message-Id: <000501beddd6$caff6e70$315c8981@ucids02.mcm.uc.edu>
Mime-Version: 1.0
Content-Type: text/plain;
charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
In-Reply-To: <Pine.GSO.4.05.9907301853080.6305-100000@auk.stats>
Thanks to all who replied to my query. Thanks especially to Brian
Ripley, Bill Venables, Scott Chasalow, and Erin Hodgess for supplying
me with code snippets that illustrate different approaches. For those
who were wondering, I ended up trying a version of the S+ code provided
by Bill Venables, which I streamlined for our particular problem.
Unfortunately, while it was quite fast, it wasn't nearly fast enough.
I have since turned to c, as suggested by several people, including
those who showed me how to avoid recursion using S+.
Anyone who is interested in details of the S+ or c routines, or of the
substantive problem that started it all, can contact me and I'll be
happy to tell you what I can.
Again, thanks for all of the helpful information.
D. Moore
> -----Original Message-----
> From: owner-s-news@wubios.wustl.edu
> [mailto:owner-s-news@wubios.wustl.edu]On Behalf Of Prof Brian D Ripley
> Sent: Friday, July 30, 1999 1:59 PM
> To: CHASALOW, SCOTT [AG/2165]
> Cc: 'Bill.Venables@cmis.csiro.au'; 'moord@email.uc.edu'; 'S-NEWS'
> Subject: RE: [S] Help eliminate a recursive function
>
>
>
> On Fri, 30 Jul 1999, CHASALOW, SCOTT [AG/2165] wrote:
>
> > the same answers.) Generating (but not doing anything interesting with)
> > the 15504 combinations of 1:20 taken 5 at a time took each function
> > around 45 seconds on a 300 MHz Pentium running S-PLUS 4.5 under Win NT.
>
> > For much larger problems, I strongly second Bill's comment that this
> > "is the sort of territory where dynamically loaded code starts to become
> > unavoidable."
>
> As Bill probably has long forgotten, there is C code to do precisely
> that in the lqs function in the V&R3 MASS library, as in
>
> /*
> Find all subsets of size k in order: this gets a new one each call
> */
> void
> next_set(Sint * x, int n, int k)
> {
> int i, j, tmp;
>
> j = k - 1;
> tmp = x[j]++;
> while (j > 0 && x[j] >= n - (k - 1 - j)) tmp = ++x[--j];
> for (i = j + 1; i < k; i++) x[i] = ++tmp;
> }
> and you will need to look at the code to see how it is initialized
> (x is 1:k). (This is often called a Gray code algorithm.)
>
> And although I originally wrote this as a loop in S, doing 100000 subsets
> meant that I needed to do it all in C.
>
> --
> Brian D. Ripley, ripley@stats.ox.ac.uk
> Professor of Applied Statistics, http://www.stats.ox.ac.uk/~ripley/
> University of Oxford, Tel: +44 1865 272861 (self)
> 1 South Parks Road, +44 1865 272860 (secr)
> Oxford OX1 3TG, UK Fax: +44 1865 272595
>
> -----------------------------------------------------------------------
> This message was distributed by s-news@wubios.wustl.edu. To unsubscribe
> send e-mail to s-news-request@wubios.wustl.edu with the BODY of the
> message: unsubscribe s-news
>
-----------------------------------------------------------------------
This message was distributed by s-news@wubios.wustl.edu. To unsubscribe
send e-mail to s-news-request@wubios.wustl.edu with the BODY of the
message: unsubscribe s-news
