2

I need to implement a very large matrix, say NxN in Standard C. The matrix must store a truth table, that is 

matrix[i][j] = [true|false]

I know I could simply use a int matrix, or boolean type if using C99, but was looking for the most lightweight solution in terms of memory.

Improve this question
5
  • What's wrong with using one bit per cell and storing bits in, say, unsigned longs? Commented Feb 14, 2012 at 18:07
  • @n.m., that is actually the solution I've implemented so far, but I wanted to know if there is a more efficient solution (and very interesting answers are coming along :) ) Commented Feb 14, 2012 at 18:11
  • Is the truth table equally filled with 1 and 0? Is it random? Is it sparse or dense? How much are typical N and M? Commented Feb 14, 2012 at 18:16
  • 1
    If you know a bit more about statistical properties of the data, you perhaps can select a good compression scheme for it. Otherwise it's the most efficient method. Commented Feb 14, 2012 at 18:26
  • I must implement a percolation cluster, and every element of the matrix must be filled with 0 or 1 with a varying probaility. I'm particulary interested in the case the matrix is dense. N and M should be ~10000 Commented Feb 14, 2012 at 18:36

4 Answers 4

Reset to default
4

The most lightweight solution in terms of memory is saving eight boolean in a char:

unsigned char getBit(char byte, unsigned short bit){ assert(bit < 8); return byte&(1<<bit); }

Then you can store a N x 8M matrix by saving the bytes in each row. If many of those bytes are empty then you should use a sparse matrix format, for example compressed spares row.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

could this help avoiding cache trashing too?
Well, if you're going to iterate over rows - maybe. The solution above uses exactly one bit for a boolean. However, when calculating or manipulating your matrix you should avoid using a function like getBit and manipulate the bytes directly using |,^,&,~ and constant bitset marks as 0x01, 0x02, 0x04 to ensure optimization.
Thanks, actually I found some useful macros to deal with bitwise operations directly on the code without using any function... hope it will work... :)
2

You might want to use a hash implementation or a list of lists if the matrix is particularly sparse.

Also if the i or j is less than the largest integer your system can store you can pack a boolean bitset into a single integer with each bit corresponding to one index. You can then access or modify this using bitwise operations.

Improve this answer

Comments

0

Isn't it what std::bitset is for ?

Improve this answer

1 Comment

I'm not using C++ right now, anyway thanks for the reference :)
0

if there is a more efficient solution

If you want to store more than 1 boolean in single bit, you need to use some compression.

Compression will work only on non-random data; And random access to compressed data can be slow.

Easiest one method is RLE (compress each row independently). A bit more complex is storing data in sparse matrix (only if you have much more 0 values than 1; this method can compress multi-dimensional data).

Much more complex compression is used here: http://crd-legacy.lbl.gov/~kewu/fastbit/index.html It is named "Word-Aligned Hybrid compression scheme"

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.