Что проверяет задание
Нужно оценить объём памяти для хранения паролей, идентификаторов, базы пользователей или сообщения фиксированной структуры. Обычно кодирование символов равномерное.
Встречаются прямые задачи (дано всё, найти объём) и обратные: по объёму найти размер дополнительных сведений, число пользователей, мощность алфавита или длину идентификатора.
Определения
Идентификатор, слово из символов заданного алфавита фиксированной или ограниченной длины: логин, пароль, код.
Мощность алфавита, сколько различных символов разрешено. От неё зависит минимальное число бит на символ.
Длина кода символа, при равномерном кодировании это наименьшее целое число бит, не меньшее log₂ от мощности алфавита. Память обычно выделяют целыми байтами, поэтому длину часто округляют вверх до кратного 8.
Запись базы, один пользователь или один объект: идентификатор плюс дополнительные поля фиксированного размера.
Служебные данные, поля, которые не являются самим паролем, но занимают место: дата, номер, контрольная сумма, выравнивание.
Выравнивание, округление размера записи до целого числа байт, слов или блоков. Даже если информация занимает 9 бит, хранить могут 2 байта.
Информационный объём базы, произведение числа записей на размер одной записи после всех округлений.
Мощность алфавита из условия
Мощность складывают из всех частей алфавита, которые перечислены в условии:
- десятичные цифры: 10 символов;
- цифры шестнадцатеричной (семнадцатеричной) системы: 16 (17) символов;
- латинские буквы одного регистра: 26, прописные и строчные вместе: 52;
- «N-символьный набор» или «N-символьный алфавит»: N символов;
- перечисленные через запятую символы считают по одному.
Если сказано «буквы используются в двух начертаниях: строчные и прописные», каждую букву считают дважды. Если в условии уже написано «всего используется N символов» или «таким образом, используется N-символьный алфавит», берут это N.
Требования вида «пароль должен содержать хотя бы одну цифру» не меняют алфавит: все перечисленные символы разрешены в любой позиции.
Бит на один символ
При равномерном кодировании каждому символу дают одинаковое число бит i. Кодов длины i ровно 2^i, поэтому нужно наименьшее i, для которого 2^i не меньше мощности алфавита N:
- 2 символа: 1 бит, до 4 символов: 2 бита, до 8: 3 бита, до 16: 4 бита;
- до 32: 5 бит, до 64: 6 бит, до 128: 7 бит, до 256: 8 бит;
- до 512: 9 бит, до 1024: 10 бит, до 2048: 11 бит, до 4096: 12 бит.
Например, для 36 символов: 2^5 = 32 мало, 2^6 = 64 хватает, значит i = 6.
N = 36
i = 0
while 2 ** i < N: # подбираем наименьшую степень двойки, которая вмещает алфавит
i += 1
print(i) # 6
Два разных округления
Сначала округляют код одного символа до целого числа бит. Затем часто округляют весь идентификатор до целого числа байт. Эти два шага нельзя сливать в один: лишние биты на символ и лишние биты в конце записи, разные добавки.
Например, пароль из 7 символов по 6 бит занимает 42 бита. 42 / 8 = 5,25, поэтому под пароль отводят 6 байт (48 бит), а не 5,25 байта.
from math import ceil
i, length = 6, 7
bits = i * length # 42 бита на пароль
bytes_ = ceil(bits / 8) # 6 байт: целое число байт, округляем вверх
print(bits, bytes_)
Если сказано «каждый символ кодируется … битами», длину кода уже дали, и log₂ считать не нужно.
Дополнительные сведения о пользователе
Кроме пароля в записи о пользователе часто хранят дополнительные сведения фиксированного размера: E байт на каждого. Тогда одна запись занимает
размер записи = байты пароля + E.
Если известен общий объём V для K пользователей, а E неизвестно, сначала находят размер записи V / K, а затем вычитают байты пароля:
E = V / K − байты пароля.
password_bytes = 6
users, total = 20, 500
record = total // users # 25 байт на одного пользователя
extra = record - password_bytes # 19 байт дополнительных сведений
print(extra)
Единицы измерения
В задании 11 приставки двоичные:
- 1 байт = 8 бит;
- 1 Кбайт = 1024 байт = 2^10 байт;
- 1 Мбайт = 1024 Кбайт = 2^20 байт;
- 1 Гбайт = 1024 Мбайт = 2^30 байт.
Если ответ просят в Кбайт целым числом, а объём не делится на 1024 нацело, берут наименьшее целое число Кбайт, которого хватит: округляют вверх.
from math import ceil
total_bytes = 3200 * 33
print(ceil(total_bytes / 1024)) # Кбайт с округлением вверх
Обратная задача: мощность алфавита или длина
Иногда известен только предел памяти: «отведено не более V», «требуется более V». Тогда перебирают число бит на символ (или длину) и проверяют условие на объём.
- Наибольшая мощность алфавита: находим наибольшее i, при котором объём ещё укладывается в предел. Алфавит может содержать до 2^i символов.
- Наименьшая мощность: находим наименьшее i, при котором объём уже превышает предел. Чтобы понадобилось i бит, символов должно быть больше 2^(i−1), то есть не меньше 2^(i−1) + 1.
- Наибольшая или наименьшая длина: так же перебирают длину при известном числе бит на символ.
from math import ceil
count, limit = 12450, 955 * 1024 # 12 450 номеров, не более 955 Кбайт
length = 157
best = 0
for i in range(1, 65):
record = ceil(length * i / 8) # байт на один номер
if count * record <= limit:
best = i # такое число бит ещё помещается
print(2 ** best) # наибольшая мощность алфавита
Сколько записей поместится
Если дан объём памяти и размер одной записи, наибольшее число записей: объём, делённый на размер записи, с округлением вниз. Неполная запись не хранится.
memory = 2 * 1024 # 2 Кбайт
record = 18 # байт на пользователя
print(memory // record) # 113 пользователей
Сообщение без округления до байт
Если коды символов (или измерений) записываются подряд, «одинаковым минимальным количеством бит», без выделения целых байт на каждую запись, объём равен числу символов, умноженному на число бит на символ. В байты переводят только итог.
Так же решают задачи про номера участников и результаты измерений: число возможных значений даёт число бит на одно значение.
Общий алгоритм решения
- Выписать алфавит или его мощность, длину идентификатора и число записей.
- Найти число бит на один символ: по условию или как ⌈log₂ N⌉.
- Найти число бит на идентификатор и округлить так, как предписывает условие (обычно до байта).
- Добавить служебные поля, тоже с их округлением.
- Умножить размер одной записи на количество записей.
- Перевести ответ в те единицы, которые просят: бит, байт, КиБ, МиБ.