By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
440,844 Members | 836 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 440,844 IT Pros & Developers. It's quick & easy.

Memory-efficient datastructure for sparse matrixes not indexed from 0

P: n/a
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.

--
Erik Wikström

Nov 15 '06 #1
Share this Question
Share on Google+
2 Replies


P: n/a
In article <11**********************@i42g2000cwa.googlegroups .com>,
er****@student.chalmers.se <er****@student.chalmers.sewrote:
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<triangleId_t, triangleId_tpairKey_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(triangleId_t first, triangleId_t second);

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

private:
triangleId_t m_first;
triangleId_t m_second;

}

and use a map<TrianglePair, 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

Nov 15 '06 #2

P: n/a
On 2006-11-15 16:42, Yannick Tremblay wrote:
In article <11**********************@i42g2000cwa.googlegroups .com>,
er****@student.chalmers.se <er****@student.chalmers.sewrote:
>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<triangleId_t, triangleId_tpairKey_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
Nov 15 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.