From vograno at evafunds.com  Fri Sep 24 02:48:45 2004
From: vograno at evafunds.com (Vadim Ogranovich)
Date: Fri Sep 24 02:49:12 2004
Subject: [Rd] algorithm reference for sample()
Message-ID: <C698D707214E6F4AB39AB7096C3DE5A56D850A@phost015.EVAFUNDS.intermedia.net>

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


[Rd] algorithm reference for sample()
Vadim Ogranovich