[Rd] algorithm reference for sample() - Knuth

[Vadim Ogranovich]

My apologies for the previous incomplete message, I accidentally hit
"send". Here is another try.


Thank you all for the reference to Knuth. Indeed in vol. 2 he has a
section "Random Sampling and Shuffling" which looks relevant.
Unfortunately, I don't have an access to the book itself so I couldn't
figure if this section discusses samples w/o replacement WITH
pre-specified sampling probability. The only public library around that
has the book is a parking nightmare so before I go there I would really
appreciate if someone, who has the book on his shelf, could tell me that
the section is relevant indeed?

Many thanks,
Vadim

> -----Original Message-----
> From: Tony Plate [mailto:tplate at 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 at stat.math.ethz.ch mailing list
> >https://stat.ethz.ch/mailman/listinfo/r-devel
> 
>