Optimizing a simple sampling function for speed

• To: mathgroup at smc.vnet.net
• Subject: [mg25343] Optimizing a simple sampling function for speed
• From: "Kimberly N. Russell" <norris at cerc.columbia.edu>
• Date: Sat, 23 Sep 2000 03:36:07 -0400 (EDT)
• Sender: owner-wri-mathgroup at wolfram.com

```Hi Gang,

In a lot of my work I have need for a function that draws a sample of size n
without replacement from a set of objects in bins, where the distribution is
given as a simple list. This function is used in simulations, so speed and
efficiency are important. Here is my attempt at doing this in Mathematica.

First, define a function that removes one number at random from a list
without replacement.

In[1]:=
removeone[l_] := Module[{chosenobs, chosencat},
chosenobs = Random[]*Fold[Plus, 0, l];
chosencat =
Extract[Position[Drop[FoldList[Plus, 0, l], 1],
x_ /; x ? chosenobs], {1, 1}];
ReplacePart[l, l[[chosencat]] - 1, chosencat]
]

Nesting this allows a sample of size n to be removed, and subtracting that
from the original gives you the sample itself.

In[2]:=
randsampcat[l_, n_] := l - Nest[removeone, l, n]

So, create a distribution with approx 5000 objects in 1000 bins...

In[10]:=
dist = Table[Random[Integer, {1, 100}], {100}];

...and sample 1000 of them.

In[9]:=
randsampcat[dist, 1000]; // Timing

Out[9]=
{3.96667 Second, Null}

I am sure that this can be improved upon. Can any of you Mathematica wizards
show me how? I tried compiling removeone, but got the following errors which
I don't really understand.

In[8]:=
removeonecomp = Compile[{{l, _Integer, 1}}, Module[{chosenobs, chosencat},
chosenobs = Random[]*Fold[Plus, 0, l];
chosencat =
Extract[Position[Drop[FoldList[Plus, 0, l], 1],
x_ /; x ? chosenobs], {1, 1}];
ReplacePart[l, l[[chosencat]] - 1, chosencat]
]
]

Compile::"cpintlt": "(chosencat) at position 2 of
System`Private`CompileLocal1[[chosencat]] should be either a non-zero
integer or a vector of non-zero integers; evaluation will use the uncompiled
function."

Compile::"cpintlt": "(chosencat) at position 2 of l[[chosencat]] should be
either a non-zero integer or a vector of non-zero integers; evaluation will
use the uncompiled function."

Out[8]=
CompiledFunction[{l},
Module[{chosenobs, chosencat}, chosenobs = Random[] Fold[Plus, 0, l];
chosencat =
Extract[Position[Drop[FoldList[Plus, 0, l], 1],
x_ /; x ? chosenobs], {1, 1}];
ReplacePart[l, l\[LeftDoubleBracket]chosencat\[RightDoubleBracket] - 1,
chosencat]], "-CompiledCode-"]

________________________________________________________
1stUp.com - Free the Web
Get your free Internet access at http://www.1stUp.com

```

• Prev by Date: Re: Noise Sphere
• Next by Date: Re: Strange behaviour of FiniteFields?
• Previous by thread: Progress Meter
• Next by thread: Re: Optimizing a simple sampling function for speed