C ++ 2,5 байта (20 бит) целое число

Question

Я знаю, что это смешно, но мне нужно это для оптимизации хранилища.Есть ли хороший способ реализовать это в C ++?

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

Answer 1

Если хранение является вашей основной задачей, я подозреваю, что вам нужно немало 20-битных переменных.Как насчет хранения их в парах?Вы можете создать класс, представляющий две такие переменные и сохранить их в 2,5 + 2,5 = 5 байт.

Для удобного доступа к переменным вы можете переопределить оператор [], чтобы вы могли написать:

int fst = pair[0];
int snd = pair[1];

Поскольку вы, возможно, захотите разрешить такие манипуляции, как

pair[1] += 5;

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

На самом деле, как предполагает @Tony, вы можете обобщить это, чтобы иметь общий контейнер, содержащий N таких 20-битных переменных.

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

Answer 2

Нет ... вы не можете сделать это как один семантический тип значения ... любые данные класса должны быть кратны 8-битному размеру символа (с учетом всех обычных подсказок о CHAR_BITS и т. Д.).

Тем не менее, давайте хвататься за соломинку ...

К сожалению, вы явно обрабатываете очень много элементов данных.Если это больше, чем 64 КБ, любой прокси-объект в пользовательском контейнере упакованных значений, вероятно, тоже будет нуждаться в> 16-битном индексе / дескрипторе, но все же одна из немногих возможностей, которую я вижу, заслуживает дальнейшего рассмотрения.Это может подойти, если вы активно работаете с семантическим поведением значений и нуждаетесь в нем только для небольшого подмножества значений в один момент времени.

struct Proxy
{
    Int20_Container& container_;  // might not need if a singleton
    Int20_Container::size_type index_;
    ...
};

Итак, прокси может быть 32, 64 или болеебиты - потенциальная выгода возможна только в том случае, если вы можете создавать их «на лету» из индексов в контейнер, делать так, чтобы они записывали прямо обратно в контейнер, и сохранять их недолговечными одновременно с несколькими.(Один простой способ - не обязательно самый быстрый - реализовать эту модель - это использовать набор битов или вектор STL в качестве Int20_Container и либо сохранить 20-кратный логический индекс в index_, либо умножить на лету.)

Также неясно, что, хотя ваши значения находятся в пределах 20-битного пространства, в действительности вы используете не более 64 тыс. Различных значений.Если у вас есть такое понимание вашего набора данных, вы можете создать справочную таблицу, в которой 16-битные индексы массива отображаются в 20-битные значения.

Answer 3

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

Но это не оптимизирует объем памяти на вашем компьютере. Особенно, если вы вставите в плоский массив, 20-битный, скорее всего, будет выровнен на 32-битной границе, поэтому преимущество 20-битного типа здесь бесполезно.

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

Answer 4

Используйте битовое поле.(Я действительно удивлен, что никто не предложил это.)

struct int20_and_something_else {
    int less_than_a_million : 20;
    int less_than_four_thousand : 12; // total 32 bits
};

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

Если вам действительно нужно оптимизировать гигантский массив из 20-битных чисел и ничего больше, есть:

struct int20_x3 {
    int one : 20;
    int two : 20;
    int three : 20; // 60 bits is almost 64

    void set( int index, int value );
    int get( int index );
};

Вы можете добавить функции получения / установки всделайте его красивее, если хотите, но вы не можете взять адрес битового поля, и они не могут участвовать в массиве.(Конечно, вы можете иметь массив struct.)

Использовать как:

int20_x3 *big_array = new int20_x3[ array_size / 3 + 1 ];

big_array[ index / 3 ].set( index % 3, value );

Answer 5

Вы можете использовать C ++ std :: bitset .Сохраняйте все в битах и ​​получайте доступ к своим данным, используя правильный индекс (x20).

Answer 6

Вы не сможете получить ровно 20 битов как тип (даже с битовой структурой), так как он всегда будет выровнен (с наименьшей зернистостью) к байту.Imo единственный способ, если у вас есть 20 битов, это создать поток битов для обработки данных (который вы можете перегрузить, чтобы принять индексацию и т. Д.)

Answer 7

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

Answer 8

Хотя это можно сделать несколькими способами. Одной из возможностей было бы использование битового скручивания для сохранения их в виде левой и правой частей 5-байтового массива с классом для хранения / извлечения, который преобразует желаемую запись массива в запись массива в массиве byte5 [] и извлекает левый или правый половина в зависимости от обстоятельств.

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

Я думаю, что было бы более эффективно увеличить пространство подкачки и позволить виртуальной памяти позаботиться о вашем большом массиве (в конце концов, 20 на 32 - не большая экономия!), Всегда предполагая, что у вас 64-битная ОС.

Answer 9

Просто идея: использовать оптимизированное хранилище (5 байтов для двух экземпляров), а для операций преобразовать его в 32-битное целое число и затем обратно.

Answer 10

Насколько я знаю, это невозможно.

Самый простой вариант - определить пользовательский тип, который использует int32_t в качестве резервного хранилища и реализует соответствующие математические операции в качестве операторов переопределения.

Для лучшей плотности хранения вы можете хранить 3 int20 в одном значении int64_t.