2
\$\begingroup\$

Recently I have been asked to implement a key map with expire time for each key and possibility to limit the number of keys, in Python. I've used a dictionary + heap to store the entries, e.g.:

from datetime import datetime, timedelta
from heapq import heapify, heappop, heappush


class KeyMap:
    def __init__(self, maxsize=None):
        self.maxsize = maxsize
        self.entries = {}
        self.entries_heap = []

    def set(self, key, value, expiration_time: timedelta):
        expires_at = datetime.now() + expiration_time
        entry = {'key': key, 'value': value, 'expires_at': expires_at}
        self.entries[key] = entry
        heappush(self.entries_heap, (expires_at, entry))

        if len(self.entries) > self.maxsize:
            _, oldest = heappop(self.entries_heap)
            del self.entries[oldest['key']]

    def get(self, key):
        entry = self.entries[key]
        if entry['expires_at'] < datetime.now():
            del self.entries[key]
            raise KeyError(key)
        return entry[value]

    def delete(self, key):
        del self.entries[key]
        for i in range(len(self.entries)):
            if self.entries_heap[i][1]['key'] == key:
                self.entries_heap[i] = self.entries_heap[-1]
                self.entries_heap.pop()
        heapify(self.entries_heap)

AFAIC, this should give O(log n) time for set(), O(1) for get() and O(n) for delete(). Are there any ways to improve the performance of set() and delete() methods?

\$\endgroup\$
  • \$\begingroup\$ If it were possible to implement set in \$O(1)\$ then you could use this data structure to sort a list of numbers in \$O(n)\$ (by turning the numbers into datetime objects and using them as expiration times and then looking at the order they get evicted from the cache). But sorting a list of numbers takes \$Ω(n\log n)\$. \$\endgroup\$ – Gareth Rees Dec 8 '18 at 18:07
  • \$\begingroup\$ Actually, sorting numbers can be done in O(n) time, check this, for example :) \$\endgroup\$ – Eugene Yarmash Dec 10 '18 at 8:41
  • \$\begingroup\$ I was afraid someone would offer that nitpick. But if you know all about bucket sort then you know why it's actually \$Ω(n\log n)\$ in the general case. \$\endgroup\$ – Gareth Rees Dec 10 '18 at 8:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.