В задании 11 мы работаем с текстовыми данными: паролями, идентификаторами и серийными номерами. В первой статье мы учились находить длину такой записи, а теперь длина уже известна — нужно определить, сколько памяти занимают одна запись и вся база данных.
Чтобы не потеряться в вычислениях, каждый раз идём по одной цепочке: сначала находим мощность алфавита, затем число бит на один символ, после этого переводим размер записи в целое число байт и только в конце умножаем на количество объектов.
В статье разберём три варианта: подробное решение вручную, запись тех же формул в Python и пример, где к паролю добавляются отдельные сведения о пользователе.
Тип 2. Объём памяти
В этом типе требуется найти общий объём памяти для заданного числа паролей, идентификаторов или серийных номеров. Все записи имеют одинаковую длину и хранятся в одинаковом, минимально возможном целом числе байт.
Объём памяти
Обозначим через N мощность алфавита, через L длину одной записи в символах, а через K количество записей. Число бит на символ обозначим i. Если в условии есть дополнительные данные пользователя, их размер будем обозначать extra и прибавлять к размеру записи до умножения на K.
Сначала подбираем минимальное число бит i, при котором выполняется неравенство 2ⁱ ≥ N. Затем умножаем длину записи L на i и делим результат на 8. Если получилось дробное число байт, округляем его вверх, потому что для каждой записи выделяется целое число байт. Так получаем размер одной записи B. Общий объём равен I = K · B. Округлять нужно именно размер одной записи, а не сумму дробных размеров всей базы.
Алгоритм решения
Действовать будем по такому алгоритму:
1. Складываем все символы, которые могут встретиться в записи, и получаем N.
2. Подбираем минимальное i, для которого 2ⁱ ≥ N. Это число бит, необходимое для хранения одного символа.
3. Умножаем длину записи L на i и делим результат на 8. Если получилось дробное число байт, округляем его вверх: запись должна занимать целое число байт.
4. Если в записи есть дополнительные сведения, добавляем их размер к размеру одной записи (B).
5. Умножаем размер одной записи на количество объектов K. В конце переводим байты в Кбайты или Мбайты, если этого требует условие.
Пример 1. Ручное решение
Начнём разбор с такого задания:
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 317 символов и содержащий только десятичные цифры и символы из 4090-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Мбайт), необходимый для хранения 262 144 идентификаторов.
В ответе запишите только целое число – количество Мбайт.
Решаем последовательно, не перескакивая через округления.
1. В алфавите 10 цифр и 4090 специальных символов: N = 10 + 4090 = 4100.
2. Сравниваем N со степенями двойки: 2¹² = 4096 < 4100, поэтому двенадцати бит недостаточно. Следующая степень двойки — 2¹³, значит, на один символ потребуется 13 бит.
3. В одном идентификаторе 317 символов. В битах это 317 · 13 = 4121 бит, или 4121 / 8 = 515,125 байта. Запись должна занимать целое число байт, поэтому округляем вверх: B = 516 байт.
4. Для 262 144 идентификаторов получаем 516 · 262 144 = 135 266 304 байта. В одном Мбайте 2²⁰ байт, поэтому 135 266 304 / 2²⁰ = 129 Мбайт.
В итоге получаем ответ на это задание: 129.
Пример 2. Решение по формулам в Python
Теперь те же действия поручим Python. Важно сохранить порядок вычислений: сначала округлить размер пароля, затем добавить служебные данные и только после этого умножить на количество пользователей.
При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 7 символов и содержащий только символы 26-символьного набора строчных латинских букв и десяти арабских цифр. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно пароля, для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 9 байт на одного пользователя.
Определите объём памяти (в байтах), необходимый для хранения сведений о 30 пользователях.
В ответе запишите только целое число – количество байт.
Импортируем нужные функции из модуля math и выписываем имеющиеся данные:
from math import ceil, log2
length = 7
alphabet = 26 + 10
extra = 9
users = 30
Вычисляем, сколько бит нужно на один символ:
bits = ceil(log2(alphabet))
Теперь определим, сколько байт нужно для хранения пароля:
password_bytes = ceil(length * bits / 8)
По условию к паролю добавляются 9 байт дополнительных сведений. Учтём их:
bytes_per_user = password_bytes + extra
Всё, осталось лишь найти объем памяти для 30 пользователей:
total_bytes = bytes_per_user * users
Допишем вывод значения на экран и получим такую программу:
from math import ceil, log2
length = 7
alphabet = 26 + 10
extra = 9
users = 30
bits = ceil(log2(alphabet))
password_bytes = ceil(length * bits / 8)
bytes_per_user = password_bytes + extra
total_bytes = bytes_per_user * users
print(total_bytes)
Запустим её и получим число 450, которое и запишем в ответ.
Пример 3
Для закрепления решим еще одно задание тем же способом. Перебором в цикле решать задания второго типа не будем.
На очереди такое задание:
При регистрации в компьютерной системе каждому объекту присваивается идентификатор, состоящий из 5 символов и содержащий только десятичные цифры и символы из 7084-символьного специального алфавита. В базе данных для хранения каждого идентификатора отведено одинаковое и минимально возможное целое число байт. При этом используется посимвольное кодирование идентификаторов, все символы кодируются одинаковым и минимально возможным количеством бит.
Определите объём памяти (в Кбайт), необходимый для хранения 22 528 идентификаторов.
В ответе запишите только целое число – количество Кбайт.
В данном случае один идентификатор занимает 9 байт, а общий объём равен 198 Кбайт. Число 198 и будет ответом.
Итоги
В задачах на объём памяти мы движемся от алфавита к общей базе: N → i → B → I. Сначала определяем число бит на символ, затем округляем размер одной записи вверх до целого байта, добавляем дополнительные данные и только после этого умножаем результат на количество объектов.
Можно вывести такой шаблонный код:
from math import ceil, log2
length = *1
alphabet = *2
extra = *3
objects = *4
bits = ceil(log2(alphabet))
bytes_per_object = ceil(length * bits / 8) + extra
total_bytes = bytes_per_object * objects
print(*5)
Здесь:
*1 — длина записи,
*2 — мощность алфавита,
*3 — дополнительные байты на объект,
*4 — число объектов.
Вместо *5 выведите total_bytes или переведите его в нужные единицы.
Всегда обращайте внимание на единицы измерения: 1 Кбайт = 2¹⁰ байт, 1 Мбайт = 2²⁰ байт. Не округляйте общий объём вместо каждой записи и не прибавляйте служебные данные после умножения — они относятся к каждому пользователю.
В следующей статье разберём обратную задачу: по ограничению памяти найдём мощность алфавита.
Разберём эту тему на бесплатном пробном занятии
Преподаватель покажет, как решать такие задачи, и подскажет, с чего начать подготовку. Группы до 8 человек, очно в Калининграде и онлайн.
Мы используем файлы cookie. Необходимые обеспечивают работу сайта: корзину и вход в личный кабинет. С вашего согласия мы также используем сервис Яндекс Метрика, чтобы анализировать посещаемость и улучшать сайт.
Подробнее — в политике конфиденциальности.
