Undirected Pair State

Question

I'm looking for an "efficient" way to persist a binary state when given to two integers. Giving these two integers A an B, A is always less than B and the range of values which they will contain is 0 through N. The integer N will be greater than 2 and less than 256.

The simple solution is to create a two-dimensional array of Boolean values, but that leaves more than half of the array unused because there are unused values when B is less than or equal to A.

Does anyone know of a way to use less memory and still be "fast?"

Answer 1

Rather than creating a two-dimensional array that is square you can create one that is triangular. For example if N is 3 your array would be (Let the first index be the value of B and the second be the value of A):

boolean[][] array = {{},{false},{false,false}};

array[0][0] doesn't exist because B = 0 and A = 0

array[1][0] exists because B = 1 and A = 0

Answer 2

If what you are trying to do is similar to indexing the element A[i][j] in an upper-triangular matrix, where N is the number of rows, you can calculate the index like this:

A[ N*j - j*(j-1)/2 + i ]

for example if N=4, and i=1, j=2, then the index in the matrix is
4*2 - 2*1/2 + 1 = 8-1+1 = 8

    0  1  2  3
0: 0  4  7  9
1: 1  5  8 
2: 2  6  
3: 3

Then it shouldn't be too hard to adapt the (I,J) to your (A,B). Then if you let A be a linear array of bits, that should be pretty compact.

On the other hand, if only one element of the array is ever set, you could just save the (A,B) pair and be done with it, because in the former case you need to remember N(N+1)/2 bits, while in the latter case you only need to remember 2*log(N) bits (base 2).

Answer 3

Here's some example C++ code that prints "pair" if the pair exists. This is just an example. In production code, N won't be known a compile-time and I would delete the allocated memory... etc.

#include <iostream>
using namespace std;
template<typename T>
void foo ( ) {
   const int n = 3;
   const unsigned int a = 8; // align to "a" bytes
   // find the size of the first dimension
   unsigned int s = (n-1) * sizeof(T**);
   // find a size that aligns the second dimension
   if (s%a) s=s/a*a+a;
   T** p = (T**) malloc(s +
                        (n*n-n)/2 * sizeof(T));
   T* j = (T*)p + s;
   for (int i=0; i<n-1; i++) {
      p[i] = j - (i+1);
      j += (n - (i+1)) * sizeof(T);
   }
   // the "pair matrix" hasn't been populated
   for (int i=0; i<n-1; i++)
      for (int j=i+1; j<n; j++)
         if (p[i][j])
            cout << "pair" << endl;
}

int main(int argc, char* argv[])
{
   foo<bool>();
   return 0;
}

Answer 4

Wasting half of a matrix isn't such a terrible thing. If you add a new level of indirection, as you are willing to do, you need space for those pointers, and that space is comparable to that of integers in the first place. If you do any kind of bit packing, you will have to pay the time cost of the unpacking.

Anyway, the other solution I would prefer in C++ is storing the present pairs into a set<pair<int, int>>.