Speed Challenge
- To: mathgroup at smc.vnet.net
- Subject: [mg27159] Speed Challenge
- From: "Gareth J. Russell" <russell at cerc.columbia.edu>
- Date: Thu, 8 Feb 2001 04:40:46 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
For the efficiency and speed demons among you: a challenge.
Take a list of integers that represents, say, the number balls in each of a
set of boxes. I want the fastest code that removes ONE ball at random. The
ball is chosen at random from all the balls (rather than a box being
randomly chosen). Here is my suggestion, and its speed over 10,000
iterations on my system:
removeone = Compile[{{l, _Integer, 1}}, Module[{chosenball, chosenbox},
chosenball = Random[Integer, {1, Apply[Plus, l]}];
chosenbox =
Position[
Map[If[# ? chosenball, 1, 0] &, Drop[FoldList[Plus, 0, l],
1]],
1][[1, 1]];
MapAt[# - 1 &, l, chosenbox]
]
];
Do[removeone[{5, 4, 7, 6, 5, 4, 7, 8, 9, 4, 5, 6}], {10000}]; // Timing
{1.06667 Second, Null}
I think there must be faster way to do the middle expression (chosenbox =
...). Can you beat it!
Gareth
P.S. I do have a practical use for this...
==================================================
Dr. Gareth J. Russell
University of Tennessee
Columbia University (as visitor)
MAILING ADDRESS (new as of 15TH JANUARY, 2001)
110 Geosciences
Lamont-Doherty Earth Observatory
Columbia University
61 Route 9W
Palisades, NY 10964, U.S.A.
PHONE: ++1 845 365 8683
FAX: ++1 845 365 8156 (not conveniently located, avoid if possible)
E-MAIL: russell at cerc.columbia.edu (NO CHANGE)
WWW: http://web.utk.edu/~grussell (NO CHANGE)
==================================================