RE: [Rd] algorithm reference for sample() - Knuth

From: Vadim Ogranovich <vograno_at_evafunds.com>
Date: Sat 25 Sep 2004 - 07:17:43 EST


Thank you for the reference to Knuth. Indeed in vol. 2 he has a

> -----Original Message-----
> From: Tony Plate [mailto:tplate@blackmesacapital.com]
> Sent: Friday, September 24, 2004 8:05 AM
> To: Vadim Ogranovich
> Subject: Re: [Rd] algorithm reference for sample()
>
> Have you tried looking in Knuth's books on computer
> algorithms? (They are classics for good reason!) If I
> remember correctly, a colleague found a very clever and fast
> algorithm for just this problem in one of those volumes.
>
> -- Tony Plate
>
>
> At Thursday 06:48 PM 9/23/2004, Vadim Ogranovich wrote:
> >Hi,
> >
> >Don't know if it belongs to r-devel or r-help, but since I
> am planning
> >to alter some of R's internal code I am sending it here.
> >
> >The existing implementation of the sample() function, when
> the optional
> >'prob' argument is given, is quite inefficient. The complexity is
> >O(sampleSize * universeSize), see ProbSampleReplace() and
> >ProbSampleNoReplace() in random.c. This makes the function
> impractical
> >for the vector sizes I use. I want to re-code these functions and I
> >"think" I can come up with a more efficient algorithm.
> However before I
> >go and reinvent the wheel I wonder if there is a published
> description
> >of an efficient sampling algorithm with user-specified probabilities?
> >
> >Thanks,
> >Vadim
> >
> > [[alternative HTML version deleted]]
> >
> >______________________________________________
> >R-devel@stat.math.ethz.ch mailing list
> >https://stat.ethz.ch/mailman/listinfo/r-devel
>
>



R-devel@stat.math.ethz.ch mailing list
https://stat.ethz.ch/mailman/listinfo/r-devel Received on Sat Sep 25 07:22:44 2004

This archive was generated by hypermail 2.1.8 : Fri 18 Mar 2005 - 09:00:22 EST