Re: (long) Re: Speed Challenge

*To*: mathgroup at smc.vnet.net*Subject*: [mg27217] Re: [mg27202] (long) Re: [mg27159] Speed Challenge*From*: Daniel Lichtblau <danl at wolfram.com>*Date*: Mon, 12 Feb 2001 03:20:56 -0500 (EST)*References*: <200102090810.DAA24966@smc.vnet.net>*Sender*: owner-wri-mathgroup at wolfram.com

>Getting the absolute best speed can be a bit tricky and I'd not be >surprised if there are yet faster ways to do this sort of thing; I am >hoping I did not miss one that is entirely obvious. Hmmm... I was at best incomplete in my handling of the tree method. In particular I messed it up for the cases most of interest. If we insist on using Compile we must recreate the entire structure and alter components of the copy. If the bins are all of comparable size and there are n of them, the alteration step is expected time log(n) whereas the copy time is O(n) (albeit with much smaller coefficient). So it is to our advantage, when there are many bins, to avoid Compile, make it a held function, and alter elements in-place. The code below does this. Note that three lines that actually alter the result in significant places are commented out so that we do not run out of objects in doing large batches of tests. SetAttributes[removeonetootree, HoldAll]; removeonetootree[ll_] := Module[ {ball,bin,sum,node,posn,numtoleft,tlen=Length[ll]}, ball = Random[Integer, {1,ll[[tlen,1]]}]; (* ll[[tlen,1]]--; *) ll[[tlen,3]] = ball; posn = ll[[tlen,2]]; node = ll[[posn]]; numtoleft = node[[3]]; While[!(numtoleft<ball && numtoleft+node[[4]]>=ball), If [numtoleft>=ball, (* walk to left *) (* ll[[posn,3]]--; *) numtoleft -= node[[3]]; posn = node[[1]]; node = ll[[posn]]; numtoleft += node[[3]], (* else walk to right *) numtoleft += node[[4]]; posn = node[[2]]; node = ll[[posn]]; numtoleft += node[[3]]; ]; ]; (* ll[[posn,4]]--; *) ll ] For the small example this is several times slower than the version that uses Compile. But that hardly matters because for small bin counts this tree method is not the best way to proceed. For the very large example (10^5 bis), I now get a factor around 8 improvement in speed (the last version took 3 seconds to do 100 iterations). In[340]:= Timing[Do[removeonetootree[amazonrainforest], {1000}];] Out[340]= {3.82 Second, Null} To perform a large series of such experiments, I removed the comments that block out code, do assignments to alter the input, and have In[342]:= Timing[Do[amazonrainforest = removeonetootree[amazonrainforest], {1000}];] Out[342]= {4.44 Second, Null} Checking First[Last[amazonrainforest]] will show that we did indeed remove 1000 balls from the 10^5 bins. This destructive tree method is probably the best way to proceed if you have alot of bins (assuming an earth scientist is allowed to use destructive tree techniques in the first place). Daniel Lichtblau Wolfram Research

**References**:**(long) Re: Speed Challenge***From:*Daniel Lichtblau <danl@wolfram.com>