expression form of one-to-many dict?

[Nick Craig-Wood]

Steven Bethard <steven.bethard at gmail.com> wrote:
>  map = {}
>  for key, value in sequence:
>       map.setdefault(key, []).append(value)

I was thinking about exactly that the other day, when converting some
perl to python.

[ digression: In perl, you do

  push @{$map->{$key}}, $value

If $map->{$key} doesn't exist is is autovivified into an array (since
its in array context).  Now thats exactly the sort of magic that gives
perl a bad name ;-) ]

However, one thing I noticed is that a list is created and destroyed
as the second parameter to setdefault whether or not it is used in
map, which strikes me as a bit wasteful. You obviously can't use the
same list there either.  If it was an object with a more expensive
constructor then you'd notice it more.

It would be nice if setdefault didn't evaluate the second argument
unless it needed it.  However I guess it would have to be a language
feature to do that.

Here are some timings

$ /usr/lib/python2.3/timeit.py -s 'sequence=zip(range(1000),range(1000))' 'map = {}
for key, value in sequence:
    map.setdefault(key, []).append(value)'
1000 loops, best of 3: 1.42e+03 usec per loop

$ /usr/lib/python2.3/timeit.py -s 'sequence=zip(range(1000),[ i%11 for i in range(1000)])' 'map = {}
for key, value in sequence:
    map.setdefault(key, []).append(value)'
1000 loops, best of 3: 1.57e+03 usec per loop

$ /usr/lib/python2.3/timeit.py -s 'sequence=zip(range(1000),range(1000))' 'map = {}
for key, value in sequence:
    if map.has_key(key):
        map[key].append(value)
    else:
        map[key] = [ value ]'
1000 loops, best of 3: 1.1e+03 usec per loop

$ /usr/lib/python2.3/timeit.py -s 'sequence=zip(range(1000),[ i%11 for i in range(1000)])' 'map = {}
for key, value in sequence:
    if map.has_key(key):
        map[key].append(value)
    else:
        map[key] = [ value ]'
1000 loops, best of 3: 1.11e+03 usec per loop


Not that timing is everything of course ;-)
-- 
Nick Craig-Wood <nick at craig-wood.com> -- http://www.craig-wood.com/nick