Re: need little help - no longer!
- To: mathgroup at smc.vnet.net
- Subject: [mg23644] Re: [mg23530] need little help - no longer!
- From: "Allan Hayes" <hay at haystack.demon.co.uk>
- Date: Sun, 28 May 2000 23:08:57 -0400 (EDT)
- References: <8g9nm8$mmd@smc.vnet.net> <8gfuar$br7@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Ted, Mark
Below, I generate the same list of 10000 entries using using:
compiledRandomIndex (Ted Erseck/ MarkFisher): timing 94.91 seconds
And two new codes:
makePicker: timing 63.00 seconds
pickRandom: timing 6.31 seconds
The codes follow the examples
Generate the list of probabilities
m = #/(Plus @@ #) &[Table[Random[], {500}]];
EXAMPLES
1) compileRandomIndex
pick = compileRandomIndex[m];
SeedRandom[1]; Table[pick2[], {10}]
SeedRandom[1]; Table[pick[], {10000}]; // Timing
{333, 426, 394, 60, 471, 297, 382, 486, 61, 278}
{94.91 Second, Null}
2) makePicker: uses Position instead of Which
pick2 = makePicker[m];
SeedRandom[1]; Table[pick2[], {10}]
SeedRandom[1]; Table[pick2[], {10000}]; // Timing
{333, 426, 394, 60, 471, 297, 382, 486, 61, 278}
{63. Second, Null}
3) pickRandom: optimised for making runs, uses list operations, Sort and
Split - an example of setting up structure and modifying it
SeedRandom[1]; pickRandom[m, 10]
SeedRandom[1]; pickRandom[m, 10000]; // Timing
{333, 426, 394, 60, 471, 297, 382, 486, 61, 278}
{6.31 Second, Null}
CODE
compileRandomIndex[list_] :=
Block[{x, y},
Compile @@ (Hold[{}, With[{x = Random[]}, y], {{Which[__], _Integer}}]
/.
y -> Which @@ (Flatten@
Transpose[{Thread[x <= Rest at FoldList[Plus, 0, list]],
Range[Length[list]]}]))]
makePicker[m_] :=
With[{m2 = Rest[FoldList[Plus, 0, m]]},
Compile[{}, Position[Sort[Append[m2, #]], #] &[Random[]][[1, 1]]
]
]
pickRandom[m_, n_] :=
Last[Transpose[
Sort[Join @@ (Map[Last,
Split[Sort[
Join[Transpose[{#, Range[Length[#]]} &[
Table[Random[], {n}]]],
Thread[List[#, List /@ Range[Length[#]]]]
Rest[FoldList[Plus, 0, m]]] ]],
FreeQ[{#1}, {_, {_Integer}}] &], {2}] /. {{x__, \
{p_Integer}} :> Thread[List[{x}, p]],
{{_}} -> Sequence[]})]]]
Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
hay at haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565
"Mark Fisher" <mefisher at bellsouth.net> wrote in message
news:8gfuar$br7 at smc.vnet.net...
> Following up on Andrzej's point, Ken's solution is indeed elegant, but
> Ted Ersek's solution can be compiled. Here is Ted's solution (slightly
> modified):
>
> With[{x = Random[]},
> Which[x < .2, 1, x < .6, 2, x < .7, 3, x < 1., 4]
>
> Here's a function that takes a list and returns a CompiledFuntion:
>
> compileRandomIndex[list_List/; Plus @@ list == 1] :=
> Block[{x, y},
> Compile @@
> (Hold[{}, With[{x = Random[]}, y],
> {{Which[__], _Integer}}] /. y ->
> Which @@ (Flatten @
> Transpose[{Thread[x < Rest @ FoldList[Plus, 0, list]],
> Range[Length[list]]}]))]
>
> The Hold is used to make an inert container that facilitates the
> construction of the arguments to Compile. The idea is to insert the
> evaluated Which expression into the Hold container without evaluating
> the call to Random, and only then slap on the Compile head. (The third
> argument to Compile alerts Compile to the fact that the Which expression
> returns an Integer.)
>
> Here is the usage:
>
> m = {0.2, 0.4, 0.1, 0.3}
> ran = compileRandomIndex[m]
> ran[]
>
> It runs faster than Ken's solution, with the advantage growing with the
> length of the list.
>
> --Mark.
>