- This message: [ Message body ] [ More options ]
- Related messages: [ Next message ] [ Previous message ] [ In reply to ] [ Next in thread ] [ Replies ]

From: Martin Maechler <maechler_at_stat.math.ethz.ch>

Date: Fri 24 Sep 2004 - 18:02:53 EST

R-devel@stat.math.ethz.ch mailing list

https://stat.ethz.ch/mailman/listinfo/r-devel Received on Fri Sep 24 18:14:25 2004

Date: Fri 24 Sep 2004 - 18:02:53 EST

Hi Vadim,

>>>>> "Vadim" == Vadim Ogranovich <vograno@evafunds.com>

>>>>> on Thu, 23 Sep 2004 17:48:45 -0700 writes:

Vadim> Hi, Don't know if it belongs to r-devel or r-help, Vadim> but since I am planning to alter some of R's internal code

i.e., you will propose a patch to the R sources eventually ?

Vadim> I am sending it here.

good choice. Also, since you are talking about internal (non-API) C code from R - which I would deem inappropriate on R-help.

Vadim> The existing implementation of the sample() function, Vadim> when the optional 'prob' argument is given, is quite Vadim> inefficient. The complexity is O(sampleSize * Vadim> universeSize), see ProbSampleReplace() and Vadim> ProbSampleNoReplace() in random.c. This makes the Vadim> function impractical for the vector sizes I use.

I'm interested: What problem are you solving where sample() is the bottleneck (rather than what you *do* with the sample ..)

Vadim> I want to re-code these functions and I "think" I can Vadim> come up with a more efficient algorithm.

I agree. It's a kind of table lookup, that definitely can be made faster e.g. by bisection ideas.

Vadim> However before I go and reinvent the wheel I wonder if there Vadim> is a published description of an efficient sampling Vadim> algorithm with user-specified probabilities?

I've got some ideas, but maybe would first want to get a reply to the current ones.

Vadim> Thanks, Vadim

Vadim> [[alternative HTML version deleted]] ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

(you *did* read the posting guide or just the general instructions on http://www.R-project.org/mail.html ? )

Martin Maechler

R-devel@stat.math.ethz.ch mailing list

https://stat.ethz.ch/mailman/listinfo/r-devel Received on Fri Sep 24 18:14:25 2004

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