Arrays and Memory Usage
-
We have alot of data we need to store. Sometimes on the order of 3000 elements:omg:. Thus, I could declare a large square matrix (ie: 3000 by 3000) entries for a double data type:wtf:. This is, obviously, totally undesirable. On a P4 it takes about 1/2 a minute to initialize just the array, nevermind the calculation:(( X| . Furthermore, because we have a diagonal matrix (mirror symmetry about the matrix diagonal) the lower half of the matrix is redundant. Thus, we decided (for now) to go with a stair-case type matrix. ie:
m_ppdDeltaMMatrix = new double*[m_uzMaxNodes]; for (int i = 0; i < m_uzMaxNodes; i++) m_ppdDeltaMMatrix[i] = new double[i+1];For large matrix sizes (thousands) the memory savings converge to approximately 50% or (n-1)/2:|. The data is also sparse (quite a few zeroes). I was wondering if anyone had a novel way of solving this problem (I don't :confused: ). This would imply reducing the number of entries to only those necessary, while being able to address arbitrary elements of the matrix like: m_ppdDeltaMMatrix[3][2] or m_ppdDeltaMMatrix[300][127] in the next access to the data. Any help would be greatly appreciated.:-O -
We have alot of data we need to store. Sometimes on the order of 3000 elements:omg:. Thus, I could declare a large square matrix (ie: 3000 by 3000) entries for a double data type:wtf:. This is, obviously, totally undesirable. On a P4 it takes about 1/2 a minute to initialize just the array, nevermind the calculation:(( X| . Furthermore, because we have a diagonal matrix (mirror symmetry about the matrix diagonal) the lower half of the matrix is redundant. Thus, we decided (for now) to go with a stair-case type matrix. ie:
m_ppdDeltaMMatrix = new double*[m_uzMaxNodes]; for (int i = 0; i < m_uzMaxNodes; i++) m_ppdDeltaMMatrix[i] = new double[i+1];For large matrix sizes (thousands) the memory savings converge to approximately 50% or (n-1)/2:|. The data is also sparse (quite a few zeroes). I was wondering if anyone had a novel way of solving this problem (I don't :confused: ). This would imply reducing the number of entries to only those necessary, while being able to address arbitrary elements of the matrix like: m_ppdDeltaMMatrix[3][2] or m_ppdDeltaMMatrix[300][127] in the next access to the data. Any help would be greatly appreciated.:-O -
We have alot of data we need to store. Sometimes on the order of 3000 elements:omg:. Thus, I could declare a large square matrix (ie: 3000 by 3000) entries for a double data type:wtf:. This is, obviously, totally undesirable. On a P4 it takes about 1/2 a minute to initialize just the array, nevermind the calculation:(( X| . Furthermore, because we have a diagonal matrix (mirror symmetry about the matrix diagonal) the lower half of the matrix is redundant. Thus, we decided (for now) to go with a stair-case type matrix. ie:
m_ppdDeltaMMatrix = new double*[m_uzMaxNodes]; for (int i = 0; i < m_uzMaxNodes; i++) m_ppdDeltaMMatrix[i] = new double[i+1];For large matrix sizes (thousands) the memory savings converge to approximately 50% or (n-1)/2:|. The data is also sparse (quite a few zeroes). I was wondering if anyone had a novel way of solving this problem (I don't :confused: ). This would imply reducing the number of entries to only those necessary, while being able to address arbitrary elements of the matrix like: m_ppdDeltaMMatrix[3][2] or m_ppdDeltaMMatrix[300][127] in the next access to the data. Any help would be greatly appreciated.:-OFirst question, before you go down and dirty: do you really need the huge matrix? is there another algorithm yielding similar results? (peterchens #1 rule in optimizaton: can you avoid it?) Some 7 years ago I looked at some RogueWave libraries for matrix manipulaiton, they claimed to have effective and fast sparse matrices. (Rule #2 - can you use the implementaiton of someone else?) Depends on the required lookup speed, required lookup methods, and if there's some rule in the sparseness. For high sparseness, acceptable memory consumption and fairly fast lookup, you can use a map<int index,double value> for each row (or column, if this yields better results). Add to the map only the indices that are actually used, and provide an overloaded operator[], that looks uses map.find to see if the element is actually there, and return 0.0, or *find This is deadly, however, if you want ot use a "normal" matrix multiplication for multiplying two of these. Two other options (that are simple to implement only if index access can be slow, but iteration through a row must be fast): store which cells are occupied separate from the cell data itself. e.g. an int (or even byte) array: alternating one value number of zeroes, number of "used" values, then store the double's packed, e.g. a ( 0 0 0 1 0 0 2 3 4 0 0 0 ) matrix would be encoded ( 3,1,2,3,3 ) (1,2,3,4) Index access is very slow here. Or use a bit mask to identify occupied cells. (good compression of zeroes, fast iteration, but for index access you need some extra data and clever lookup table juggling. If you need multiplication often, you can create a row-iterable and a column-iterable matrix, and use a specialized multiplication can very quickly identify where there are non-nulls "meeting" each other. Well, there are more clever layots (I can *feel* it ;) ) - but maybe you just say what you have to *do* with the matrix.
"Der Geist des Kriegers ist erwacht / Ich hab die Macht" StS
sighist | Agile Programming | doxygen -
First question, before you go down and dirty: do you really need the huge matrix? is there another algorithm yielding similar results? (peterchens #1 rule in optimizaton: can you avoid it?) Some 7 years ago I looked at some RogueWave libraries for matrix manipulaiton, they claimed to have effective and fast sparse matrices. (Rule #2 - can you use the implementaiton of someone else?) Depends on the required lookup speed, required lookup methods, and if there's some rule in the sparseness. For high sparseness, acceptable memory consumption and fairly fast lookup, you can use a map<int index,double value> for each row (or column, if this yields better results). Add to the map only the indices that are actually used, and provide an overloaded operator[], that looks uses map.find to see if the element is actually there, and return 0.0, or *find This is deadly, however, if you want ot use a "normal" matrix multiplication for multiplying two of these. Two other options (that are simple to implement only if index access can be slow, but iteration through a row must be fast): store which cells are occupied separate from the cell data itself. e.g. an int (or even byte) array: alternating one value number of zeroes, number of "used" values, then store the double's packed, e.g. a ( 0 0 0 1 0 0 2 3 4 0 0 0 ) matrix would be encoded ( 3,1,2,3,3 ) (1,2,3,4) Index access is very slow here. Or use a bit mask to identify occupied cells. (good compression of zeroes, fast iteration, but for index access you need some extra data and clever lookup table juggling. If you need multiplication often, you can create a row-iterable and a column-iterable matrix, and use a specialized multiplication can very quickly identify where there are non-nulls "meeting" each other. Well, there are more clever layots (I can *feel* it ;) ) - but maybe you just say what you have to *do* with the matrix.
"Der Geist des Kriegers ist erwacht / Ich hab die Macht" StS
sighist | Agile Programming | doxygenOk, now we're talking. This is just the type of reply that I was hoping for. Now a bit more on the nature of the problem. Problem 1: Huge matrices are UNAVOIDABLE. Problem 2: Noone has ever tackled this particular problem before (either in literature or in another commercial product.) Problem 3: Just coming up with a method of solution for this problem required a solid week of brain-wracking work by a trained physicist (me!) and a mathematician. Problem 4: I am not a programmer, and so am looking for a better implementation for a data structure One positive is that we don't ever (I repeat never) need to multiply any of these matrices together. They are solely used as "lookup tables" if you will. Each entry in the matrix is addressed by (row,column) and this is important. Let's say for now that each entry represents a connection between nodes and the entry at that location is significant. For example: entry (0, 2) represents a connection between city 0 and city 2 and the data stored at (0,2) would be, say, the distance between city 0 and city 2 (in double form). If you can imagine 7 cities with possible interconnections between all 7 cities (ie: (0, 1), (1, 7), (3, 4), (4, 3, etc...) where (3, 4) = (4,3) But ah! What redundancy through yonder window breaks!) you will see that connections may or may not exist, thus, there is no 'rule' per se on the sparseness of the matrix. Furthermore, entries can generally be made in any conceivable order (for 7 cities, that is quite a few permutations) However, the buck doesn't stop there! We're talking *thousands* of possible interlinks. (The data isn't cities and distances, but that is irrelevant - the behaviour is the same). Also, any given entry at some point may be removed. Speed *is*, unfortunately a great concern as the code is quite optimized right now. I think the map idea is becoming attractive. Others I work with have proposed use of a linked list or STL vector, but I am a bit discouraged by those ideas - they make searching the table a bit daunting. One question I do have concerns the maps. If each entry is indexed by 2 nodes (as above) how would a map of the form map<int index, double value> help here? Is this not basically an STL vector style implementation? Thanks for the help.
-
Ok, now we're talking. This is just the type of reply that I was hoping for. Now a bit more on the nature of the problem. Problem 1: Huge matrices are UNAVOIDABLE. Problem 2: Noone has ever tackled this particular problem before (either in literature or in another commercial product.) Problem 3: Just coming up with a method of solution for this problem required a solid week of brain-wracking work by a trained physicist (me!) and a mathematician. Problem 4: I am not a programmer, and so am looking for a better implementation for a data structure One positive is that we don't ever (I repeat never) need to multiply any of these matrices together. They are solely used as "lookup tables" if you will. Each entry in the matrix is addressed by (row,column) and this is important. Let's say for now that each entry represents a connection between nodes and the entry at that location is significant. For example: entry (0, 2) represents a connection between city 0 and city 2 and the data stored at (0,2) would be, say, the distance between city 0 and city 2 (in double form). If you can imagine 7 cities with possible interconnections between all 7 cities (ie: (0, 1), (1, 7), (3, 4), (4, 3, etc...) where (3, 4) = (4,3) But ah! What redundancy through yonder window breaks!) you will see that connections may or may not exist, thus, there is no 'rule' per se on the sparseness of the matrix. Furthermore, entries can generally be made in any conceivable order (for 7 cities, that is quite a few permutations) However, the buck doesn't stop there! We're talking *thousands* of possible interlinks. (The data isn't cities and distances, but that is irrelevant - the behaviour is the same). Also, any given entry at some point may be removed. Speed *is*, unfortunately a great concern as the code is quite optimized right now. I think the map idea is becoming attractive. Others I work with have proposed use of a linked list or STL vector, but I am a bit discouraged by those ideas - they make searching the table a bit daunting. One question I do have concerns the maps. If each entry is indexed by 2 nodes (as above) how would a map of the form map<int index, double value> help here? Is this not basically an STL vector style implementation? Thanks for the help.
John Theal wrote: One question I do have concerns the maps. If each entry is indexed by 2 nodes (as above) how would a map of the form map help here? Is this not basically an STL vector style implementation? // 0 <= row < numberOfRows // 0 <= col < numberOfCols int mapIndex = row*numberOfColumns + col; // row = mapIndex/numberOfCols // col = mapIndex%numberOfCols
-
We have alot of data we need to store. Sometimes on the order of 3000 elements:omg:. Thus, I could declare a large square matrix (ie: 3000 by 3000) entries for a double data type:wtf:. This is, obviously, totally undesirable. On a P4 it takes about 1/2 a minute to initialize just the array, nevermind the calculation:(( X| . Furthermore, because we have a diagonal matrix (mirror symmetry about the matrix diagonal) the lower half of the matrix is redundant. Thus, we decided (for now) to go with a stair-case type matrix. ie:
m_ppdDeltaMMatrix = new double*[m_uzMaxNodes]; for (int i = 0; i < m_uzMaxNodes; i++) m_ppdDeltaMMatrix[i] = new double[i+1];For large matrix sizes (thousands) the memory savings converge to approximately 50% or (n-1)/2:|. The data is also sparse (quite a few zeroes). I was wondering if anyone had a novel way of solving this problem (I don't :confused: ). This would imply reducing the number of entries to only those necessary, while being able to address arbitrary elements of the matrix like: m_ppdDeltaMMatrix[3][2] or m_ppdDeltaMMatrix[300][127] in the next access to the data. Any help would be greatly appreciated.:-OI am a physicist like you and the problem You have many of us had before. The goal of the boost project is to provide fast number crunching libraries. Your matrix can be represented by a sparse matrix which allocates only memory for the needed elements. You can warp a class around to make use of the symmetry of your matrix. http://www.boost.org/libs/numeric/ublas/doc/matrix\_sparse.htm Even if you do not like the coding style it is worth the effort. Your approach with many pointers and arrays with no boundary checking is very error prone and I guarantee you that You will spend much more time with tracking down errors compared to the time you will need to integrate the sparse matrix.
-
Ok, now we're talking. This is just the type of reply that I was hoping for. Now a bit more on the nature of the problem. Problem 1: Huge matrices are UNAVOIDABLE. Problem 2: Noone has ever tackled this particular problem before (either in literature or in another commercial product.) Problem 3: Just coming up with a method of solution for this problem required a solid week of brain-wracking work by a trained physicist (me!) and a mathematician. Problem 4: I am not a programmer, and so am looking for a better implementation for a data structure One positive is that we don't ever (I repeat never) need to multiply any of these matrices together. They are solely used as "lookup tables" if you will. Each entry in the matrix is addressed by (row,column) and this is important. Let's say for now that each entry represents a connection between nodes and the entry at that location is significant. For example: entry (0, 2) represents a connection between city 0 and city 2 and the data stored at (0,2) would be, say, the distance between city 0 and city 2 (in double form). If you can imagine 7 cities with possible interconnections between all 7 cities (ie: (0, 1), (1, 7), (3, 4), (4, 3, etc...) where (3, 4) = (4,3) But ah! What redundancy through yonder window breaks!) you will see that connections may or may not exist, thus, there is no 'rule' per se on the sparseness of the matrix. Furthermore, entries can generally be made in any conceivable order (for 7 cities, that is quite a few permutations) However, the buck doesn't stop there! We're talking *thousands* of possible interlinks. (The data isn't cities and distances, but that is irrelevant - the behaviour is the same). Also, any given entry at some point may be removed. Speed *is*, unfortunately a great concern as the code is quite optimized right now. I think the map idea is becoming attractive. Others I work with have proposed use of a linked list or STL vector, but I am a bit discouraged by those ideas - they make searching the table a bit daunting. One question I do have concerns the maps. If each entry is indexed by 2 nodes (as above) how would a map of the form map<int index, double value> help here? Is this not basically an STL vector style implementation? Thanks for the help.
One solution is to use a Map for each row. Another solution is a map < pair xy, double distance > However, I would use the latter only if it's *really* sparse. You could run performance checks against both, but I'd expect the one-map-per-row to be faster still. OK, breakdown of my previous post (I guess it might have got lost): random index access is fastest with map, row/colum iteration can benefit from another storage scheme. so you emulate the matrix by a vector < map * >, and can keep unused rows as NULL pointer. lookup is them basically:
double GetItem(int row, int col)
{
if (below diag)
return GetItem(above diag);
map * rowMap = m_vector[row];
if (rowMap == NULL)
return 0.0;
map::iterator it = rowMap->find(col);
if (it == rowMap.end())
return 0.0;
return it->second;
}I'm still pondering a thought of a "better" storage scheme, however, the map will take you quite far. You can probably boost performance (if required) by a custom pool allocator. May I asked what you're working on? I've got 5 years of successless physics study in my backlog...
"Der Geist des Kriegers ist erwacht / Ich hab die Macht" StS
sighist | Agile Programming | doxygen -
One solution is to use a Map for each row. Another solution is a map < pair xy, double distance > However, I would use the latter only if it's *really* sparse. You could run performance checks against both, but I'd expect the one-map-per-row to be faster still. OK, breakdown of my previous post (I guess it might have got lost): random index access is fastest with map, row/colum iteration can benefit from another storage scheme. so you emulate the matrix by a vector < map * >, and can keep unused rows as NULL pointer. lookup is them basically:
double GetItem(int row, int col)
{
if (below diag)
return GetItem(above diag);
map * rowMap = m_vector[row];
if (rowMap == NULL)
return 0.0;
map::iterator it = rowMap->find(col);
if (it == rowMap.end())
return 0.0;
return it->second;
}I'm still pondering a thought of a "better" storage scheme, however, the map will take you quite far. You can probably boost performance (if required) by a custom pool allocator. May I asked what you're working on? I've got 5 years of successless physics study in my backlog...
"Der Geist des Kriegers ist erwacht / Ich hab die Macht" StS
sighist | Agile Programming | doxygenWe're trying to simulate real-time surface deformation with possible extension to a collision detection algorithm. Speed and low memory consumption are therefore very desirable.
-
We're trying to simulate real-time surface deformation with possible extension to a collision detection algorithm. Speed and low memory consumption are therefore very desirable.
-
How's it going?
"Der Geist des Kriegers ist erwacht / Ich hab die Macht" StS
sighist | Agile Programming | doxygenSlow at the moment - we're bug slaying. :mad: Our solution engine is also cranking out correct solutions, but they are sometimes translated and/or rotated (albiet correct...):rolleyes:. I therefore haven't had time to code/implement the array map yet. Soon though...:cool: Let's just say we still have some work to do. ;) I think it will eventually be a go.