Just a suggestion to make ChainMap.get and possibly contains a bit faster.
get3 is fairly DRY I suppose. Also, same approach, I believe could be used for __contains__, then get could be left as it is and __contains__ replaced with __contains2__ in my example. This is probably the most DRY, but performance suffers a bit from multiple method invocation.
I, myself, am going with get2 in my subclasses, and replacing __contains__ with __contains2__ for best performance.
import collections as coll
class Cm(coll.ChainMap):
def get2(self, key, default=None):
for mapping in self.maps:
try:
return mapping[key]
except KeyError:
return default
def get3(self, key, default=None):
try:
return self[key]
except KeyError:
return default
def __contains2__(self, key):
try:
self[key]
return True
except KeyError:
return False
def get4(self, key, default=None):
return self[key] if self.__contains2__(key) else default
maps = [dict(a=1), dict(a=2), dict(a=3)]
cm = Cm(*maps)
In [17]: %timeit cm['a']
115 ns ± 0.602 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
In [18]: %timeit cm.get('a')
790 ns ± 10.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
In [19]: %timeit cm.get2('a')
127 ns ± 0.478 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
In [20]: %timeit cm.get3('a')
156 ns ± 0.366 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
In [20]: %timeit cm.get4('a')
334 ns ± 8.03 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
This doesn’t work because of __missing__. This would break with e.g. a defaultdict and insert new keys, which is not what you want with get and __contains__. It would also break in a subclass that redefines __missing__ to return a value.
Also whether or not this is faster will depend on the implementation of the mappings that have been passed in, maybe someone is using a custom mapping with a cheap containment check, but where retrieving the actual value is expensive, optimizing for dict might be fine if you only ever use dict, but that’s a specialized use-case and that should require a specialized class, which doesn’t fit into the stdlib.
That is a sensible optimization yes, it avoids iterating over all the mappings twice, when you technically already knew in which mapping the key was in, in the first iteration.
Irrelevant ramblings
, although this would still change the behavior, because right now it would actually return ChainMap._missing(key) before returning default. This is kind of inconsistent with how it works in defaultdict and dict, so you could consider it a bug and report it as such in the CPython repository, but just something to keep in mind. Nevermind I misread the implementation, __mising__ can’t get called because __getitem__ is only called when the key is present
That being said your benchmarks are fairly incomplete, because they only test the case where the key is present in the first mapping, you would need to cover more cases to make a really compelling case.
import collections as coll
class Cm2(coll.ChainMap):
def __contains__(self, key):
for mapping in self.maps:
if key in mapping:
return True
return False
class Cm3(Cm2):
def get(self, key, default=None):
for mapping in self.maps:
if key in mapping:
return mapping[key]
return default
maps = [dict(a=1), dict(a=2, b=2), dict(a=3, b=2, c=3)]
cm = coll.ChainMap(*maps)
cm2 = Cm2(*maps)
cm3 = Cm3(*maps)
%timeit 'a' in cm # 615 ns
%timeit 'c' in cm # 752 ns
%timeit cm.get('a') # 776 ns
%timeit cm.get('b') # 1.15 µs
%timeit cm.get('c') # 1.46 µs
%timeit 'a' in cm2 # 140 ns
%timeit 'c' in cm2 # 218 ns
%timeit cm2.get('a') # 297 ns
%timeit cm2.get('b') # 633 ns
%timeit cm2.get('c') # 945 ns
%timeit cm3.get('a') # 149 ns
%timeit cm3.get('b') # 179 ns
%timeit cm3.get('c') # 221 ns
Just replacing __contains__ already makes get faster. However, there is still overhead, because it iterates once in __contains__ and again in __getitem__.
IMO, replacing both __contains__ and get might be best. Although, there is no re-usage of methods in each other, it has no unnecessary repetitions.
Maybe it could be done via helper method, which say returns a tuple(mapping, value), if key is contained, otherwise False, then use it in both get and __contains__ (maybe even in __getitem__), but that IMO would be too much unnecessary complexity, when a fairly simple straightforward and faster solution exists.
class Cm(coll.ChainMap):
def _search(self, key):
for mapping in self.maps:
if key in mapping:
return mapping
def __contains__(self, key):
return self._search(key) is not None
def get(self, key, default=None):
if (m := self._search(key)) is not None:
return m[key]
return default
maps = [dict(a=1), dict(a=2, b=2), dict(a=3, b=2, c=3)]
cm = Cm(*maps)
%timeit 'a' in cm # 198 ns
%timeit 'c' in cm # 274 ns
%timeit cm.get('a') # 210 ns
%timeit cm.get('b') # 243 ns
%timeit cm.get('c') # 284 ns
Extra method, which is used in both methods. Also, it could be useful for other matters. However, performance suffers a bit, of which major part is one extra function call.
Get can remain one-liner as it is now
def get(self, key, default=None):
return default if (m := self._search(key)) is None else m[key]
Does anyone know why was decision made for children of ChainMap to be on the left of maps list?
I find it very unintuitive. Finally got used to it from users perspective, but now as I started implementing similar classes, I am unsure what convention to go with.
Would be nice to keep ChainMap’s convention, but in that case would be good to know the why.
I think it makes sense if you use it to model things like variable scopes. You would start with a map for the current scope and each time you descend into a function or something else that has its own scope you would add a child scope, the child scope should then take precedence over the parent scope when looking up names.
I agree that with the mental model of a stack it would make more sense if the children were appended to the list, but it doesn’t really matter which direction you choose as long as you are consistent about it.
I think in this case this just was both the most convenient way to store it to keep the implementation simple[1] and it’s also the most intuitive interpretation if you pass in a list of your own and didn’t know about these two methods.
i.e. you don’t have a bunch of calls to reversed everywhere ↩︎
