Как реализовать кеш в Python, который эффективно поддерживает операции как со словарем, так и с кучей?

В Python dict уже упорядочена вставка (в старых версиях используйте collections.OrderedDict), аналогично куче, отсортированной по времени. Это означает, что самый старый вставленный элемент всегда находится впереди. Вместо обновления значений удалите и вставьте элемент, чтобы принудительно переместить обновленные элементы назад.

Чтобы использовать dict в качестве временного кеша, используйте следующий подход. Вы можете выделить его в отдельный подкласс, предоставить вспомогательные функции или добавить встроенный код. Подкласс удобнее и позволяет избежать неправильного использования, но включает в себя множество специальных методов, поэтому я покажу более простые вспомогательные функции и предположу, что время жизни (ttl) задано.

• Предметы должны быть формы "key": (time, value). Выгодно иметь неизменяемые значения (т. е. tuple или NamedTuple), чтобы предотвратить аннулирование ограничения действительного time.
• При вставке удалите все предыдущие элементы того же ключа. Это заставляет элемент быть вставлен в последнюю позицию.

  def set(cache, key, value):
       cache.pop(key, None)  # clear the previous position if any
       cache[key] = (time.monotonic(), value))
  

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

  def get(cache, key):
       key_time, value = cache[key]
       if key_time < time.monotonic() + ttl:  # check timestamp validity
           del cache[key]
           raise KeyError(key)
       return value
  

• Чтобы удалить самый старый элемент, просто возьмите первый ключ и удалите его.

  def free(cache):
       if cache:
          oldest_key = next(iter(cache))
          del cache[oldest_key]
  

• Чтобы удалить все устаревшие элементы, просто выполните итерацию до тех пор, пока не будет найден первый ключ, который все еще действителен.

  def clean(cache):
       outdated, deadline = [], time.monotonic() + ttl
       for key, (key_time, _) in cache.items():
           if key_time < deadline:
               outdated.append(key)
           else:  # all following keys are valid as well
               break
       for key in outdated:
           del cache[key]