In article <1163575811.706084.100220@i42g2000cwa.googlegroups .com>,
eriwik@student.chalmers.se <eriwik@student.chalmers.sewrote:
Quote:
As part of those computations I have to calculate a
>value for each pair of triangles
key
Quote:
>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
