tgoop.com/python_job_interview/1089
Last Update:
Реализуйте класс SmartCache, который работает следующим образом:
- Метод put(key: str, value: Any):
- Сохраняет значение по ключу.
- Если суммарный объем памяти, занимаемый всеми элементами, превышает лимит (например, 10 MB), автоматически удаляются наименее "ценные" элементы.
- Метод get(key: str) -> Any:
- Возвращает значение по ключу.
- Увеличивает счётчик использования элемента.
- Если элемент отсутствует — возвращает None.
Что значит "ценность" элемента:
- Ценность = количество обращений (`hit count`) к элементу.
- При очистке кэша сначала удаляются элементы с наименьшим количеством обращений.
Ограничения:
- Класс должен корректно считать объём памяти, занимаемый элементами.
- Нужно учитывать, что элементы могут быть сложными структурами (`dict`, list, вложенные объекты).
- Решение должно быть эффективным: операции должны быть быстрыми даже при большом количестве элементов.
---
▪️ Подсказки:
- Для оценки размера объектов можно использовать модуль sys.getsizeof, но для сложных вложенных структур нужен рекурсивный подсчет.
- Для хранения частоты обращений стоит использовать дополнительную структуру данных (`collections.Counter` или `dict`).
- При очистке лучше сначала группировать элементы по "ценности", а затем удалять самые "дешевые".
---
▪️ Что оценивается:
- Умение работать с ограничениями по памяти.
- Аккуратная обработка ссылок и размеров объектов.
- Эффективность очистки кэша.
- Чистота и читаемость кода.
---
▪️ Разбор возможного решения:
Идея архитектуры:
- Храним:
- storage: словарь {key: value}.
- hits: счётчик {key: hit_count}.
- size: общий размер всех объектов.
- При put():
- Добавляем элемент.
- Пересчитываем суммарный размер.
- Если размер превышает лимит:
- Удаляем наименее популярные элементы до тех пор, пока не уложимся в лимит.
- При get():
- Увеличиваем hit_count элемента.
- Возвращаем значение или None.
Оценка размера объектов:
- Простого sys.getsizeof недостаточно для коллекций.
- Нужна функция, рекурсивно подсчитывающая размер всех вложенных объектов.
Мини-пример функции подсчета размера:
import sys
def deep_getsizeof(obj, seen=None):
"""Рекурсивно считает память объекта и его вложенных объектов"""
size = sys.getsizeof(obj)
if seen is None:
seen = set()
obj_id = id(obj)
if obj_id in seen:
return 0
seen.add(obj_id)
if isinstance(obj, dict):
size += sum([deep_getsizeof(v, seen) + deep_getsizeof(k, seen) for k, v in obj.items()])
elif isinstance(obj, (list, tuple, set, frozenset)):
size += sum(deep_getsizeof(i, seen) for i in obj)
return size
Мини-пример интерфейса `SmartCache`:
class SmartCache:
def __init__(self, max_size_bytes):
self.max_size = max_size_bytes
self.storage = {}
self.hits = {}
self.total_size = 0
def put(self, key, value):
# добавить логику добавления и очистки при переполнении
pass
def get(self, key):
# увеличить hit_count и вернуть значение
pass
🔖 Дополнительные вопросы:
- Как ускорить очистку кэша без полного перебора всех элементов?
- Как сделать потокобезопасную версию кэша?
- Как адаптировать
SmartCache для распределённой архитектуры (кэш между несколькими машинами)?@python_job_interview