MathGroup Archive 2001

[Date Index] [Thread Index] [Author Index]

Search the Archive

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




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