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(ke y, []).extend(values )

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

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

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

d.count(key, qty)
d.appendlist(ke y, *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

[Raymond Hettinger]

> > d.count(key, qty)

d.appendlist(ke y, *values)

[Bengt Richter] How about an efficient duck-typing value-incrementer to replace both?
There is some Zen of Python that argues against this interesting idea. Also, I'm
concerned that by folding appendlist() into valadd() we would lose an important
cue that a list is being built-up.

Another issue is that duck-typed multiple-dispatch is only readable when the
type of the input argument is obvious from the surrounding code. Given
d.valadd(x), it is hard to grok if x was created by some code far away. Since a
primary goal is readability and clarity, having two separate, concrete methods
is likely better than having a single more-abstracted multi-purpose method. The
performance gains are just icing on the cake.
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?

How about countkey() or tabulate()?

Raymond Hettinger

[Michele Simionato]

Raymond Hettinger:

Any takers for tally()?
Dunno, to me "tally" reads "counts the numbers of votes for a candidate
in an election".
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.
I agree with Paul Rubin's argument on that issue, let's use increment()
and do not
worry about negative increments.

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?

Well, I have used setdefault *very few times* in years of heavy Python
usage.
His disappearence would not bother me that much. Grepping my source
code I find that practically
my main use case for setdefault is in a memoize recipe where the result
of a function call
is stored in a dictionary (if not already there) and returned. Then I
have a second case
with a list as second argument.

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.

Honestly, I don't care about the performance arguments. However I care
a lot about
about readability and clarity. setdefault is terrible in this respect,
since most
of the time it does *not* set a default, it just get a value. So I am
always confused
and I have to read at the documentation to remind to myself what it is
doing. The
only right name would be "get_and_possib ly_set" but it is a bit long to
type.
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.

Well, I never figured out that the intent of setdefault was to build up
a list ;)

Anyway, if I think at how many times I have used setdefault in my code
(practically
twice) and how much time I have spent trying to decipher it (any time I
reread the
code using it) I think I would have better served by NOT having the
setdefault
method available ;)

About appendlist(): still it seems a bit special purpose to me. I mean,
dictionaries
already have lots of methods and I would think twice before adding new
ones; expecially
methods that may turn out not that useful in the long range, or easily
replaceble by
user code.
Michele Simionato

[Paul Rubin]

Reinhold Birkenfeld <re************ ************@wo lke7.net> writes:

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.

It is sort of an uncommon word. As a US English speaker I'd say it
sounds a bit old-fashioned, except when used idiomatically ("let's
tally up the posts about accumulator messages") or in nonstandard
dialect ("Hey mister tally man, tally me banana" is a song about
working on plantations in Jamaica). It may be more common in UK
English. There's an expression "tally-ho!" which had something to do
with British fox hunts, but they don't have those any more.

I'd say I prefer most of the suggested alternatives (count, add,
incr/increment) to "tally".

[Roose]

> 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)

Oh great, I just saw that. I was referring to this, which didn't get much
discussion:

http://mail.python.org/pipermail/pyt...ry/051556.html

but it looks like it went much further, to builtins! I'm surprised.

But I wish it could be included in Python 2.4.x. I really hope it won't
have any bugs in it. :) At my job we are probably going to upgrade to 2.4,
and that takes a long time, so it'll probably be a year or 18 months after
that happens (which itself might be months from now) that we would consider
upgrading again. Oh well...

[Raymond Hettinger]

[Michele Simionato]

Dunno, to me "tally" reads "counts the numbers of votes for a candidate
in an election".
That isn't a pleasant image ;-)
The
only right name would be "get_and_possib ly_set" but it is a bit long to
type.

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.

Well, I never figured out that the intent of setdefault was to build up
a list ;)

Right! What does have that intent is the full statement: d.setdefault(k,
[]).append(v).

My thought is that setdefault() is rarely used by itself. Instead, it is
typically part of a longer sentence whose intent and meaning is to accumulate or
build-up. That meaning is not well expressed by the current idiom.

Raymond Hettinger

[Raymond Hettinger]

> > 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)

[Roose] Oh great, I just saw that. . . . But I wish it could be included in Python 2.4.x.

If it is any consolation, the any() can already be expressed somewhat cleanly
and efficiently in Py2.4 with genexps:

True in (x >= 42 for x in data)

The translation for all() is a little less elegant:

False not in (x >= 42 for x in data)
Raymond Hettinger

[Roose]

> 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:
Actually I was just looking at Python 2.5 docs since you mentioned this.

http://www.python.org/dev/doc/devel/whatsnew/node3.html

It says min() and max() will gain a key function parameter, and sort()
gained one in Python 2.4 (news to me).

And they do indeed default to the identity in all 3 cases, so this seems
very inconsistent. If one of them has it, and sort gained the argument even
in Python 2.4 with generator expressions, then they all should have it.
any(x >= 42 for x in data)

Not to belabor the point, but in the example on that page, max(L, key=len)
could be written max(len(x) for x in L).

Now I know why Guido said he didn't want a PEP for this... such a trivial
thing can produce a lot of opinions. : )

Roose

[Peter Otten]

Roose wrote:

Not to belabor the point, but in the example on that page, max(L, key=len)
could be written max(len(x) for x in L).

No, it can't:

Python 2.5a0 (#2, Mar 5 2005, 17:44:37)
[GCC 3.3.3 (SuSE Linux)] on linux2
Type "help", "copyright" , "credits" or "license" for more information.

max(["a", "bbb", "cc"], key=len)

'bbb'

Peter

[Raymond Hettinger]

[Roose]

Actually I was just looking at Python 2.5 docs since you mentioned this.

http://www.python.org/dev/doc/devel/whatsnew/node3.html

It says min() and max() will gain a key function parameter, and sort()
gained one in Python 2.4 (news to me).
It also appears in itertools.group by() and, for Py2.5, in heapq.nsmallest () and
heapq.nlargest( ).

And they do indeed default to the identity in all 3 cases, so this seems
very inconsistent. If one of them has it, and sort gained the argument even
in Python 2.4 with generator expressions, then they all should have it.

any(x >= 42 for x in data)

Not to belabor the point, but in the example on that page, max(L, key=len)
could be written max(len(x) for x in L).

Think about it. A key= function is quite a different thing. It provides a
*temporary* comparison key while retaining the original value. IOW, your
re-write is incorrect:

L = ['the', 'quick', 'brownish', 'toad']
max(L, key=len) 'brownish' max(len(x) for x in L)

8
Remain calm. Keep the faith. Guido's design works fine.

No important use cases were left unserved by any() and all().

Raymond Hettinger

[El Pitonero]

On Sat, 19 Mar 2005 01:24:57 GMT, "Raymond Hettinger"
<vz******@veriz on.net> wrote:

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)

Bengt Richter wrote:

>>> class xdict(dict):

... def valadd(self, key, incr=1):
... try: self[key] = self[key] + type(self[key])(incr)
... except KeyError: self[key] = incr

What about:

import copy
class safedict(dict):
def __init__(self, default=None):
self.default = default
def __getitem__(sel f, key):
try:
return dict.__getitem_ _(self, key)
except KeyError:
return copy.copy(self. default)

x = safedict(0)
x[3] += 1
y = safedict([])
y[5] += range(3)
print x, y
print x[123], y[234]