I was trying to implement a data structure that returns a value such that set (key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp. I tried to use a heapq in Python. It raised an exception that I don't understand.
class TimeMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.mapping = collections.defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.mapping[key].append([-timestamp, value])
def get(self, key: str, timestamp: int) -> str :
if not self.mapping[key]:
return ''
heap = heapq.heapify(self.mapping[key])
for pre_stamp, val in heapq.heappop(heap):
if -pre_stamp <= timestamp:
return val
return ''
The exception was: heap argument must be a list.
But it looks the mapping[key] returned value is a list.
The fact that self.mapping
is defined as collections.defaultdict(list)
does not mean that self.mapping[key]
will return a list for every arbitrary key
. It just means that self.mapping[key]
will return a list for every key
that does not exist will return an empty list.
import collections
d = collections.defaultdict(list)
d['a'] = 'not a list'
print(type(d['a']), d['a'])
outputs
<class 'str'> not a list