[SOLVED] Large, mostly empty data structure for tetrahedron faces

Large, mostly empty data structure for tetrahedron faces

I'm trying to link the node id of every face in a tetrahedron with it's corresponding tetra id.

tetras = [1 2 3 4  % Tetra 1
          5 6 7 8] % Tetra 2

For tetra 1, there are four faces:

faces = [1 2 3; 1 2 4; 1 3 4; 2 3 4] % Notice these are sorted

Then I'd like to store these in a data structure:

tet_for_face = cell(8,8,8) % 8 allows for the maximum node id

tet_for_face{1,2,3} = 1;
tet_for_face{1,2,4} = 1;
tet_for_face{1,3,4} = 1;
tet_for_face{2,3,4} = 1;

This means that I can find the tetra ID of any particular face in O(1):

tet_for_face{2,3,3}
ans = []
tet_for_face{2,3,4}
ans = 1

The problem with this approach is that it requires contiguous memory. As my mesh gets larger, I run out of memory:

cell(1000, 1000, 1000)
??? Error using ==> cell
Out of memory. Type HELP MEMORY for your options.

I've also played around with using nested cells:

tet = cell(num_nodes, 1);
tet2 = cellfun(@(x) cell(num_nodes, 1), tet, 'UniformOutput', 0);
tet3 = cellfun(@(x) cellfun(@(y) cell(num_nodes, 1), x, 'UniformOutput', 0), tet2, 'UniformOutput', 0);

tet3{2}{3}{4} = 1;
...

Although this works for small meshes, and doesn't require contiguous memory (AFAIK), it has a nasty habit of crashing MATLAB with N=1000.

Any ideas?

Solution

After a bit of playing with sparse arrays (which can only be 1D or 2D, not 3D), and not getting anywhere, I decided to go with containers.Map (HashMap).

I used string keys, and the fastest way I found of producing them I found was using sprintf (rather than int2str or mat2str)

Sample code:

tet = containers.Map;
for tetra_id in tetras 
    for face in faces
        face_key = sprintf('%d ', face);
        tet(face_key) = tetra_id;

This gives me a map like so:

tet('1 2 3') = 1