Is get lazily evaluated?
Development, Python January 24th, 2009
What do you think about a dict.get operation does?
d.get[the_key, fall_back]
Something like this?
try:
return d[the_key]
except KeyError:
return fall_back
return d[the_key]
except KeyError:
return fall_back
That is my intuition, just like C’s short-circuit evaluation, the fallback is not evaluated until the requested key does not exist. Unfortunately, this not try, for example:
>>> d = {1: 3, 2:4}
>>> def f():
… print 7
…
>>> d.get(3, f())
7
>>> d.get(1, f())
7
3
>>> def f():
… print 7
…
>>> d.get(3, f())
7
>>> d.get(1, f())
7
3
f is always evaluated regardless whether the key exists or not.
This is expected behavior from the compiler/interpreter perspective, the fallback value needs to be reduced first before get is invoked. It would be nice to evaluate get lazily to avoid the expensive try/except mechanism; or tedious has_key test.
You may want to look up the difference between macros and functions (and all the magic that languages from the lisp family do with macros).
I have wanted something like you described more than a few times. If your dict never cannot contain a false value, you can get away with
d.get(key) or f()
In recent python versions there’s also the defauldict class in the collections module.
I usually use the pattern:
if value is None:
value = compute_some_value()
It’s not exactly compact, and assumes that the dict doesn’t contain any None values, but it works for most situations.
Since get() is just an ordinary function, it wouldn’t make sense to lazily evaluate the arguments. C only does short-circuit evaluation for the && and ? syntax, which are both special cases.
You can use defaultdict instead – that will call the function only when the key is missing:
>>> from collections import defaultdict
>>> def f():
… return 7
…
>>> d = defaultdict(f)
>>> d[3]
7
Or you could subclass dict to add your own get method that takes a callable instead of a value.
>>> class mydict(dict):
def get_fn(self, key, f):
if key in self:
return self['key']
return f()
…
>>> d = mydict()
>>> d.get_fn(3, f)
7
I’m sorry, but I think you’re wrong.
if you call d.get(3, f()) you’re NOT passing the function f to the get method!
You are invoking f, then passing the result (None, in this case, as you just print 7) to get!
I think the get implementation it’s really like the
return d[the_key]
except KeyError:
return fall_back
code you wrote, but you can see the “fall_back” is just returned, there isn’t a “return fall_back()” or something like that (and I can’t see a valid reason to do so)
f() is a function call – its evaluated BEFORE the d.get method is called and only return value is passed. It is the case with all function calls.
Yes. Python evaluates all method arguments eagerly.
And this is why I hardly ever use d.get(key, fallback) and never use d.setdefault(key, defaultvalue). I always end up doing:
: if key not in d:
::: d[key] = defaultvalue
: do_something_with( d[key] )
It’s ugly, but I just can’t stomach the overhead since the times when this would be most useful is, e.g. in a loop when I’m building up some kind of dict of keys to lists of values. The first time I see a key, I need to create a list for its value in the dict. But the *normal* case is every other time I see the key, and I don’t want to be pointlessly creating and throwing away empty lists in the normal case. That just seems wasteful.
You can fake your way around python’s default of eager evaluation by making use of a higher order function:
: def set_default( dictionary, key, default_value_thunk):
::: if key not in dictionary:
::::: dictionary[key] = default_value_thunk()
::: return dictionary[key]
which you can call like this:
set_default(d, “a”, lambda: list())
or, in this particular case, like this:
set_default(d, “a”, list)
If dict.get() behaved lazily it would be unlike every other Python function — *that* would be very unintuitive to me.
There is also
d[3] if 3 in d else f()
which is not that bad…
dict.get is no special function and as such has no way to ever evaluate anything in a truly lazy fashion. It does not even receive f() on its end, just its actual value. You can easily write a function for your use case, though:
if key in dic: # much faster than try-except
return dic[key]
else:
return default()
lazy_get(d, 3, f) # –> 7
lazy_get(d, 1, f) # –> 3
…but it’s a function call
You don’t understand how the language works in general
When you write f() you are evaluating the f function right there and you will pass the value of it into the get function. This has nothing to do with the get function, you cannot write a function at all where
writing f() in the parameter list would postpone executing f().
Your analogy is incorrect too.
What you need to do is write a function that allows you to pass other functions into it, not default values.
I don’t think that try/except is as expensive as you think. Some testing in ipython with timeit confirms it:
In [2]: d = {’a':1}
In [3]: timeit d.get(’a')
1000000 loops, best of 3: 353 ns per loop
In [4]: timeit “try: d['a']\nexcept: 1″
10000000 loops, best of 3: 42.3 ns per loop
In [5]: timeit d.get(’b', 1)
1000000 loops, best of 3: 377 ns per loop
In [6]: timeit “try: d['b']\nexcept: 1″
10000000 loops, best of 3: 42.5 ns per loop
So .get(key, fallback) is more expensive in both cases – where a value for the key exists and where the fallback is used.
In your example, wouldn’t passing in f() call the function immediately? I was under the impression the () effectively calls the function in place.
It is an interesting idea though to create a dict type that does lazy evaluation on the get function. You could make the fallbacks pretty complex if there was an option to take a callable.
Thanks for all the comments first.
I think Robert Lehmann’s proposal is exactly I try to approach.
And also Christian Wyglendowski’s experiment is quite interesting. At least in C++, try/catch is quite expensive, the compiler needs to generate quite little bit code to guarantee the order of exceptions and that constrains the out-of-order optimization.
And personally, I think the try/except is abused if the condition is not really exceptional.
Just to expand on Robert Lehmann’s example, you can go one step further and define a subclass that allows functions (or any object with a __call__ method really) or values:
… def get(self, key, default_value_or_func):
… if key in self:
… return self[key]
… if hasattr(default_value_or_func, “__call__”):
… return default_value_or_func()
… return default_value_or_func
…
>>> def f():
… print “f was called”
… return 7
…
>>> d = newdict({1:2, 3:4})
>>> d.get(1, f)
2
>>> d.get(42, f)
f was called
7
>>> d.get(”heinz”, 57)
57
>>>
There must be something wrong with Christian’s timing. I’ve seen posts on the internet where the last example has been found to be pretty slow.
I don’t know but I think that you wrong.I am notcompetent in this but I think so.