Remi.b Remi.b - 10 days ago 4
C++ Question

Data structure for a matrix containing many zeroes?

In C++, I have to save in the RAM a very large square matrix that is made of about 90% (true frequency of zeroes depend upon the user input) of zeroes. It would be a waste of RAM to allocate memory for all these zeroes.

How could one make a class that uses little RAM and is convenient to reach an element with something like

into this big matrix?


There are many ways to go. But first thing to consider is that you'll get a good hit in performance for doing this as accessing elements will become more complicate. Second, you'll be unable to use famous libraries like LAPACK, because as far as I know, they don't provide any interface for such complicated data structures. So, every time you want to do some Mathematical operation, you'll have to either decompress your matrix and flatten it, or you'll have to redevelop the code that does the operation you want to do, which is not really an easy thing to do. The people that did LAPACK did research that for years.

What I'm saying is: Consider the consequences before doing this.

Now after mentioning the consequences, I can mention a method off the top of my head.

  1. imagine your matrix as a flat array, order in column major (hence column after column in memory), contiguous in memory.
  2. Now this matrix is a list that has many zeros. Your question is: How do we eliminate these zeros?

Well there are many ways to go, and each method will have different computational complexity that depends on your application, let me mention some of the way:

  • You could use a linked list, where every element can be std::pair, containing the value of the current matrix element, and the index of the next available element.

  • You could use a linked list, and you could use the way some compression software works, and count how many zeroes you have before every element, and store it in a container for every element.

You see, there are really many ways to go... I could think and guess another few. But ask yourself: What's the computational complexity you're looking for?

Hope this helps.