Задача 26. Форматы данных

и эффективность. Часть 1: игры в сжатие. Сложность: 4

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

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

1. Какой из перечисленных стандартных контейнеров использует меньше памяти для хранения одного и того же количества объектов одинакового типа т; deque, list, set или vector? Поясните свой ответ.

Вопрос для профессионала

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

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

а) 128 байтов на полуход

б) 32 байта на полуход

в) от 4 до 8 байтов на полуход

г) от 2 до 4 байтов на полуход

д) 12 битов на полуход

Решение

1. Какой из перечисленных стандартных контейнеров использует меньше памяти для хранения одного и того же количества объектов одинакового типа т: deque, list, set или vector? Поясните свой ответ.

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

• vector<T> хранит данные в виде непрерывного массива объектов т и, таким образом, не имеет никаких дополнительных расходов на хранение одного элемента.

• deque<T> может рассматриваться как vector<T>, внутреннее представление которого разбито на отдельные блоки. deque<T> хранит блоки, или "страницы" объектов. Для этого требуется по одному дополнительному указателю на страницу, что обычно приводит к дополнительным расходам памяти, составляющим доли бита на один элемент. Других дополнительных затрат памяти нет, по

скольку у deque<T> нет никаких дополнительных указателей или другой информации для отдельных объектов Т.

• list<T> представляет собой двухсвязный список узлов, которые хранят элементы т. Это означает, что для каждого элемента т в list<T> хранятся также два указателя, которые указывают на предыдущий и последующий узлы списка. При вставке нового элемента в список мы создаем два дополнительных указателя, так что дополнительные затраты контейнера list<T> составляют два указателя на один хранимый элемент.

• И наконец, set<T> (и аналогичные в данном отнощении multiset<T>, тар<Кеу,Т> и multimap<Key,т>) также гранят объекты т (или pair<const кеу,т>) в узлах. Обычная реализация set<T> включает три дополнительные указателя на каждый узел. Зачастую, услышав об этом, многие спрашивают: "Откуда три указателя? Разве недостаточно двух ~ на левый и правый дочерние узлы?" Дело в том, что требуется еще один указатель на родительский узел, иначе задача определения "следующего" узла по отношению к некоторому произвольно взятому не может быть решена достаточно эффективно. (Возможны и другие способы реализации этих контейнеров; например, можно воспользоваться структурой списков с чередующимися пропусками (alternating skip list) - но и в этом случае требуется как минимум три указателя на каждый элемент (см. [МагпеОО]).)

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

Различные способы представления данных

Цель второго вопроса задачи - п р о де м о н стри ро вать, что может быть множество способов представления одной и той же информации.

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

В оставшейся части задачи мы используем следующие стандартные термины и аббревиатуры: К King (Король) Q Queen (Ферзь) R Rook (Ладья) В Bishop (Слон) N Knight (Конь) Р Pawn (Пешка)

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

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

а) 128 байтов на полуход

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

Q. R, -в", n, "Р" или . .

Используя эту схему и сохраняя доску по горизонталям от 1 до 8, и по вертикалям от я до А в пределах каждой горизонтали, возможное представление полухода может быть таким:

WRWNWBWQWKWBWNWR wpwpwp..WPWPWPWP

......WP........

ВРВРВРВРВРВРВРВР

brbnbbbqbkbbbnbr

.Здесь представлен полуход "1. d4", с которого я обычно начинаю партию.

б) 32 байта на полуход

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

Мы можем снизить количество необходимой памяти до 32 байт на полуход, храня всего лишь 4 бита информации для каждой клетки: 3 бита для указания фигуры (например, представление О для короля, 1 для ферзя, 2 для ладьи, 3 для слона, 4 для коня, 5 для пешки и 6 - для пустой клетки требуется 3 бита, при этом одно значение остается неиспользованным), и 1 бит для цвета (значение этого бита игнорируется для пустой клетки).

При использовании такой схемы для сохранения всей доски как и ранее, по горизонталям от 1 до 8, и по вертикалям от а до А в пределах каждой горизонтали, требуется всего лишь 32 байта:

хххххххххххххххххххххххххххххххх

в) от 4 до 8 байтов на полуход

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

Старая "описательная" запись шахматной партии идентифицирует клетки с использованием дескрипторов переменной длины, наподобие КЗ или QN8 вместо двух-символьных дескрипторов вроде еЗ или Ь8. Для записи полухода при этом требуется как минимум 4 символа (например, P-Q4) и не более 8 символов (например, RKN1 -КВ1, Р-КВ8(0)). Заметим, что никакие завершающие нули или другие ограничители строк не требуются, поскольку записанные таким образом ходы дешифруются однозначно.

При этой схеме запись полухода может выглядеть как

p-kb8(q)

г) от 2 до 4 байтов на полуход

Это достигается путем хранения полуходов как текста в современной записи шахматных партий.

Современная "алгебраическая" запись более компактна, и любой полуход можно записать с использованием от 2 символов (например, d4) до 4 символов (например.