4
$\begingroup$

I have a large set of points in 3D and I'm trying to identify all the points that lie within a certain distance of each point. Then using this data store the vector between the pairs of points.

I have about 1M points and this results in millions of vectors.

It seems that when I Map Nearest over my set of points it is unpacking the array (because it becomes ragged?) and this appears to take up all my memory. At the end I Flatten the array to a specific depth and can manually pack it again and I estimate it should fit in memory.

closepointsvectors finds all the points within 1 unit of point x and then returns the vector between the point x and the "close" points. I then Map this over all the points in the dataset. This generates many many vectors.

Here is a minimal (non)working example.

data = RandomReal[10, {10^6, 3}];
nearestfunction = Nearest[data];
closepointsvectors[x_] := (x - #) & /@ nearestfunction[x, {Infinity, 1}]

(*lets try on a small subset of the data*)
smalltest = Flatten[Map[closepointsvectors, data[[1 ;; 10000]]],2]; // AbsoluteTiming

(*{1.5870908, Null}*)

Developer`PackedArrayQ@data

(*True*)

Developer`PackedArrayQ@smalltest

(*False*)

ByteCount[smalltest]

(*40818664*)

packedsmalltest = Developer`ToPackedArray@smalltest;
Developer`PackedArrayQ@packedsmalltest

(*True*)

ByteCount[packedsmalltest]

(*10204824*)

Is there a way to reduce memory usage, possibly keeping the array packed the whole time. Can I pad the array with zeroes as I go to prevent it from becoming ragged? I tried to take advantage of compile but it doesn't appear to work with Nearest.

$\endgroup$
4
  • 1
    $\begingroup$ I don't have M available at the moment. It might be helpful to use On["Packing"] to determine exactly where the unpacking is occurring as a start. $\endgroup$
    – Andy Ross
    Nov 30, 2012 at 5:08
  • 3
    $\begingroup$ Did I miss the definition of nearestfunction? $\endgroup$ Nov 30, 2012 at 10:20
  • $\begingroup$ Is it the unpacking of the original array that causes memory to be exhausted or the generation of the set of closest vectors? If the latter you could always write out subsets of the closest vectors to disk as you work through the original data. $\endgroup$ Nov 30, 2012 at 10:31
  • $\begingroup$ @image_doctor, fixed sorry. $\endgroup$
    – s0rce
    Nov 30, 2012 at 15:55

1 Answer 1

7
$\begingroup$

I suggest packing the output row-by-row as you create it:

data = RandomReal[10, {10000, 3}];
nf = Nearest[data];
f[x_] := Developer`ToPackedArray[(x - #) & /@ nf[x, {Infinity, 1}]]
smalltest = f /@ data;

ByteCount[smalltest]
(* 10611288 *)

As you can see, the memory usage is kept low - smalltest is an unpacked array of packed arrays.

However, you want the final output flattened, which will unpack the elements:

ByteCount[Flatten[smalltest]]
(* 32239408 *)

The workaround is to use Join to do the flattening:

smalltest = Join @@ Join @@ smalltest;

ByteCount[smalltest]
(* 9211384 *)

Developer`PackedArrayQ[smalltest]
(* True *)
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.