Optimising arrays of lists
- To: mathgroup at smc.vnet.net
- Subject: [mg40709] Optimising arrays of lists
- From: Jon Harrop <jdh30 at cam.ac.uk>
- Date: Mon, 14 Apr 2003 04:06:24 -0400 (EDT)
- Organization: Univerisity of Cambridge
- Reply-to: jdh30 at cam.ac.uk
- Sender: owner-wri-mathgroup at wolfram.com
I've implemented some voxel code to play with particle systems (actually cubic supercells of ~100,000 atoms) in Mathematica. The current code works but is too slow (~20 times slower than my optimised C++ code). Basically, the principle data structure which is used to store the atoms efficiently is a 3D array of lists of atoms. This data structure partitions the atoms in the cubic cell into voxels containing a few atoms each. Nearest neighbour calculations etc. can then be done in O(1) time. In C++ this structure is implemented as something like vector<list<Atom>> but in Mathematica this is a nested list of uniform depth 4 with the leaf lists having various lengths. Ideally, I would like the array of voxels to be a packed array and the list of atoms in each voxel to be a list in Mathematica. However, I have not been able to do this because Mathematica is so good at abstracting away packed arrays. One solution is to use a packed array where underfilled voxels are padded out with null atoms. Aside from not being elegant this will obviously be slower for adding new atoms to a full voxel (the entire structure will need to be regenerated) and for shuffling atoms around. Is there a more elegant solution? Cheers, Jon.