CS
Задачник Базовый курс EN

Задача

Выравнивание полей

замеры жадность сортировка симуляция

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

Размеры и выравнивания на 64-битной машине:

ТипыРазмерВыравнивание
bool, int8, uint8, byte11
int16, uint1622
int32, uint32, rune, float3244
int64, uint64, int, uint, uintptr, float64, указатель *T, map[K]V88
string, any, error, complex128168
срез []T248
массив [k]Tk · размер Tкак у T
структура, описанная раньше во входееё размереё выравнивание

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

Вход

В первой строке q (1 ≤ q ≤ 1000) — число структур. Дальше структуры по порядку: строка с именем и числом полей k (1 ≤ k ≤ 12), затем k строк «имя тип». Тип записан без пробелов и ссылается только на типы из таблицы и на структуры, описанные выше; размер любой структуры не больше 10⁹.

Выход

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

Примеры

Пример 1

Вход
2
Event 6
Done bool
Mag float64
Deep bool
Year int32
Felt bool
Count int64
Quake 7
Time string
Lat float64
Lon float64
Depth float64
Mag float64
MagType string
Place string
Выход
Event 40 24
Quake 80 80

Ограничения

Время · Python
3000 мс
Время · Go
1000 мс
Память
256 МБ
Проверка
6 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Размер каждого типа кратен его выравниванию. Что будет, если класть поля от самого строго выровненного к самому слабому?

2Идея

Размер в описанном порядке — прямое моделирование: смещение растёт, перед каждым полем округляется вверх до кратного его выравниванию, в конце — до кратного наибольшему выравниванию. Для наименьшего размера отсортируем поля по выравниванию, от большего к меньшему, и посчитаем так же. Вложенные структуры, массивы и сложные типы сводятся к паре «размер, выравнивание» рекурсивно.

3Разбор

Почему сортировка по выравниванию оптимальна. Размер любого порядка — не меньше суммы размеров полей, округлённой вверх до кратного наибольшему выравниванию A: в нём лежат все поля, и размер структуры кратен A. А порядок по убыванию выравнивания этой границы достигает. Выравнивания — степени двойки, и пока идут поля с выравниванием a, смещение кратно a: все предыдущие поля имели выравнивание не меньше a, а их размеры кратны их выравниваниям, значит, и a. Пустых байт между полями не остаётся — только хвост в конце.

Сортировать по размеру — частая ошибка, которая обычно работает. Не работает она, когда размер не равен выравниванию: массив [3]int32 весит 12 байт при выравнивании 4. Поставленный перед int64, он сдвигает его на 4 байта — во втором тесте структура Pixel выходит 48 байт вместо 40.

В примере из статьи о памяти поля bool, float64, bool, int32, bool, int64 занимают 40 байт, из них 17 — пустые. От больших к маленьким — 24. Все ответы этой задачи совпадают с тем, что показывает unsafe.Sizeof в настоящем Go; анализатор fieldalignment из golang.org/x/tools ищет именно такие структуры.

3+Решение
4Сложность

O(k log k) на структуру плюс разбор типов: размеры описанных структур запоминаются в словаре.

5Типичные ошибки
  • Сортировать по размеру. Ломается на массивах, у которых размер больше выравнивания.
  • Забыть хвост. Размер структуры округляется до её выравнивания: float32, bool, float32 — это 12 байт, а не 9.
  • Переставлять поля вложенной структуры. Вложенная структура — одно поле со своим размером; переставлять можно только поля текущей.

Алгоритмы задачи

TEC Приём Сколько займёт в памяти Байты на запись — и сразу видно, поместится ли миллиард: из чего складывается вес данных в Python и Go. прикидка — байты на запись × число записей 1 задача PAR Приём Жадные алгоритмы Лучший шаг сейчас без оглядки назад: когда это оптимально, когда почти, и как это доказать. обычно O(n log n): сортировка или куча 2 задачи
Каталог алгоритмов