короткий короткий int в c?

Question

Я пытаюсь выжать как можно больше из моей памяти. У меня есть матрица 4.9999995e13 целых, но они должны быть только истинными или ложными - в основном мне нужен только один бит памяти для каждой из этих целых.

Я понимаю, что в C нет однобитовых типов (может быть, кто-то может объяснить, почему, для меня), и я также знаю, что если бы существовал short short int, то это был бы 1 байт, такой же, как у char. Однако все логические операции в C возвращают целые числа (а также некоторые другие функции).

Итак, мои вопросы:

• Есть ли способ заставить short short int существовать?
• Если бы я вместо этого использовал char, уменьшилось бы ли у меня быстродействие из-за всех приведений к int, которые нужно было бы сделать?
• Есть ли другой способ, по которому я скучаю?

На всякий случай это актуально, я компилирую с GCC для C99.

РЕДАКТИРОВАТЬ Я только что видел на этой странице википедии , что существует тип _Bool, это действительно стандарт?

Answer 1

Тип __Bool является стандартным в самой последней версии C, но это по-прежнему не то, что вам нужно, потому что __Bool по-прежнему занимает как минимум один байт (как и char, по определению).

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

Answer 2

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

И не существует такого понятия, как short short int, это просто char, которыйявляется наименьшим целочисленным классом хранения в C.

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

Небольшой пример может помочь проиллюстрировать:

Использование обычной целочисленной матрицы:

int mat[8*8]; // assuming row major order
int is_element_set(int x, int y) { 
  return mat[y*8 + x];
}

С битовой картой:

unsigned char mat[8]; // assuming CHAR_BIT == 8
int is_element_set(int x, int y) { 
  return mat[y] & (1 << x);
}

Answer 3

У вас есть около 50 терабит данных. Вы хотите поместить их все в оперативную память одновременно? Было бы совершенно безумно использовать более одного ОЗУ в порядке, чтобы хранить один бит информации, и даже тогда ваш компьютер должен был бы быть размером с самый большой суперкомпьютер на этой планете. Забудьте о производительности бит-упаковки. Вам придется беспокоиться о совершенно разных вещах.

Answer 4

5e13 - это около 5,6 терабайт хранилища, которое вам понадобится только для представления вашего битового поля.Вероятно, есть лучший способ решить вашу проблему.

Answer 5

Как и другие люди, вероятно, вам следует использовать битовое поле.

Кроме того, если вы просто используете значения true / false, и одно из значений гораздо менее распространено, чем другое,рассмотреть возможность использования неявного кодирования.Вы можете сделать это легко с помощью структуры данных карты.Поскольку вы выполняете работу с графиками, это сэкономит вам огромный объем памяти, если ваш график вообще невелик.Если вы объедините это с методами упаковки битов, описанными выше, вы можете даже поместить все это в оперативную память.Однако нужно быть довольно умным в отношении индексирования.

Еще одна вещь, которую вы могли бы сделать, если вам не нужно, чтобы производительность снижалась во время обработки (т. Е. Если вы больше беспокоитесь о хранении *)1006 * это, чем обрабатывать его), выполняется структура через алгоритм сжатия в блоках.Есть библиотека C для bzip2, которая может сэкономить вам 90% или больше на чем-то подобном.Недостатки в том, что это займет (очень!) Много времени.Вы можете получить сравнимую производительность от побитового компрессора, такого как Dynamic Markov Compression (DMC), и это намного быстрее.

Answer 6

C99 stdbool.h позволяет использовать bool.Однако здесь ваша проблема в том, что 4.9999995e13 / 8 даст более или менее 6.2500e + 12 ($ 10 ^ 9 $ - Гбайт, $ 10 ^ 12 $ - Тбайт), поэтому вам нужно более 6 Тбайт реальной + виртуальной памяти (чтобысчастливый).Это говорит о том, что вы делаете что-то еще не так.Вам необходимо «масштабировать» свою проблему в подзадачах, которые вы можете решить, используя меньше памяти.

Answer 7

Возможно, вы могли бы использовать некоторую мудрую реализацию структур битовых полей, доступных в ANSI C.

Примерно так:

typedef struct node_t_
{
    char bit0 : 1;
    char bit1 : 1;
    char bit2 : 1;
    char bit3 : 1;
    char bit4 : 1;
    char bit5 : 1;
    char bit6 : 1;
    char bit7 : 1;
} node_t;

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

Answer 8

Я пытаюсь выжать как можно больше из моей памяти.

Если бы это было правдой, вы бы не потратили 8 битов на хранение данных на 1 бит. Вы бы использовали битовое поле.

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

Если нет, то 4.9999995e13 займет около 6 ТБ ОЗУ!