Ненаправленное состояние пары

Question

Я ищу "эффективный" способ сохранения бинарного состояния при задании двух целых чисел. Если задать эти два целых числа A a B, A всегда меньше B, а диапазон значений, которые они будут содержать, составляет от 0 до N. Целое число N будет больше 2 и меньше 256.

Простое решение заключается в создании двумерного массива логических значений, но при этом остается больше половины массива неиспользованным, поскольку существуют неиспользуемые значения, когда B меньше или равно A.

Кто-нибудь знает способ использовать меньше памяти и при этом быть быстрым?

Answer 1

Если то, что вы пытаетесь сделать, похоже на индексирование элемента A [i] [j] в верхней треугольной матрице, где 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 2

Вместо создания двумерного квадратного массива вы можете создать треугольный. Например, если N равно 3, ваш массив будет (пусть первый индекс будет значением B, а второй - значением A):

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

массив [0] [0] не существует, потому что B = 0 и A = 0

массив [1] [0] существует, потому что B = 1 и A = 0

Answer 3

Потеря половины матрицы не такая уж страшная вещь. Если вы добавите новый уровень косвенное, как вы готовы сделать, вам нужно место для этих указателей, и это пространство сравнимо с целыми числами в первую очередь. Если вы производите упаковку битов, вам придется оплатить временную стоимость распаковки.

В любом случае, другое решение, которое я бы предпочел в C ++, - сохранить существующие пары в set<pair<int, int>>.

Answer 4

Вот пример кода C ++, который печатает «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;
}