algorithm reference for sample() - Knuth

-----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]]