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