E
eriwik
I'm working on an application that performs calculations on triangles
of a 3D-model. As part of those computations I have to calculate a
value for each pair of triangles and the number of triangles can be
quite large (testmodel has 16500 triangles). Each triangle has a
ID-number, however the number-range does not start from 0 but usually
somewhere in the range of 10000-100000 and are not neccesarily
contigious. My problem is to store the results of the computations, a
quick calculation shows that 16500*16500*sizeof(float) ~ 1GB.
Fortunately most of the results (~95%) are 0 so by not saving them we
can reduce the size to ~50MB which is quite manageable. However I have
not found any really memory-efficient structure to save the data in
that will also allow fast retrieval (and preferably fast inserts). My
current solution is:
std::map<int, std::map<int, float> >
(put inside a wrapper to return 0 if an element can't be found and
making insertions of 0 a noop) which gives me an access time of O(log
16500 + log 830) (meaning that there are on average ~830 elements per
row in the matrix), which translated to real time gives acceptable
preformance. However it uses about 350MB memory instead of the optimal
50MB.
My question: does anyone know of a more memory efficient
storage-solution that would allow comparable performance, kind of like
a lightweight std::map? If it's easily implemented that would of course
be a bonus.
of a 3D-model. As part of those computations I have to calculate a
value for each pair of triangles and the number of triangles can be
quite large (testmodel has 16500 triangles). Each triangle has a
ID-number, however the number-range does not start from 0 but usually
somewhere in the range of 10000-100000 and are not neccesarily
contigious. My problem is to store the results of the computations, a
quick calculation shows that 16500*16500*sizeof(float) ~ 1GB.
Fortunately most of the results (~95%) are 0 so by not saving them we
can reduce the size to ~50MB which is quite manageable. However I have
not found any really memory-efficient structure to save the data in
that will also allow fast retrieval (and preferably fast inserts). My
current solution is:
std::map<int, std::map<int, float> >
(put inside a wrapper to return 0 if an element can't be found and
making insertions of 0 a noop) which gives me an access time of O(log
16500 + log 830) (meaning that there are on average ~830 elements per
row in the matrix), which translated to real time gives acceptable
preformance. However it uses about 350MB memory instead of the optimal
50MB.
My question: does anyone know of a more memory efficient
storage-solution that would allow comparable performance, kind of like
a lightweight std::map? If it's easily implemented that would of course
be a bonus.