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]

[El Pitonero]

Is it even necessary to use a method name?

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]

safedict() and variants have been previously proposed with the name defaultdict
or some such.

For the most part, adding methods is much less disruptive than introducing a new
type.

As written out above, the += syntax works fine but does not work with append().

As written, the copy.copy() approach is dog slow but can be optimized for lists
and ints while retaining its type flexibility.

BTW, there is no need to make the same post three times.
Raymond

[Brian van den Broek]

Kent Johnson said unto the world upon 2005-03-19 07:19:

Brian van den Broek wrote:

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 appendlist(self , key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

For appendlist, I would have expected

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

The original proposal reads better at the point of call when values is a
single item. In my experience this will be the typical usage:
d.appendlist(ke y, 'some value')

as opposed to your proposal which has to be written
d.appendlist(ke y, ['some value'])

The original allows values to be a sequence using
d.appendlist(ke y, *value_list)

Kent

Right. I did try the alternatives out and get the issue you point to.

But:

1) In my own code, cases where I'd use the proposed appendlist method
are typically cases where I'd want to add multiple items that have
already been collected in a sequence. But, since I've little coding
under my belt, I concede that considerations drawn from my experience
are not terribly probative. :-)

2) Much more important, IMHO, is that the method name `appendlist'
really does suggest it's a list that will be appended. Hence my stated
expectation. While it would make the method name longer, given the
original interface Raymond posted, I would find appendtolist more
transparent.

out-of-my-depth-ly y'rs,

Brian vdB

[George Sakkis]

"Raymond Hettinger" <vz******@veriz on.net> wrote:

[Jeff Epler]

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

While this could work and potentially be useful, I think it is better to keep
the proposal focused on the two common use cases. Adding a third would reduce
the chance of acceptance.

Also, in all of my code base, I've not run across a single opportunity to use
something like unionset(). This is surprising because I'm the set() author and
frequently use set based algorithms. Your example was a good one and I can
also image a graph represented as a dictionary of sets. Still, I don't mind
writing out the plain Python for this one if it only comes up once in a blue
moon.

Good example. I actually have a directed graph and multigraph module that uses dictionary of sets
internally. It turns out I've used setdefault 8 times in this module alone !

George

[Roose]

Ah OK, I stand corrected. Whoops. I just read the web page and thought the
wrong thing, that makes sense.

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

[Do Re Mi chel La Si Do]

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

d[(key,subkey)] = value

?
Michel Claveau

[El Pitonero]

Raymond Hettinger wrote:

As written out above, the += syntax works fine but does not work with append(). ...
BTW, there is no need to make the same post three times.

The append() syntax works, if you use the other definition of safedict
(*). There are more than one way of defining safedict, see the subtle
differences between the two versions of safedict, and you'll be glad
more than one version has been posted. At any rate, what has been
presented is a general idea, nitpicking details is kind of out of
place. Programmers know how to modify a general receipe to suit their
actual needs, right?

(*) In some cases, people do not want to create a dictionary entry when
an inquiry is done on a missing item. In some case, they do. A general
receipe cannot cater to the needs of everybody.

[George Sakkis]

"Aahz" <aa**@pythoncra ft.com> wrote:

In article <JbL_d.8237$qN3 .2116@trndny01> ,
Raymond Hettinger <py****@rcn.com > wrote:

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

+1 tally()

-1 for count(): Implies an accessor, not a mutator.
-1 for tally(): Unfriendly to non-native english speakers.
+0.5 for add, increment. If incrementing a negative is unacceptable, how about
update/updateby/updateBy ?
+1 for accumulate. I don't think that separating the two cases -- adding to a scalar or appending to
a list -- is that essential; a self-respecting program should make this obvious by the name of the
parameter anyway ("dictionary.ac cumulate('hello ', words)" vs "a.accumulate(' hello', b)").

George

[El Pitonero]

George Sakkis wrote:

"Aahz" <aa**@pythoncra ft.com> wrote:

In article <JbL_d.8237$qN3 .2116@trndny01> ,
Raymond Hettinger <py****@rcn.com > wrote:

The proposed names could possibly be improved (perhaps tally() is more activeand clear than count()).
+1 tally()

-1 for count(): Implies an accessor, not a mutator.
-1 for tally(): Unfriendly to non-native english speakers.
+0.5 for add, increment. If incrementing a negative is unacceptable,

how about update/updateby/updateBy ?
+1 for accumulate. I don't think that separating the two cases -- adding to a scalar or appending to a list -- is that essential; a self-respecting program should make this obvious by the name of the parameter anyway ("dictionary.ac cumulate('hello ', words)" vs

"a.accumulate(' hello', b)").

What about no name at all for the scalar case:

a['hello'] += 1
a['bye'] -= 2

and append() (or augmented assignment) for the list case:

a['hello'].append(word)
a['bye'] += [word]

?

[Dan Sommers]

On Sat, 19 Mar 2005 15:17:59 GMT,
"Raymond Hettinger" <vz******@veriz on.net> wrote:

[Dan Sommers]

Curious that in this lengthy discussion, a method name of
"accumulate " never came up. I'm not sure how to separate the two
cases (accumulating scalars vs. accumulating a list), though.

Separating the two cases is essential. Also, the wording should
contain strong cues that remind you of addition and of building a
list.

Agreed, with a slight hedge towards accumulation or tabulation rather
than addition. I don't think "summation" gets us anywhere, either.

Are the use cases for qty != 1 for weighted averages (that's the only
one I can think of off the top of my head)? Is something like this:

def accumulate( self, key, *values ):
if values == ( ):
values = 1
try:
self[ key ] += values
except KeyError:
if type( key ) == int:
self[ key ] = 1
else
self[ key ] = *values

possible? It's more "klunky" than I thought it would be before I
started typing it out.

Then we'd have these two use cases:

histogram = { }
for word in text.split( ):
histogram.accum ulate( word )

and

org_chart = { }
for employee in employees:
org_chart.accum ulate( employee.manage r, employee.name )

Regards,
Dan

--
Dan Sommers
<http://www.tombstoneze ro.net/dan/>
μ₀ × ε₀ × c² = 1

[Kay Schluehr]

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

-1 form me.

I'm not very glad with both of them ( not a naming issue ) because i
think that the dict type should offer only methods that apply to each
dict whatever it contains. count() specializes to dict values that are
addable and appendlist to those that are extendable. Why not
subtractable, dividable or right-shiftable? Because of majority
approval? I'm mot a speed fetishist and destroying the clarity of a
very fundamental data structure for speedup rather arbitrary
accumulations seems to be a bad idea. I would move this stuff in a
subclass.

Regards Kay