3

Requirement

I would like to define a defaultdict that returns the value of the largest key, if the key that I am providing is not in the dictionary. Basically I am looking for a way to store config information with the twist, that values default to their last defined values.

Solution so far

My implementation is as follows:

from collections import defaultdict

d = defaultdict(lambda: d[max(d.keys())])
d.update({2010: 10, 2011: 20, 2013: 30 })

for year in [2010, 2011, 2013, 2014]:
    print(f"{year}: {d[year]}")

which correctly produces:

2010: 10
2011: 20
2013: 30
2014: 30

(a more elaborate version could also return values for keys smaller than the smallest).

Question

Is there a more elegant way to define the lambda function without the requirement that you know the dictionary's name?

divingTobi
  • 2,044
  • 10
  • 25
  • 1
    Searching for the largest key every time is going to get really slow when there are a lot of keys. This doesn't sound like a job for a defaultdict. – user2357112 Sep 03 '21 at 09:13
  • Also, remember that defaultdicts *insert* the default value when you look up a missing key. That doesn't sound like the behavior you need here. – user2357112 Sep 03 '21 at 09:14

2 Answers2

2

Calculating frequently the max key looks quite inefficient because in Python keys are in hash maps so they aren't sorted.

Consider writing your own default_dict:

class DictLast(collections.MutableMapping,dict):
    def __init__(self, *args, **kwargs):
        self.theMaxKey = None 
        self.update(*args, **kwargs)
    def __getitem__(self, key):
        if dict.__contains__(self,key): 
            return dict.__getitem__(self,key)
        return dict.__getitem__(self, self.theMaxKey)
    def __setitem__(self, key, value):
        if self.theMaxKey is None:
            self.theMaxKey = key
        if key > self.theMaxKey: 
            self.theMaxKey = key
        dict.__setitem__(self,key,value)   

d = DictLast()
d.update({2010: 10, 2011: 20, 2013: 30 })

for year in [2010, 2011, 2013, 2014]:
    print(f"{year}: {d[year]}")

please notice that, whenever asked for a missing key, my implementation doesn't add the key to the dictionary. I assume this is the intended behavior

If you are in doubt, try this code with my and your implementation:

for year in [2010, 2011, 2013, 2015]:
    print(f"{year}: {d[year]}")
d[2014]=7
for year in [2010, 2011, 2013, 2015]:
    print(f"{year}: {d[year]}")

to understand what's the difference

EDIT: As pointed out in the comments below:

"this strategy only works if you don't remove items from the dictionary".

IMO If you want the data structure to be well designed you should manage removal too (up to you to decide if you want to raise, recalculate the max or do something different).

jimifiki
  • 5,377
  • 2
  • 34
  • 60
  • 2
    Beware that this strategy only works if you don't remove items from the dictionary. – kaya3 Sep 03 '21 at 10:01
  • @kaya3 you're right! An edit is in order. Either raise if the dict is not intended to be used for remove; recalculate maxkey if removing is not frequent; rethink the data structure otherwise. Thx – jimifiki Sep 03 '21 at 10:05
  • Why do you need a `MutableMapping` here at all? `dict` already [is one](https://docs.python.org/3/glossary.html#term-mapping). Note that for python3.9, you need to write `collections.abc.MutableMapping` to avoid a deprecation warning. – normanius Sep 03 '21 at 10:06
  • If the main reason for re-inheriting from `MutableMapping` was that `__setitem__()` is also called for `dict.update()`, then I'm not sure if this is the right way to go. (The inheritance order matters in your class definition, try it out.) – normanius Sep 03 '21 at 10:10
  • @normanius Yes, the reason was to enforce that. I tried both and by testing them, I think the one I put in my answer is the working one. That said, I could be wrong – jimifiki Sep 03 '21 at 10:15
  • 1
    @jimifiki Modifying a built-in python class is always tricky... See [this related post](https://stackoverflow.com/questions/2060972). I think you would have to override more dict methods (such as `__delitem__`, `update` and `setdefault`) for your approach to work properly. – normanius Sep 03 '21 at 10:41
  • @normanius thanks for the precious link. I am tempted to edit my class so to manage the `__delitem __` but this can be done only once one knows the use cases of this specific class. The class passes the small test suite here: [accepted answer](https://stackoverflow.com/a/2588648/512225) as soon as possible I'll check it really works as intended – jimifiki Sep 03 '21 at 11:44
  • Thanks a lot for the above piece of code and the discussion in the comments. Any idea why the content of the dictionary is not displayed in ipython? I only get `In [100]: d, Out [100]: {}`, i.e. an empty dictionary. Only `print(d)` shows the content. Adding a `__str__`-method does not seem to help either. – divingTobi Sep 03 '21 at 13:42
1

Not sure if you need to use a defaultdict here. The main use of a defaultdict is to insert and set a default value if a requested key is not found. In the original question, however, this feature seems not to be required.

Instead, I'd simply go with a customized dictionary:

class CustomDict(dict):
    def __getitem__(self, key):
        if key not in self.keys():
            key = max(self.keys())
        return super().__getitem__(key)

If you really need a defaultdict for some reason, you could proceed similarly and derive from defaultdict.

normanius
  • 8,629
  • 7
  • 53
  • 83