как эффективно получить доступ к 3 ^ 20 векторам в 2 ^ 30 битах памяти

Question

Я хочу сохранить 20-мерный массив, где каждая координата может иметь 3 значения в минимальном объеме памяти (2 ^ 30 или 1 гигабайт).Это не разреженный массив, мне действительно нужно каждое значение.Кроме того, я хочу, чтобы значения были целыми числами произвольной, но с фиксированной точностью, скажем, 256 бит или 8 слов * пример 1001 *

;

set_big_array(1,0,0,0,1,2,2,0,0,2,1,1,2,0,0,0,1,1,1,2, some_256_bit_value);

и

get_big_array(1,0,0,0,1,2,2,0,0,2,1,1,2,0,0,0,1,1,1,2, &some_256_bit_value);

Поскольку значение3 - относительное простое число 2. Его трудно реализовать с помощью эффективного побитового сдвига и и или операторов.Я хочу, чтобы это было как можно быстрее.

есть мысли?

Answer 1

Мне кажется сложно без какого-либо сжатия:

3^20 = 3486784401 values to store
256bits / 8bitsPerByte = 32 bytes per value
3486784401 * 32 = 111577100832 size for values in bytes
111577100832 / (1024^3) = 104 Gb

Вы пытаетесь уместить 104 Гб в 1 Гб.Для данных должен быть какой-то шаблон, который можно использовать для его сжатия.

Извините, я знаю, что это не сильно поможет, но, возможно, вы можете переосмыслить свою стратегию.

Answer 2

Есть 3.48e9 вариантов 20-ти наборов индексов, которые равны 0,1,2. Если вы хотите сохранить 256-битное значение для каждого индекса, это означает, что вы говорите о 8,92e11 битах - о терабитах или о 100 ГБ.

Я не уверен, что вы пытаетесь сделать, но это звучит дорого в вычислительном отношении. Он может быть приемлемым в качестве файла с отображением в памяти и может быть достаточно быстрым в качестве файла с отображением в памяти на SSD.

Что вы пытаетесь сделать?

Таким образом, практическим решением было бы использовать 64-битную ОС и большой файл с отображенной памятью (предпочтительно на SSD) и просто вычислить адрес для данного элемента типичным способом для массивов, то есть как sum-of(forall-i(i-th-index * 3^i)) * 32 bytes в псевдо-математике. Или используйте очень-очень дорогую машину с таким большим объемом памяти или другой алгоритм, который не требует этот массив.

Несколько замечаний по платформам: Windows 7 поддерживает только 192 ГБ памяти, поэтому использование физической памяти для подобной структуры возможно, но реально ее продвигает (более дорогие версии поддерживают больше). Если вы можете найти машину на все, что есть. Согласно странице Microsoft по этому вопросу виртуальное адресное пространство в пользовательском режиме составляет 7-8 ТБ, поэтому mmap / виртуальная память должна быть выполнимой. Алекс Ионеску объясняет , почему существует столь низкий предел виртуальной памяти, несмотря на явно 64-битную архитектуру . Википедия устанавливает адресные ограничения linux на 128 ТБ , хотя, вероятно, это до разделения ядра / пользовательского режима.

Предполагая, что вы хотите обратиться к такому многомерному массиву, вы должны обработать каждый индекс по крайней мере один раз: это означает, что любой алгоритм будет иметь значение O (N), где N - это число индексов. Как упоминалось ранее, вам не нужно преобразовывать в адресацию base-2 или что-либо еще, единственное, что имеет значение, - это то, что вы можете вычислить смещение integer - и то, на каком основании происходит математика, не имеет значения. Вы должны использовать максимально компактное представление и игнорировать тот факт, что каждое измерение не кратно 2.

Таким образом, для 16-мерного массива эта функция вычисления адреса может быть:

int offset = 0;
for(int ii=0;ii<16;ii++)
    offset = offset*3 + indexes[ii];
return &the_array[offset];

Как уже говорилось, это обычная формула индексации массива, ничего особенного в этом нет. Обратите внимание, что даже для "всего лишь" 16 измерений, если каждый элемент составляет 32 байта, вы имеете дело с чуть более гигабайтом данных.

Answer 3

Я начну с прямого вычисления адреса, а затем посмотрю, смогу ли я его оптимизировать

адрес = 0; для (я = 15; я> = 0; я--) { адрес = 3 * адрес + массив [i];
}

address = address * number_of_bytes_needed_for_array_value

Answer 4

Может быть, я неправильно понял ваш вопрос.Но вы не можете просто использовать обычный массив?

INT256 bigArray[3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3];
OR
INT256 ********************bigArray = malloc(3^20 * 8);

bigArray[1][0][0][1][2][0][1][1][0][0][0][0][1][1][2][1][1][1][1][1] = some_256_bit_value;

и т. Д.

Редактировать: не будет работать, потому что вам нужно 3 ^ 20 * 8Byte = ca.25GByte.Неправильный вариант malloc.

Answer 5

Вы можете использовать указатель на массив ²⁰ , чтобы ваш компилятор реализовал для вас вычисления индекса:

/* Note: there are 19 of the [3]'s below */
my_256bit_type (*foo)[3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3][3];

foo = allocate_giant_array();

foo[0][1][1][0][2][1][2][2][0][2][1][0][2][1][0][0][2][1][0][0] = some_256bit_value;

Answer 6

Возможно, вы захотите взглянуть на нечто вроде STXXL , реализацию STL, предназначенную для обработки очень больших объемов данных

Answer 7

2 ^ 30 бит - это 2 ^ 27 байт, поэтому на самом деле это не гигабайт, а восьмая часть гигабайта.

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

Если вам не требуется немедленный «случайный» доступ, ваше решение может быть двухбитовым словом «переменного размера», так что ваше наиболее часто хранящеесязначение занимает только 1 бит, а два других - 2 бита.

Если 0 является вашим наиболее распространенным значением, то: 0 = 0 10 = 1 11 = 2

или что-то в этом роде.

В этом случае вы сможете хранить свои биты в последовательности таким образом.

Это может занять до 2 ^ 40 битов, но, вероятно, не будет.Вы можете предварительно просмотреть свои данные и посмотреть, какое из них является наиболее часто встречающимся, и использовать его для обозначения своего однобитового слова.Вы также можете сжать данные после того, как вы их сериализовали до 2 ^ 40 битов.

Я предполагаю, что вы будете использовать диск, возможно, с отображением памяти, поскольку вряд ли у вас будет так много доступной памяти.

Я предполагаю, что пространство - это все, а не время.