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