Services & ResourcesWolfram ForumsMathGroup Archive

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

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>