Undirected Pair State

Question

두 개의 정수가 주어질 때 이진 상태를 유지하는 "효율적인"방법을 찾고 있습니다. 이 두 정수 A와 B를주는 A는 항상 B보다 작고 포함 할 값의 범위는 0에서 N까지입니다. 정수 N은 2보다 크고 256보다 작습니다.

간단한 해결책은 다음과 같습니다. 부울 값의 2 차원 배열을 만들지 만 B가 A보다 작거나 같은 경우 사용하지 않는 값이 있으므로 배열의 절반 이상을 사용하지 않습니다.

메모리를 적게 사용하는 방법을 알고있는 사람이 있습니까? 여전히 "빠르다"?

Answer 1

정사각형 인 2 차원 배열을 만드는 대신 삼각형 모양을 만들 수 있습니다. 예를 들어 N이 3이면 배열은 다음과 같습니다 (첫 번째 인덱스를 B의 값으로, 두 번째 인덱스를 A의 값으로 둡니다).

부울 [] [] 배열 = {{}, {false}, { 거짓, 거짓}};

어레이 [0] [0]이 어떤 경우 B = 0 및 A = 0

배열 [1] [0] 때문에 B = 1, A = 0

Answer 2

존재하기 때문에 존재하지 않는하면 예를 들어 만약에 대한

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

: 수행하려고하는 소자 A [i]를 N 행의 개수는 상부 삼각 행렬의 [j]가,이 같은 색인을 계산할 수 인덱싱 비슷 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를 비트의 선형 배열로 만들면 꽤 컴팩트해야합니다.

반면에 배열의 한 요소 만 설정되면 이전의 경우 N (N + 1)을 기억해야하기 때문에 (A, B) 쌍을 저장하고 완료 할 수 있습니다. 1)/2 비트이고, 후자의 경우 2 * log (N) 비트 (기본 2) 만 기억하면됩니다.

Answer 3

다음은 쌍이 존재하는 경우 "쌍"을 인쇄하는 몇 가지 예제 C++ 코드입니다. 이것은 단지 예일뿐입니다. 생산 코드에서는 행렬의 절반을 낭비 등

#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

그런 끔찍한 일이 아니다 ... N은 컴파일 시간을 알 수 없습니다 나는 할당 된 메모리를 삭제합니다. 새로운 수준의 간접 지정을 추가하면 기꺼이 그 포인터를위한 공간이 필요하며 그 공간은 처음에 정수의 공간과 비교할 수 있습니다. 어떤 종류의 포장을하는 경우, 포장 풀기의 시간 비용을 지불해야합니다.

어쨌든 C++에서 선호하는 다른 솔루션은 현재 쌍을 set<pair<int, int>>에 저장하는 것입니다.