Объявление огромного динамического массива с крошечными ячейками [C ++]

Question

У меня есть этот проект, над которым я работаю.Применяются следующие условия

1. В этом проекте мне нужно создать один огромный массив (надеюсь, я смогу создать его размером ~ 7,13e + 17, но эта цель еще впереди).
2. Каждая ячейка в массиве может содержать одно из трех значений: 0,1,2
3. Я использую C ++ в качестве языка.

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

int * p;
int i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int[i];

Но, насколько я понимаю, этот массив создает массив с возможным максимальным размером максимального размера типа int.Если я изменю свой код и использую следующий код

long long * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) long long [i];

, тогда каждая ячейка в массиве будет иметь тип «long long», что сделает массив очень загруженным.Есть ли способ создать массив, используя long long, чтобы определить количество ячеек в массиве и иметь каждую ячейку размером int?

Большое спасибо, Уриэль.

РЕДАКТИРОВАТЬ: для дальнейшегоИнформация.

1. Эта проблема в основном теоретическая, она является частью моей магистерской диссертации.Я все еще хотел бы, чтобы эта программа работала как можно лучше.
2. Мой текущий шаг - сделать эту работу для массива с элементами 2.56e + 09, быстрый расчет показывает, что мы говорим о массиве, который по крайней мере0,6 гигабайта, с чем моя система должна справиться.Тем не менее, я не могу достичь этой цели с моим текущим решением для кодирования, даже если требуемый объем памяти действительно равен 4,5 ГБ.

Answer 1

Есть ли способ создать массив, используя long long, чтобы определить количество ячеек в массиве и иметь каждую ячейку размером int?

Нет причин, по которым тип массива должен совпадать с типом переменной, используемой для указания размера. Поэтому используйте long long для переменной, которая задает размер, а затем int для типа массива.

int * p;
long long i;    
i=[size]; //This is calculated somewhere else.
p= new (nothrow) int [i];

---

Однако меня беспокоит, когда вы говорите, что вам нужно создать массив «размером ~ 7,13e + 17». Я не знаю, имеете ли вы в виду байты или элементы, но в любом случае это невероятно важно для прямого массива. Это входит в область петабайт данных.

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

В 64-битной программе теоретически вы можете выделить такой большой массив, насколько я знаю. Тем не менее, я скептически отношусь к тому, что большинство машин могут справиться с этим. Поскольку этот объем данных намного превышает объем оперативной памяти на машине, операционная система будет вынуждена поместить большую часть этого массива в файл подкачки. Но файл подкачки размером в петабайт намного превысил бы пространство на жестком диске на большинстве типичных машин прямо сейчас.

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

Answer 2

Поскольку вы хотите максимизировать плотность упаковки, вам лучше всего использовать битовые поля:

struct item_pack { 
    char a:2;
    char b:2:
    char c:2;
    char d:2;
};

Затем вы можете создать их массив и использовать прокси-объекты для поддержки чтения и записи отдельных файлов.элементы - при условии, что существуют некоторые ограничения на то, как много вы можете делать с прокси-объектами, поэтому вам придется быть немного осторожнее с тем, как вы пытаетесь использовать это.Небольшое рассмотрение некоторых статей о vector<bool> должно дать некоторые разумные подсказки - большинство его характеристик проистекают из этого общего типа реализации.Несмотря на недостатки контейнера общего назначения, он может работать в определенных пределах и обеспечивает более плотную упаковку информации, чем большинство очевидных альтернатив.

Answer 3

В этом проекте мне нужно создать один огромный массив (надеюсь, я смогу создать его размером ~ 7,13e + 17, но эта цель еще впереди.)

Это требует создания выделенной структуры, типа цифрового дерева (или b-дерева ) с ключом, являющимся индексом, чтобы избежать больших выделений.

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

NB ~7.13e+17 имеет длину около 60 бит.У вас даже есть оборудование, которое может поддерживать столько оперативной памяти?Не то, чтобы я внимательно следил за отраслью, но я кратко слышал об NUMA-арках с 58-битной адресной шиной, но ничего о 60-битных арках.три значения: 0, 1, 2.2.

Если ячейка может содержать только 3 значения (2.2 может быть представлено как 2), что составляет 2 бита информации.Это означает, что вы можете упаковать в значения uint32_t 16 и в значения uint64_t 32.

Вы можете попытаться найти существующую реализацию цифрового дерева (или свернуть свою собственную) и использовать в качестве верхнего ключабиты индекса.Остальные биты исходного индекса будут индексом в листе дерева, который будет массивом с упакованными значениями.В качестве примера использования std::map вместо дерева, не проверено:

enum {
   LS_BITS = 16,
   MS_BITS = 64-LS_BITS
};

enum {
   VALUE_BITS = 2,
   VALUE_MASK = ((1<<VALUE_BITS)-1)
};

// this represents an array of `1<<LS_BITS` values
struct leaf_node {
   uint64_t packed_data[ ((1<<LS_BITS)*VALUE_BITS) / (sizeof(uint64_t)*8) ];
};

// that should be a trie, to provide faster look-up
typedef std::map< uint64_t, leaf_node > big_array_type;

void
big_array_set_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   x = (x & (VALUE_MASK<<li)) | (value << li);
}

int
big_array_get_value( big_array_type &b, uint64_t index, uint64_t value )
{
   leaf_node &n = b[index >> LS_BITS];
   uint64_t li = index & ((1<<LS_BITS)-1);
   li *= VALUE_BITS;   // convert into bit offset
   uint64_t &x = n.packed_data[ li / (sizeof(uint64_t)*8) ];
   li %= (sizeof(uint64_t)*8);
   return (x >> li) & VALUE_MASK;
}

Таким образом, каждый по-прежнему тратит 0,5 бита информации, так как память составляет 2 бита, что позволяет 4 значениям, но используются только 3.Это также можно улучшить, но при гораздо более высоких затратах производительности доступа.

Answer 4

Размер, используемый для указания размера массива, должен быть типа size_t.Тип, используемый в выражении new, является типом элементов массива.Независимо от типа i в вашем примере, он будет преобразован в size_t для создания массива.

Теперь на 32-разрядной машине максимальное значение size_t составляет около 4e + 9,поэтому создание массива размером 1e + 17 не вызывает проблем.На 64-битной машине size_t теоретически может подняться примерно до 1e + 19, но вы никак не можете располагать где-то рядом с таким объемом памяти, поэтому выделение не удастся.какая-то редкая структура данных, как обсуждали другие.Ключ здесь состоит в том, чтобы решить, какое из ваших трех значений является наиболее распространенным, и хранить только значения, для которых массив является одним из двух других значений.Вы можете использовать std :: map для хранения этих значений (даже поддерживает использование синтаксиса [index]) или множества других, в зависимости от того, что именно вы пытаетесь сделать, и деталей ваших данных.

Answer 5

Но, насколько я понимаю, этот массив создает массив с возможным максимальным размером максимального размера int.Если я изменю свой код и использую следующий код

Это абсолютно неправильно!Размер массива полностью не зависит от максимального значения типа массива.

Поэтому нет необходимости делать его массивом long long.Вместо этого вы должны даже сделать его массивом char или даже меньше.

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

A char обычно составляет 1 байт, поэтому 8 бит.Чтобы сохранить 3 значения, вам нужно 2 бита;поэтому вы можете хранить 4 значения в char.

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

Answer 6

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

Значения:
0 -> 0
1 -> 1
2.2 -> 2

Хранение значений:

char values[i];
values[i] = 0;
values[i] = 1;
values[i] = 2;  // really the 2.2 value

Получение значений:

int zero = values[i] - 0;
int one  = values[i] - 0;
double two_point_two values[i] - 0;
if (two_point_two == 2)
    two_point_tow = 2.2;

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

Распределение массива:

int main ()
{   
    // static allocation requires a const size
    const int static_array_size = 100;
    char static_array[static_array_size];
    std::cout << "static array size is:" << sizeof(static_array) << std::endl;

    // heap allocation can vary in size (i.e. non const heap_array_size variable)
    int heap_array_size = 200;
    char* heap_array = new char[heap_array_size];
    std::cout << "static array size is:" << sizeof(heap_array_size) << std::endl;
}   

Answer 7

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