Memory-efficient datastructure for sparse matrixes not indexed from 0

[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*siz eof(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.

--
Erik Wikström

[Yannick Tremblay]

In article <11************ **********@i42g 2000cwa.googleg roups.com>,
er****@student. chalmers.se <er****@student .chalmers.sewro te:

As part of those computations I have to calculate a
value for each pair of triangles

key

>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.

You said it yourself in the description above. Your operations are on
triangle pairs

So what about:

typedef int triangleId_t;
typedef std::pair<trian gleId_t, triangleId_tpai rKey_t;
std::map< pairKey_t, floatresultMap;

while keeping as above not storing 0.

Amount of memory used = ~50Mb
access time 0log(16500 * 830)

Alternatively if std::pair doesn't do it for you, you can create a
class ala:

TrianglePair
{
public:
TrianglePair(tr iangleId_t first, triangleId_t second);

bool operator=(trian gleId_t const & lhs); // or non-member friends
bool operator<(trian gleId_t const & lhs);

private:
triangleId_t m_first;
triangleId_t m_second;

}

and use a map<TrianglePai r, float>

This might be particularly appropriate if your operation is
commutative since it would allow you to handle it in the contructor
and optimise the operator for first always smaller than second.

Hope this helps

Yan

[Erik Wikström]

On 2006-11-15 16:42, Yannick Tremblay wrote:

In article <11************ **********@i42g 2000cwa.googleg roups.com>,
er****@student. chalmers.se <er****@student .chalmers.sewro te:

>As part of those computations I have to calculate a
value for each pair of triangles

key

>>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.

You said it yourself in the description above. Your operations are on
triangle pairs

So what about:

typedef int triangleId_t;
typedef std::pair<trian gleId_t, triangleId_tpai rKey_t;
std::map< pairKey_t, floatresultMap;

while keeping as above not storing 0.

Amount of memory used = ~50Mb
access time 0log(16500 * 830)

<snip>

Yeah, I tried that but for some reason it was slower than the double-
map, shouldn't be though since log a + log b = log a*b. Anyway, it's of
no matter now, after a lot of work and restructuring I managed to remove
the outer map and use a vector (by taking a bit more time at other
places. Even though I should now be at O(1 + log 830) it does not run
any faster, seems like the computation itself is the bottleneck now.

Thanks anyway.

--
Erik Wikström