Хранение базовых типов данных в структурах данных

Автор — Romtek 2009/10/09 17:07

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

Как это сделать?

Сперва необходимо определить следующие параметры:

• Свойства полей
• Количество записей

Базовые типы полей могут быть:

• числами
  • целыми
  • вещественными
• логическими (ПРАВДА/ЛОЖЬ)
• символами

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

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

• bool/boolean: TRUE/FALSE (8 бит)
• wordbool: TRUE/FALSE (16 бит)
• longbool: TRUE/FALSE (32 бита)

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

Для проверки бита nBit числа N:

((N SHR nBit) AND 1)

Для установки бита nBit (TRUE) числа N:

N := N OR (1 SHL nBit)

Для очистки бита nBit (FALSE) числа N:

N := N AND NOT (1 SHL nBit)

Для переключения бита nBit числа N:

N := N XOR (1 SHL nBit)

Примечание:
nBit начинается с нулевого/младшего бита (lsb)

Для того, чтобы сохранить, допустим, 3 битовых флага (FALSE,TRUE,TRUE), нужно:

1. обнулить переменную N
2. сбросить 0-й бит
3. установить 1-й бит
4. установить 2-й бит

Целые типы могут быть представлены несколькими предопределёнными типами:

• byte: -128 .. 127 (8 бит)
• short/shortint: -32,768 .. 32,767 (16 бит)
• int/integer: -2,147,483,648 .. 2,147,483,647 (32 бита)
• long/longint: -9,223,372,036,854,775,808 .. 9,223,372,036,854,775,807 (64 бита)

Вещественные типы могут быть представлены несколькими предопределёнными типами:

• float/shortreal: -3.4E38 .. 3.4E38, INF (32 бита)
• double/real: -1.8E308 .. 1.8E308, INF (64 бита)

Символьный тип может быть представлен:

• char: 0X .. 0FFFFX (16 бит)

Каждая запись хранит информацию о наборе базовых типов. Определение записи подразумевает собой набор неоднородных типов.

Рассмотрим запись, состоящую из набора переменных, типы которых {int,char,int,bool,long,bool,char}. А теперь подсчитаем сколько байт занимают типы:

Некоторые компиляторы предоставляют возможность упаковки записей. Это означает, что каждое поле записи хранится без выравнивания до ближайшего числа, кратного 2. Таким образом, если упаковать эту запись, её размер будет 176 бит (22 байта).

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

то мы видим, что два идущих рядом типа bool можно упаковать в один. Итоговая запись может выглядеть так:

Таким образом, теперь в byte хранятся значения двух логических типов, если упаковать биты методом, упомянутым выше.
Итого 168 бит (21 байт).

Данные можно хранить в бинарном и текстовом форматах и у каждого из них есть свои преимущества и недостатки. Давайте рассмотрим их.

Преимуществами хранения данных в текстовом формате являются:

1. прозрачная читаемость человеком

К недостаткам следует отнести:

1. отсутствие чёткого определения правил по разделению полей и записей
2. увеличение размера, необходимого для хранения данных, ведущее к дополнительной избыточности информации
3. уменьшение скорости извлечения хранимых данных

Признак окончания:

• поля
• записи

Поля могут разделяться различными лексемами: «.» , «,» , « », «:» и т.д.

Записи разделяются, как правило разделителем строки: CR/LF (Windows) CR (UNIX), LF (Mac).

CSV - Comma Separated Value (англ. Значения, Разделённые Запятыми)