Problem with BinLists for large lists
- To: mathgroup at smc.vnet.net
- Subject: [mg101293] Problem with BinLists for large lists
- From: pfalloon <pfalloon at gmail.com>
- Date: Tue, 30 Jun 2009 06:34:16 -0400 (EDT)
Hi,
I've been trying to use BinLists to bucket large (approx. a million
elements) lists of 3 dimensional vectors. I've noticed that BinLists
runs pretty slowly when working with large lists in general, and for
lists of this size and dimensionality actually runs out of memory.
I've worked up an alternative implementation which runs pretty
quickly, and works by partitioning component-wise, then finding
intersections of each bucket. I thought it might be worth posting to
see if anyone has encountered this issue and knows more about why it
happens...
Example implementation:
(* generate some large lists of reals *)
{x,y,z} = RandomReal[{0,1}, {3,10^6}];
xyz = Transpose[{x, y, z}];
(* define bin intervals *)
int = Range[0,1,0.1];
(* calculate buckets for each variable *)
{xBins, yBins, zBins} = Table[Flatten@Position[#, _?(int[[i]] <= # <
int[[i+1]] &)], {i, Length[int]-1}] & /@ {x, y, z};
(* get 3x3 grid of bins by taking intersections of the single-variable
bins *)
xyzBins = Table[Intersection[xBins[[i]], yBins[[j]], zBins[[k]]],
{i,Length@xBins}, {j,Length@yBins}, {k,Length@zBins}];
(* look at the length of each bins *)
Map[Length, xyzBins, {3}]
(* get the actual points in each bin *)
binContents = Map[xyz[[#]] &, xyzBins, {3}];
(* look at points from a particular bin *)
ListPlot[Transpose[xyz[[xyzBins[[1,2,3]]]]]]
(* the equivalent call to BinLists runs out of memory on my machine
(32-bit windows) *)
BinLists[xyz, {int}, {int}, {int}];
I'm not sure why BinLists doesn't use an approach like this. My
suspicion is that it may be using something like (using above
definitions):
xyzBins = Outer[Intersection, xBins, yBins, zBins];
the problem being that the Outer function will effectively cause
multiple copies of each list to be generated and thus runs out of
memory.