无向对状态

Question

我正在寻找一种“有效”的方式来持久化给定给两个整数的二进制状态。给定这两个整数A和B，A总是小于B，它们包含的值的范围是0到N。整数N将大于2小于256。

简单的解决方案是创建一个布尔值的二维数组，但这会留下超过一半的数组未使用，因为当B小于或等于A时，有未使用的值。

有没有人知道一种既能使用更少的内存又能保持“快速”的方法？

Answer 1

您可以创建三角形数组，而不是创建正方形的二维数组。例如，如果N是3，您的数组将是(让第一个索引是B的值，第二个是A的值)：

布尔数组= {{}，{false}，{false，false}}；

数组不存在，因为B=0和A=0

array1之所以存在，是因为B=1和A=0

Answer 2

如果您尝试执行的操作类似于索引上三角矩阵中的元素Ai，其中N是行数，则可以按如下方式计算索引：

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

例如，如果N=4和i=1、j=2，则矩阵中的索引为

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

那么把(I，J)改编成你的(A，B)应该不会太难。如果你让A是一个线性的位数组，那应该是非常紧凑的。

另一方面，如果只设置了数组中的一个元素，您可以只保存(A，B)对并完成它，因为在前一种情况下，您需要记住N(N+1)/2位，而在后一种情况下，您只需要记住2*log(N)位(基数2)。

Answer 3

下面是一些示例C++代码，如果存在" pair“，它会输出”pair“。这只是一个例子。在生产代码中，N在编译时是未知的，我将删除分配的内存...等。

#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;
}