Pre-PEP: Dictionary accumulator methods

[Raymond Hettinger]

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

def appendlist(self, key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

The rationale is to replace the awkward and slow existing idioms for dictionary
based accumulation:

d[key] = d.get(key, 0) + qty
d.setdefault(key, []).extend(values)

In simplest form, those two statements would now be coded more readably as:

d.count(key)
d.appendlist(key, value)

In their multi-value forms, they would now be coded as:

d.count(key, qty)
d.appendlist(key, *values)

The error messages returned by the new methods are the same as those returned by
the existing idioms.

The get() method would continue to exist because it is useful for applications
other than accumulation.

The setdefault() method would continue to exist but would likely not make it
into Py3.0.


PROBLEMS BEING SOLVED
---------------------

The readability issues with the existing constructs are:

* They are awkward to teach, create, read, and review.
* Their wording tends to hide the real meaning (accumulation).
* The meaning of setdefault() 's method name is not self-evident.

The performance issues with the existing constructs are:

* They translate into many opcodes which slows them considerably.
* The get() idiom requires two dictionary lookups of the same key.
* The setdefault() idiom instantiates a new, empty list prior to every call.
* That new list is often not needed and is immediately discarded.
* The setdefault() idiom requires an attribute lookup for extend/append.
* The setdefault() idiom makes two function calls.

The latter issues are evident from a disassembly:

dis(compile('d[key] = d.get(key, 0) + qty', '', 'exec'))

1 0 LOAD_NAME 0 (d)
3 LOAD_ATTR 1 (get)
6 LOAD_NAME 2 (key)
9 LOAD_CONST 0 (0)
12 CALL_FUNCTION 2
15 LOAD_NAME 3 (qty)
18 BINARY_ADD
19 LOAD_NAME 0 (d)
22 LOAD_NAME 2 (key)
25 STORE_SUBSCR
26 LOAD_CONST 1 (None)
29 RETURN_VALUE

dis(compile('d.setdefault(key, []).extend(values)', '', 'exec'))

1 0 LOAD_NAME 0 (d)
3 LOAD_ATTR 1 (setdefault)
6 LOAD_NAME 2 (key)
9 BUILD_LIST 0
12 CALL_FUNCTION 2
15 LOAD_ATTR 3 (extend)
18 LOAD_NAME 4 (values)
21 CALL_FUNCTION 1
24 POP_TOP
25 LOAD_CONST 0 (None)
28 RETURN_VALUE

In contrast, the proposed methods use only a single attribute lookup and
function call, they use only one dictionary lookup, they use very few opcodes,
and they directly access the accumulation functions, PyNumber_Add() or
PyList_Append(). IOW, the performance improvement matches the readability
improvement.


ISSUES
------

The proposed names could possibly be improved (perhaps tally() is more active
and clear than count()).

The appendlist() method is not as versatile as setdefault() which can be used
with other object types (perhaps for creating dictionaries of dictionaries).
However, most uses I've seen are with lists. For other uses, plain Python code
suffices in terms of speed, clarity, and avoiding unnecessary instantiation of
empty containers:

if key not in d:
d.key = {subkey:value}
else:
d[key][subkey] = value



Raymond Hettinger

 

[Ivan Van Laningham]

Hi All--
Maybe I'm not getting it, but I'd think a better name for count would be
add. As in

d.add(key)
d.add(key,-1)
d.add(key,399)
etc.

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

There is no existing add() method for dictionaries. Given the name
change, I'd like to see it.

Metta,
Ivan
----------------------------------------------
Ivan Van Laningham
God N Locomotive Works
http://www.pauahtun.org/
http://www.andi-holmes.com/
Army Signal Corps: Cu Chi, Class of '70
Author: Teach Yourself Python in 24 Hours

 

[Aahz]

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

You mean

def count(self, key, qty=1)

Right?
--
Aahz ([email protected]) <*> http://www.pythoncraft.com/

"The joy of coding Python should be in seeing short, concise, readable
classes that express a lot of action in a small amount of clear code --
not in reams of trivial code that bores the reader to death." --GvR

 

[Mike Rovner]

Hi All--
Maybe I'm not getting it, but I'd think a better name for count would be
add. As in

d.add(key)
d.add(key,-1)
d.add(key,399)
etc.

IMHO inc (for increment) is better.

d.inc(key)

add can be read as add key to d

Mike

 

[Jeff Shannon]

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

I presume that the argument list is a typo, and should actually be

def count(self, key, qty=1): ...

Correct?

Jeff Shannon

 

[Raymond Hettinger]

def count(self, value, qty=1):

[Aahz]

You mean
def count(self, key, qty=1)

Right?

Yes.

Also, there is a typo in the final snippet (pure python version of dictionary of
dictionaries). It should read:

if key not in d:
d[key] = {subkey:value}
else:
d[key][subkey] = value


Raymond

 

[Roose]

I like this, it is short, low impact, and makes things more readable. I
tend to go with just the literal way of doing it instead of using get and
setdefault, which I find awkward.

But alas I had a my short, low impact, useful suggestion and I think it
died. It was for any() and all() for lists. Actually Google just released
their "functional.py" module on code.google.com with the exact same thing.
Except they are missing the identity as a default which is very useful, i.e.
any(lst, f=lambda x: x) instead of any(lst, f).

Maybe you can tack that onto your PEP

That is kind of related, they are accumulators as well. They could probably
be generalized for dictionaries, but I don't know how useful that would be.

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

def appendlist(self, key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

The rationale is to replace the awkward and slow existing idioms for dictionary
based accumulation:

d[key] = d.get(key, 0) + qty
d.setdefault(key, []).extend(values)

In simplest form, those two statements would now be coded more readably as:

d.count(key)
d.appendlist(key, value)

In their multi-value forms, they would now be coded as:

d.count(key, qty)
d.appendlist(key, *values)

The error messages returned by the new methods are the same as those returned by
the existing idioms.

The get() method would continue to exist because it is useful for applications
other than accumulation.

The setdefault() method would continue to exist but would likely not make it
into Py3.0.


PROBLEMS BEING SOLVED
---------------------

The readability issues with the existing constructs are:

* They are awkward to teach, create, read, and review.
* Their wording tends to hide the real meaning (accumulation).
* The meaning of setdefault() 's method name is not self-evident.

The performance issues with the existing constructs are:

* They translate into many opcodes which slows them considerably.
* The get() idiom requires two dictionary lookups of the same key.
* The setdefault() idiom instantiates a new, empty list prior to every call.
* That new list is often not needed and is immediately discarded.
* The setdefault() idiom requires an attribute lookup for extend/append.
* The setdefault() idiom makes two function calls.

The latter issues are evident from a disassembly:

dis(compile('d[key] = d.get(key, 0) + qty', '', 'exec'))

1 0 LOAD_NAME 0 (d)
3 LOAD_ATTR 1 (get)
6 LOAD_NAME 2 (key)
9 LOAD_CONST 0 (0)
12 CALL_FUNCTION 2
15 LOAD_NAME 3 (qty)
18 BINARY_ADD
19 LOAD_NAME 0 (d)
22 LOAD_NAME 2 (key)
25 STORE_SUBSCR
26 LOAD_CONST 1 (None)
29 RETURN_VALUE

dis(compile('d.setdefault(key, []).extend(values)', '', 'exec'))

1 0 LOAD_NAME 0 (d)
3 LOAD_ATTR 1 (setdefault)
6 LOAD_NAME 2 (key)
9 BUILD_LIST 0
12 CALL_FUNCTION 2
15 LOAD_ATTR 3 (extend)
18 LOAD_NAME 4 (values)
21 CALL_FUNCTION 1
24 POP_TOP
25 LOAD_CONST 0 (None)
28 RETURN_VALUE

In contrast, the proposed methods use only a single attribute lookup and
function call, they use only one dictionary lookup, they use very few opcodes,
and they directly access the accumulation functions, PyNumber_Add() or
PyList_Append(). IOW, the performance improvement matches the readability
improvement.


ISSUES
------

The proposed names could possibly be improved (perhaps tally() is more active
and clear than count()).

The appendlist() method is not as versatile as setdefault() which can be used
with other object types (perhaps for creating dictionaries of dictionaries).
However, most uses I've seen are with lists. For other uses, plain Python code
suffices in terms of speed, clarity, and avoiding unnecessary instantiation of
empty containers:

if key not in d:
d.key = {subkey:value}
else:
d[key][subkey] = value



Raymond Hettinger

 

[Bengt Richter]

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

def appendlist(self, key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

The rationale is to replace the awkward and slow existing idioms for dictionary
based accumulation:

d[key] = d.get(key, 0) + qty
d.setdefault(key, []).extend(values)

In simplest form, those two statements would now be coded more readably as:

d.count(key)
d.appendlist(key, value)

In their multi-value forms, they would now be coded as:

d.count(key, qty)
d.appendlist(key, *values)

How about an efficient duck-typing value-incrementer to replace both? E.g. functionally like:
... def valadd(self, key, incr=1):
... try: self[key] = self[key] + type(self[key])(incr)
... except KeyError: self[key] = incr
... Traceback (most recent call last):
File "<stdin>", line 1, in ?

>>> xd.valadd('y', range(3))
>>> xd {'y': [0, 1, 2], 'x': 1}
>>> xd.valadd('z', (1,2))
>>> xd {'y': [0, 1, 2], 'x': 1, 'z': (1, 2)}
>>> xd.valadd('x', 100)
>>> xd['x'] 101
>>> xd.valadd('y', range(3,6))
>>> xd['y'] [0, 1, 2, 3, 4, 5]
>>> xd.valadd('z', (3,4))
>>> xd['z']

(1, 2, 3, 4)

ISSUES

I'm thinking the idea that the counting is happening with the value corresponding
to the key should be emphasised more. Hence valadd or such?

The appendlist() method is not as versatile as setdefault() which can be used
with other object types (perhaps for creating dictionaries of dictionaries).
However, most uses I've seen are with lists. For other uses, plain Python code
suffices in terms of speed, clarity, and avoiding unnecessary instantiation of
empty containers:

if key not in d:
d.key = {subkey:value}
else:
d[key][subkey] = value

Yes, but duck typing for any obj that supports "+" gets you a lot, ISTM at this stage
of this BF ;-)

Regards,
Bengt Richter

 

[Jeff Epler]

Maybe something for sets like 'appendlist' ('unionset'?)

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)

iD8DBQFCO6KTJd01MZaTXX0RAj9IAKCr0dxRjOtbgo4GUyR5K6SbUSpA+gCgp75t
FkFSrxoiMQZcCg+GRzdaTnw=
=YF1H
-----END PGP SIGNATURE-----

 

[Raymond Hettinger]

[Jeff Epler]

Maybe something for sets like 'appendlist' ('unionset'?)

I do not follow. Can you provide a pure python equivalent?


Raymond

 

[Raymond Hettinger]

[Roose]

I like this, it is short, low impact, and makes things more readable. I
tend to go with just the literal way of doing it instead of using get and
setdefault, which I find awkward.

Thanks. Many people find setdefault() to be an oddball.

But alas I had a my short, low impact, useful suggestion and I think it
died. It was for any() and all() for lists. Actually Google just released
their "functional.py" module on code.google.com with the exact same thing.
Except they are missing the identity as a default which is very useful, i.e.
any(lst, f=lambda x: x) instead of any(lst, f).

Maybe you can tack that onto your PEP

Py2.5 is already going to include any() and all() as builtins. The signature
does not include a function, identity or otherwise. Instead, the caller can
write a listcomp or genexp that evaluates to True or False:

any(x >= 42 for x in data)

If you wanted an identify function, that simplifies to just:

any(data)


Raymond Hettinger

 

[Brian van den Broek]

Raymond Hettinger said unto the world upon 2005-03-18 20:24:

I would like to get everyone's thoughts on two new dictionary methods:

def count(self, value, qty=1):
try:
self[key] += qty
except KeyError:
self[key] = qty

def appendlist(self, key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

The rationale is to replace the awkward and slow existing idioms
for dictionary based accumulation:

d[key] = d.get(key, 0) + qty
d.setdefault(key, []).extend(values)

<SNIP>


Hi all,

I am *far* less experienced with Python and programming than those
who've weighed in as yet.

I quite like count, though I agree with posts up thread that `count'
might not be the best name.

For appendlist, I would have expected

def appendlist(self, key, sequence):
try:
self[key].extend(sequence)
except KeyError:
self[key] = list(sequence)


I am, however, very open to the possibility that this says more about
my level of experience than it does about which way is best

Best to all,

Brian vdB

 

[Bengt Richter]

]

Yes, but duck typing for any obj that supports "+" gets you a lot, ISTM at this stage
of this BF ;-)

Just in case, by "this BF," I meant to refer to my addval idea,
with no offensive charaterization of anyone else's ideas intended ;-)

Regards,
Bengt Richter

 

[Michele Simionato]

+1 for inc instead of count.
appendlist seems a bit too specific (I do not use dictionaries of lists
that often).
The problem with setdefault is the name, not the functionality.
get_or_set would be a better name: we could use it as an alias for
setdefault and then remove setdefault in Python 3000.

Just my 2 Eurocents,

Michele Simionato

 

[Paul Rubin]

+1 for inc instead of count.

I'd prefer incr or increment to inc. add is also ok. count isn't so great.
Something like add_count or inc_count or add_num or whatever could be ok.

 

[Michael Spencer]

I would like to get everyone's thoughts on two new dictionary methods:

+1 count
? appendlist

The proposed names could possibly be improved (perhaps tally() is more active
and clear than count()).

IMO 'tally' is exactly the right method name

One issue is with negative increments reaching zero i.e., deleting the key once
the tally goes to 0: this behavior would match the automatic key creation.

The appendlist() method is not as versatile as setdefault() which can be used

Simpler list initialization augmentation would be very handy - but I would also
like the equivalent functionality sets (don't care about dicts of dicts though).

Given the difference in set/list augmentation methods, this may present a
challenge. Alternatively, perhaps dict_of_list and dict_of_set could become
specialized containers - they might then have value_append/value_extend and
value_add methods respectively. I imagine (without any basis in fact) that it
would also be possible the optimize the performance of large mappings of
containers compared with the generic dict.


Michael

 

[Raymond Hettinger]

[Michele Simionato]

+1 for inc instead of count.

Any takers for tally()?

We should avoid abbreviations like inc() or incr() that different people tend to
abbreviate differently (for example, that is why the new partial() function has
its "keywords" argument spelled-out). The only other issue I see with that name
is that historically incrementing is more associated with +=1 than with +=n.
Also, there are reasonable use cases for a negative n and it would be misleading
to call it incrementing when decrementing is what is intended.

The issue with add() is that other types with that method use it for a radically
different purpose. For example, aSet.add(n) is not at all similar in function
to the proposed aDict.tally(n) or whatever it ends up being called. Of course,
count() is also problematic because the meaning doesn't parallel that for
list.count().

appendlist seems a bit too specific (I do not use dictionaries of lists
that often).

I'm curious. When you do use setdefault, what is the typical second argument?
In all the code I've encountered, nine times out of ten it is []. In the rare
case of {}, the resulting statement is a mess because both the subkey and value
need to be applied -- a pure python equivalent is much clearer. That leaves two
other mutable containers, set() and collections.deque() neither of which I've
ever seen used with setdefault().

IOW, I believe that, in practice, setdefault() is all about dictionaries of
lists. If so, I'm recommending a method that gets straight to the point with no
fuss, no waste, and no obfuscation.

In order to have some unused and unneeded versatility with respect to the
default object, I'm asserting that we've been burdened with an awkward, slow
idiom that is unnecesarily hard to learn and explain.

The problem with setdefault is the name, not the functionality.

Are you happy with the readability of the argument order? To me, the key and
default value are not at all related. Do you prefer having the default value
pre-instantiated on every call when the effort is likely to be wasted? Do you
like the current design of returning an object and then making a further (second
dot) method lookup and call for append or extend? When you first saw setdefault
explained, was it immediately obvious or did it taking more learning effort than
other dictionary methods? To me, it is the least explainable dictionary method.
Even when given a good definition of setdefault(), it is not immediately obvious
that it is meant to be futher combined with append() or some such. When showing
code to newbies or non-pythonistas, do they find the meaning of the current
idiom self-evident? That last question is not compelling, but it does contrast
with other Python code which tends to be grokkable by non-pythonistas and
clients.

get_or_set would be a better name: we could use it as an alias for
setdefault and then remove setdefault in Python 3000.

While get_or_set would be a bit of an improvement, it is still obtuse.
Eventhough a set operation only occurs conditionally, the get always occurs.
The proposed name doesn't make it clear that the method alway returns an object.

Even if a wording is found that better describes the both the get and set
operation, it is still a distractor from the intent of the combined statement,
the intent of building up a list. That is an intrinsic wording limitation that
cannot be solved by a better name for setdefault. If any change is made at all,
we ought to go the distance and provide a better designed tool rather than just
a name change.

Just my 2 Eurocents,

I raise you by a ruble and a pound ;-)


Raymond Hettinger

 

[Paul Rubin]

[Michele Simionato]

+1 for inc instead of count.

Any takers for tally()?

I'd say "tally" has some connotation of a counter that can never go
negative. I don't know if that behavior is desirable. Someone suggested
deleting the key if the tally is decremented to 0. I'd suggest instead
throwing an exception on an attempt to decrement it to less than 0.

We should avoid abbreviations like inc() or incr() that different
people tend to abbreviate differently (for example, that is why the
new partial() function has its "keywords" argument spelled-out).

Ok, "increment" then.

The only other issue I see with that name is that historically
incrementing is more associated with +=1 than with +=n. Also, there
are reasonable use cases for a negative n and it would be misleading
to call it incrementing when decrementing is what is intended.

Setting the default to 1 is enough for that. I mean, adding a negative
number to something is normally called "subtraction", but you can still
pass a negative argument to __iadd__.

The issue with add() is that other types with that method use it for
a radically different purpose. For example, aSet.add(n) is not at
all similar in function to the proposed aDict.tally(n)

Hmm, ok.

I'm curious. When you do use setdefault, what is the typical second
argument? In all the code I've encountered, nine times out of ten
it is [].

Yeah, me too.

 

[Reinhold Birkenfeld]

[Michele Simionato]

+1 for inc instead of count.

Any takers for tally()?

Well, as a non-native speaker, I had to look up this one in my
dictionary. That said, it may be bad luck on my side, but it may be that
this word is relatively uncommon and there are many others who would be
happier with increment.

Reinhold

 

[Roose]

+1 for inc instead of count.

appendlist seems a bit too specific (I do not use dictionaries of lists
that often).

No way, I use that all the time. I use that more than count, I would say.

Roose