Содержание

FIXME черновик

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

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

Введение

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

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

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

Свойства полей

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

Представление полей

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

Важно

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

Представление логического типа

Используется решение, при котором бит выравнивается до типа 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-й бит

Представление числа целого типа

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

Представление числа вещественного типа

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

Представление символьного типа

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

Записи

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

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

тип размер
int 32
char 16
int 32
bool 8
long 64
bool 8
char 16

Упаковка записи

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

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

тип размер, бит
bool 8
bool 8
char 16
char 16
int 32
int 32
long 64

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

тип размер, бит
byte 8
char 16
char 16
int 32
int 32
long 64

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

Файлы

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

Бинарный формат

Текстовый формат

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

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

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

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

Установление правил разделения

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

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

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

Импорт данных из текстовых файлов

Импорт из CSV

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