Сколько стоит номер

"Сколько весит твой файл?", спрашивает один программист у другого. "Файл легкий – 10 кило", слышит он в ответ. Понятно, что речь идет не о килограммах, а о килобайтах. Жаргон – внешний признак профессионализма.

Давайте и мы попытаемся выяснить, сколько весит автомобильный номер и от чего зависит этот "вес". Рассмотрим следующую задачу:

Автомобильный номер состоит из 7 символов. В качестве символов используются 30 букв и 10 цифр. Символ кодируется минимально возможным набором битов. Номер представляется целым числом байтов. Какую память требуется иметь для хранения 1000 номеров.

Решение: Алфавит для записи текстов, представляющих номера автомобилей, содержит 40 символов (30 букв и 10 цифр). Для кодировки такого алфавита потребуются двоичные слова длины 6 (2⁶ > 40 > 2⁵). Для кодировки всего номера потребуется 6*7 = 42 бита. Округляя в большую сторону до целого числа байтов, получим, что для хранения одного номера потребуется 6 байтов. Для хранения 1000 номеров достаточно 6 Кб.

А какая память потребуется для хранения всех возможных номеров? Число номеров – это число всех слов длины 7 в алфавите мощности 40. Число таких слов равно 40⁷ = 4⁷ * 10⁷ = 2¹⁴ * 10⁷. Так как в таких расчетах 2¹⁰ принимается равной 10³, то число номеров примерно равно 16* 10¹⁰. Так как для хранения одного номера требуется 6 байтов, то для хранения всех возможных номеров потребуется примерно 10¹² байтов или 1 терабайт памяти. Сегодня терабайтные внешние диски обыденная вещь. Заметьте, что номеров в таком алфавите более 160 миллиардов, что более чем на порядок превосходит число жителей на Земле.

Рассмотрим еще одну задачу на тему автомобильного номера:

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

Решение: В новых номерах символы принадлежат смешанному алфавиту – нечетные номера в алфавите согласных букв, четные – гласных. Тем не менее, подсчитать число новых номеров в одном регионе нетрудно. Оно равно 20³ * 7², что примерно равно 8 * 10³ * 50 = 4 *10⁵. Поскольку число старых номеров в одном регионе было равно 10⁵, то с появлением новых номеров их число увеличилось примерно в 5 раз.

Зададимся теперь вопросом, а сколько памяти потребуется для хранения новых номеров, если считать, что для хранения каждого символа, выделяется минимально возможное число битов, а для хранения одного номера отводится целое число байтов. Нечетные символы записаны в алфавите из 20 букв. Для хранения такого символа потребуется 5 битов ( 2⁴ < 20 < 2⁵). Таких символов три, так что понадобится 15 битов. Для хранения четного символа достаточно 3-х битов. Таких символов 2, так что для хранения 5 символов понадобится 21 бит. Не будем забывать, что хранить нужно еще и номер региона. Номер региона задается двузначным числом, его значения от 00 до 99. Для хранения чисел из такого диапазона достаточно 7 битов. Общая длина номера составляет 28 битов. Округляя до целого числа байтов, получаем, что для хранения нового номера требуется 4 байта. Заметьте, для хранения старого номера было достаточно 3-х байтов

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

4* 100 * 4 * 10⁵ + 3 * 100 * 10⁵, примерно 2* 10⁸ байтов, примерно 200 мегабайтов.

Если хранить номера только одного региона, то номер региона сохранять не нужно. В этом случае для хранения нового номера, также как и для хранения старого номера с учетом округления требуется 3 байта. Требуемая память в этом случае равна 3 * 5 * 10⁵, что примерно равно 1, 6 Мб.

Рассмотрим еще одну задачу про нумерацию, но не связанную с автомобилями.

На областной олимпиаде по информатике каждая присланная по сети задача получает индивидуальный номер. Номер состоит из нескольких полей: номер района области (в области 15 районов), номер школы в районе ( в каждом районе не более 120 школ), номер ученика данной школы (от каждой школы участвует не более 3-х учеников) и номер задачи (на олимпиаде ученикам предложено 5 задач). Кодировка каждого поля выполняется эффективно - минимально возможным числом битов. Для хранения одного номера отводится целое число байтов. Сколько памяти понадобится для хранения номеров всех участников, при условии, что каждый может прислать решение всех 5-и задач, а в олимпиаде принимает участие 80 человек.

Решение:

Для поля района потребуется 4 бита, школы – 7 битов, номера школьника – 2 бита, задачи – 3 бита, итого – 16 битов или 2 байта. Для хранения всех номеров потребуется 2 * 5 * 80 байтов = 0,8 Кб.

Подведем итоги. Во многих задачах приходится кодировать некоторый характерный признак – номер, метку. Этот признак может быть составным, и отдельные его символы могут принадлежать разным алфавитам. Числовые поля признака могут принадлежать некоторому фиксированному интервалу. При хранении такого признака в памяти компьютера разумно каждое поле кодировать двоичным словом минимального размера, достаточного для хранения всех возможных значений этого поля. Вычислив размер необходимый для хранения каждого поля, можно ответить на вопрос "Сколько весит номер?". Как правило, на этом этапе происходит округление до целого числа байтов. Зная вес одного номера, нетрудно подсчитать, сколько памяти необходимо для хранения N номеров. Примеров я привел предостаточно.

Задачи:

Задачи 1- 4

Сколько весит "признак" (автомобильный номер, участника олимпиад, адрес, регистрационные данные)

Задачи 5-8

Сколько памяти необходимо для хранения признаков.

Задачи 9-10

Во сколько раз увеличится число экземпляров при переходе к расширенному алфавиту