Использование памяти для сопоставления элементов со строго возрастающими значениями - PullRequest
Новая
       112

Использование памяти для сопоставления элементов со строго возрастающими значениями

1 голос
/ 09 мая 2020

Структура данных и использование карты M

В моем коде карта называется M и определяется как 

class T
{
public:
    size_t a;
    size_t b;
    size_t c;
    size_t d;
    size_t e;
    size_t f;

    size_t sum()
    {
        return a+b+c+d+e+f;
    }
}

const std::vector<T> M;

M - это const. Он создается в начале длительного процесса и затем используется только для чтения сопоставления между индексом i и значениями a, b, c, d, e и * 1018. *. Например, 

auto& c = M[i].c;

Свойства карты

Первый элемент карты всегда имеет sum 1. Для каждого из следующих элементов всегда , один и только один из 6 атрибутов (a, b, c, d, e или f) увеличивается ровно на 1. Другими словами, следующие утверждения о карта всегда верна 

if (i < M.size())
{
   if (i >= 0)
       assert(M[i].sum() == i+1);

   if (i > 0)
   {          
       assert(M[i].sum() - M[i-1].sum() == 1);
       assert(M[i].a == M[i-1].a || M[i].a == M[i-1].a + 1);
       assert(M[i].b == M[i-1].b || M[i].b == M[i-1].b + 1);
       assert(M[i].c == M[i-1].c || M[i].c == M[i-1].c + 1);
       assert(M[i].d == M[i-1].d || M[i].d == M[i-1].d + 1);
       assert(M[i].e == M[i-1].e || M[i].e == M[i-1].e + 1);
       assert(M[i].f == M[i-1].f || M[i].f == M[i-1].f + 1);
   }
}

Проблема и вопрос

Эта система работала хорошо до недавнего времени, потому что теперь мне нужно M длиной 5e8, что заканчивается занимая много ненужной оперативной памяти.

Есть ли способ создать карту, которая обеспечивает постоянный доступ по времени к сопоставлению между i и a, b, c , d, e или f, не занимая столько ОЗУ?

1 Ответ

0 голосов
/ 09 мая 2020

Если вы знаете предыдущее значение, этого достаточно, чтобы знать, какая из переменных увеличилась на единицу. Поскольку их шесть (a, b, c, d, e, f), вы можете представить эту информацию 3 битами. Для n -элементов вам понадобится всего 3 * n бит.

С точки зрения размера, это улучшение, но это нарушит ваше ограничение постоянного доступа, так как вам нужно повторять по всем предыдущим записям для каждого поиска. Но вы можете найти компромисс между скоростью и памятью, но сохранением снимков. Например, если вы сохраняете снимки после 100 элементов, вам в худшем случае придется перебирать последние 100 записей. Это все еще O(1).

Вам нужно будет настроить размер шага снимков, но пока вы используете постоянное число, у вас будет O(1) поиск.

...