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

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)
==================================================

```

• Prev by Date: Linux+Mathematica+Lithuanian.kbd
• Next by Date: Re: Re: Factor[1+x^4]