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

[haraldarminmassa]

Raymond,

I am +1 for both suggestions, tally and appendlist.

Extended:

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.

I am more than sure you are right about this. But, please keep in mind
that you and we all have come very, very accustomed to using lists for
everything and the kitchen sink in Python.

Lists where there from the beginning of Python, and even before the
birth of Python; very powerfull, well implemented and theoretically
well founded datastructures - I heared there is a whole language based
on list processing. *pun intended*

sets on the other hand --- I know, in mathematics they have a deep,
long history. But in programming? Yeah, in SQL and ABAP/4 basically
you are doing set operations on every join. But its rather uncommon to
call it set.

With 2.3 Python grew a set module. And, in ONLY ONE revision it got
promoted to a buildin type - a honour only those who read c.l.p.d.
regualary can value correctly.

And sets are SO NATURALLY for a lot of problems ... I never thought of
replacing my "list in dict" constructs with sets before, BUT ....
there are 90% of problem domains where order is not important, AND
fast membership testing is a unique sales point.

So please for best impressions: let us have a look at our code, where
we use the
dict.setdefault (key,[]).append() idiom, where it could be replaced to
a better effectivity with dict.setdefault (key,set()).add ()

If it is less than 60%, forget it. If it is more....

Harald

[AndrewN]

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)

-0.9

Not impressed, they feel too specific for being builtin dictionary
methods and give the impression of just trying to save a few lines here
and there. I don't feel the names convey the functionality of the
methods either.

I know there's the speed argument but I'd rather not have these on the
dict at all.

+0.1

I sort of feel a slight need for this. But where would you stop? What
if people decrement lots? what if next there's a need for division? How
would you determine how you add the item to the key if it already
exists? In a general way:

mydict.set(key, value=None, default=None, how=operator.se titem)

This feels slightly better as it's not tied down to what sort of item
you're setting. But:

for word in words:
mydict.set(word , 1, 0, operator.add)

I dunno, feels a bit verbose maybe.
The setdefault() method would continue to exist but would likely not make it into Py3.0.
I agree that setdefault is wart though.

And for dict.default = value:

(Quoth RON):

"""With a preset default mode, it then becomes possible to
inadvertently
create default values that will cause problems without knowing it. So
then we have to remember to change the setdefault value to None or
null to avoid problems. Ouch!"""

Agreed, -1 there then.
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.

I feel this only really applies for setdefault (which I wouldn't be
sorry to see the back of). And your examples:

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

Would better be written in a long-handed fashion anyway as per the
implementations were suggested:

try:
d[key] += qty
except KeyError:
d[key] = 0

Yeah, yeah, I know, speed. But not like this. Sorry.

[Michele Simionato]

FWIW, here is my take on the defaultdict approach:

def defaultdict(def aultfactory, dictclass=dict) :
class defdict(dictcla ss):
def __getitem__(sel f, key):
try:
return super(defdict, self).__getitem __(key)
except KeyError:
return self.setdefault (key, defaultfactory( ))
return defdict

d = defaultdict(int )()
d["x"] += 1
d["x"] += 1
d["y"] += 1
print d

d = defaultdict(lis t)()
d["x"].append(1)
d["x"].append(2)
d["y"].append(1)
print d

Michele Simionato

[George Sakkis]

"Michele Simionato" <mi************ ***@gmail.com> wrote:

FWIW, here is my take on the defaultdict approach:

def defaultdict(def aultfactory, dictclass=dict) :
class defdict(dictcla ss):
def __getitem__(sel f, key):
try:
return super(defdict, self).__getitem __(key)
except KeyError:
return self.setdefault (key, defaultfactory( ))
return defdict

d = defaultdict(int )()
d["x"] += 1
d["x"] += 1
d["y"] += 1
print d

d = defaultdict(lis t)()
d["x"].append(1)
d["x"].append(2)
d["y"].append(1)
print d

Michele Simionato

Best solution so far. If it wasn't for the really bad decision to add the dict(**kwargs)
constructor, I'd love to see something like
d = dict(valType=in t)
d["x"] += 1

George

[Evan Simpson]

Raymond Hettinger wrote:

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

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

def appendlist(self , key, *values):

-1.0

When I need these, I just use subtype recipes. They seem way too
special-purpose for the base dict type.

class Counter(dict):
def __iadd__(self, other):
if other in self:
self[other] += 1
else:
self[other] = 1
return self

c = Counter()
for item in items:
c += item

class Collector(dict) :
def add(self, key, value):
if key in self:
self[key].append(value)
else:
self[key] = [value]

c = Collector()
for k,v in items:
c.add(k, v)

Cheers,

Evan @ 4-am

[Greg Ewing]

Michele Simionato wrote:

def defaultdict(def aultfactory, dictclass=dict) :
class defdict(dictcla ss):
def __getitem__(sel f, key):
try:
return super(defdict, self).__getitem __(key)
except KeyError:
return self.setdefault (key, defaultfactory( ))
return defdict

That looks really nice!

I'd prefer a more elegant name than 'defaultdict', though.
How about 'table'?

--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg

[Roose]

I agree -- I find myself NEEDING sets more and more. I use them with this
idiom quite often. Once they become more widely available (i.e. Python 2.3
is installed everywhere), I will use them almost as much as lists I bet.

So any solution IMO needs to at least encompass sets. But preferably
something like the Dict with Default approach which encompasses all
possibilities.

Roose

I am more than sure you are right about this. But, please keep in mind
that you and we all have come very, very accustomed to using lists for
everything and the kitchen sink in Python.

Lists where there from the beginning of Python, and even before the
birth of Python; very powerfull, well implemented and theoretically
well founded datastructures - I heared there is a whole language based
on list processing. *pun intended*

sets on the other hand --- I know, in mathematics they have a deep,
long history. But in programming? Yeah, in SQL and ABAP/4 basically
you are doing set operations on every join. But its rather uncommon to
call it set.

With 2.3 Python grew a set module. And, in ONLY ONE revision it got
promoted to a buildin type - a honour only those who read c.l.p.d.
regualary can value correctly.

And sets are SO NATURALLY for a lot of problems ... I never thought of
replacing my "list in dict" constructs with sets before, BUT ....
there are 90% of problem domains where order is not important, AND
fast membership testing is a unique sales point.

So please for best impressions: let us have a look at our code, where
we use the
dict.setdefault (key,[]).append() idiom, where it could be replaced to
a better effectivity with dict.setdefault (key,set()).add ()

If it is less than 60%, forget it. If it is more....

Harald

[Steve Holden]

Greg Ewing wrote:

Michele Simionato wrote:

def defaultdict(def aultfactory, dictclass=dict) :
class defdict(dictcla ss):
def __getitem__(sel f, key):
try:
return super(defdict, self).__getitem __(key)
except KeyError:
return self.setdefault (key, defaultfactory( ))
return defdict

That looks really nice!

I'd prefer a more elegant name than 'defaultdict', though.
How about 'table'?

By obvious analogy with Icon (where the dictionary-like object was
created with the option of a default value) this gets my +1.

regards
Steve
--
Meet the Python developers and your c.l.py favorites March 23-25
Come to PyCon DC 2005 http://www.pycon.org/
Steve Holden http://www.holdenweb.com/

[bearophileHUGS]

R.H.:

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

I agee to remove the setdefault.

I like the new count method, but I don't like the appendlist method,
because I think it's too much specilized.

I too use sets a lot; recently I've suggested to add a couple of set
methods to dicts (working on the keys): intersection() and
difference().

Bearophile

[Christos TZOTZIOY Georgiou]

On Sat, 19 Mar 2005 01:24:57 GMT, rumours say that "Raymond Hettinger"
<vz******@veriz on.net> might have written:

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)

Both are useful and often needed, so I am +1 on adding such
functionality. However, I am -0 on adding methods to dict.

I believe BJörn Lindqvist suggested a subtype of dict instead, which
feels more right. I believe this is a type of 'bag' collection, and it
could go to the collections module.

The default argument 99% of the time is the same for all calls to
setdefault of a specific instance. So I would suggest that the default
argument should be an attribute of the bag instance, given at instance
creation. And since unbound methods are going to stay, we can use the
accumulator method as a default argument (ie int.__add__ or list.append)

Based on the above, I would suggest something like the following
implementation, waiting criticism on names, algorithm or applicability:)

..class bag(dict):
.. def __init__(self, accumulator=int .__add__):
.. self.accumulato r = accumulator
..
.. # refinement needed for the following
.. self.accu_class = accumulator.__o bjclass__
..
.. # if there was an exception, probably the accumulator
.. # provided was not appropriate
..
.. def accumulate(self , key, value):
.. try:
.. old_value = self[key]
.. except KeyError:
.. self[key] = old_value = self.accu_class ()
.. new_value = self.accumulato r(old_value, item)
..
.. # and this needs refinement
.. if new_value is not None: # method of immutable object
.. self[key] = new_value

This works ok for int.__add__ and list.append.

PS I wrote these more than 36 hours ago, and before having read the
so-far downloaded messages of the thread. I kept on reading and
obviously others thought the same too (default argument at
initialisation) .

What the heck, Bengt at least could like the class method idea :)
--
TZOTZIOY, I speak England very best.
"Be strict when sending and tolerant when receiving." (from RFC1958)
I really should keep that in mind when talking with people, actually...