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

[George Sakkis]

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

+1 on this. The new suggested operations are meaningful for a subset of all valid dicts, so they
should not be part of the base dict API. If any version of this is approved, it will clearly be an
application of the "practicali ty beats purity" zen rule, and the justification for applying it in
this case instead of subclassing should better be pretty strong; so far I'm not convinced though.

George

[Michael Spencer]

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)

These undoubtedly address common cases, which are unsatisfactory when spelled
using setdefault. However...

Use of these methods implicitly specializes the dictionary. The methods are
more-or-less mutually exclusive i.e., it would be at least strange to use count
and appendlist on the same dictionary. Moreover, on many dictionary instances,
the methods would fail or produce meaningless results.

This seems to be at odds with the other methods of built-in container types
which can be meaningfully applied, no matter what the types of the contents.
(There may be exceptions, but I can't think of any at the moment)

Does anyone else think this is a problem?

Michael

[George Sakkis]

Michael Spencer wrote:

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)

These undoubtedly address common cases, which are unsatisfactory when

spelled using setdefault. However...

Use of these methods implicitly specializes the dictionary. The methods are more-or-less mutually exclusive i.e., it would be at least strange to use count and appendlist on the same dictionary. Moreover, on many dictionary instances, the methods would fail or produce meaningless results.

This seems to be at odds with the other methods of built-in container types which can be meaningfully applied, no matter what the types of the contents. (There may be exceptions, but I can't think of any at the moment)

Does anyone else think this is a problem?

Michael

Yep, at least three more people in this thread:
- http://tinyurl.com/4bsdf
- http://tinyurl.com/3seqx
- http://tinyurl.com/6db27

George

[Alexander Schmolck]

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

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)

Yuck.

The relatively recent "improvemen t" of the dict constructor signature
(``dict(foo=bar ,...)``) obviously makes it impossible to just extend the
constructor to ``dict(default= ...)`` (or anything else for that matter) which
would seem much less ad hoc. But why not use a classmethod (e.g.
``d=dict.withde fault(0)``) then?

Or, for the first and most common case, just a bag type?
'as

[John Machin]

George Sakkis wrote:

+1 on this. The new suggested operations are meaningful for a subset of all valid dicts, so they should not be part of the base dict API. If any version of this is approved, it will clearly be an application of the "practicali ty beats purity" zen rule, and the justification for applying it in this case instead of subclassing should better be pretty strong; so

far I'm not convinced though.

My background: I've been subclassing dict since this was possible, to
provide not only a count/tally method but also a DIY intern method.
Before that I just copied dictmodule.c (every release!) and diffed and
hacked about till I had a mydict module.

*any* version? Could we make you happy by having a subclass
TotallySinfulDi ct provided as part of the core? You don't have to use
it -- come to think of it, you don't have to use a sinful method in the
base dict. You could even avert your gaze when reading the
documentation.

The justification for having it in the core: it's in C, not in Python,
it gets implemented and maintained (a) ONCE (b) by folk like the timbot
and Raymond instead of having (a) numerous versions lashed up (b) by
you and me and a whole bunch of n00bz and b1ffz :-)

[Beni Cherniavsky]

Alexander Schmolck wrote:

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

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 )
Indeed not too readable. The try..except version is better but is too
verbose. There is a simple concept underneath of assuming a default value and
we need "one obvious" way to write it.
In simplest form, those two statements would now be coded more readably as:

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

-1 from me too on these two methods because they only add "duct tape" for the
problem instead of solving it. We need to improve upon `dict.setdefaul t()`,
not specialize it.
The relatively recent "improvemen t" of the dict constructor signature
(``dict(foo=bar ,...)``) obviously makes it impossible to just extend the
constructor to ``dict(default= ...)`` (or anything else for that matter) which
would seem much less ad hoc. But why not use a classmethod (e.g.
``d=dict.withde fault(0)``) then?
You mean giving a dictionary a default value at creation time, right?

Such a dictionary could be used very easily, as in <gasp>Perl::

foreach $word ( @words ) {
$d{$word}++; # default of 0 assumed, simple code!
}

</gasp>. You would like to write::

d = dict.withdefaul t(0) # or something
for word in words:
d[word] += 1 # again, simple code!

I agree that it's a good idea but I'm not sure the default should be specified
at creation time. The problem with that is that if you pass such a dictionary
into an unsuspecting function, it will not behave like a normal dictionary.
Also, this will go awry if the default is a mutable object, like ``[]`` - you
must create a new one at every access (or introduce a rule that the object is
copied every time, which I dislike). And there are cases where in different
points in the code operating on the same dictionary you need different default
values.

So perhaps specifying the default at every point of use by creating a proxy is
cleaner::

d = {}
for word in words:
d.withdefault(0 )[word] += 1

Of course, you can always create the proxy once and still pass it into an
unsuspecting function when that is actually what you mean.

How should a dictionary with a default value behave (wheter inherently or a
proxy)?

- ``d.__getattr__ (key)`` never raises KeyError for missing keys - instead it
returns the default value and stores the value as `d.setdefult()` does.
This is needed for make code like::

d.withdefault([])[key].append(foo)

to work - there is no call of `d.__setattr__( )`, so `d.__getattr__( )` must
have stored it.

- `d.__setattr__( )` and `d.__delattr__( )` behave normally.

- Should ``key in d`` return True for all keys? It is desiarable to have
*some* way to know whether a key is really present. But if it returns False
for missing keys, code that checks ``key in d`` will behave differently from
normally equivallent code that uses try..except. If we use the proxy
interface, we can always check on the original dictionary object, which
removes the problem.

- ``d.has_key(key )`` must do whatever we decide ``key in d`` does.

- What should ``d.get(key, [default])`` and ``d.setdefault( key, default)``
do? There is a conflict between the default of `d` and the explicitly given
default. I think consistency is better and these should pretend that `key`
is always present. But either way, there is a subtle problem here.

- Of course `iter(d)`, `d.items()` and the like should only see the keys
that are really present (the alternative inventing an infinite amount of
items out of the blue is clearly bogus).

If the idea that the default should be specified in every operation (creating
a proxy) is accepted, there is a simpler and more fool-proof solution: the
ptoxy will not support anything except `__getitem__()` and `__setitem__()` at
all. Use the original dictionary for everything else. This prevents subtle
ambiguities.
Or, for the first and most common case, just a bag type?

Too specialized IMHO. You want a dictionary with any default anyway. If you
have that, what will be the benefit of a bag type?

[George Sakkis]

"John Machin" <sj******@lexic on.net> wrote in message
news:11******** **************@ g14g2000cwa.goo glegroups.com.. .

George Sakkis wrote:

+1 on this. The new suggested operations are meaningful for a subset

of all valid dicts, so they

should not be part of the base dict API. If any version of this is

approved, it will clearly be an

application of the "practicali ty beats purity" zen rule, and the

justification for applying it in

this case instead of subclassing should better be pretty strong; so

far I'm not convinced though.

My background: I've been subclassing dict since this was possible, to
provide not only a count/tally method but also a DIY intern method.
Before that I just copied dictmodule.c (every release!) and diffed and
hacked about till I had a mydict module.

*any* version? Could we make you happy by having a subclass
TotallySinfulDi ct provided as part of the core? You don't have to use
it -- come to think of it, you don't have to use a sinful method in the
base dict. You could even avert your gaze when reading the
documentation.

The justification for having it in the core: it's in C, not in Python,
it gets implemented and maintained (a) ONCE (b) by folk like the timbot
and Raymond instead of having (a) numerous versions lashed up (b) by
you and me and a whole bunch of n00bz and b1ffz :-)

I believe it was pretty clear that I'm not against a new dict extension, in the core or in the
standard library; the proposed functionality is certainly useful and it would be most welcome. I
just don't find it appropriate for the existing base dict because it is not applicable to *every*
dictionary. As for the "you don't have to use feature X if you don't like it" argument, it's rarely
relevant in language design.

George

[Kay Schluehr]

George Sakkis wrote:

-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

+1 on this. The new suggested operations are meaningful for a subset of all valid dicts, so they
should not be part of the base dict API. If any version of this is approved, > it will clearly be an application of the "practicali ty beats purity" zen rule, and the
justification for applying it in
this case instead of subclassing should better be pretty strong; so far I'm not convinced though.

George

It is bad OO design, George. I want to be a bit more become more
specific on this and provide an example:

Let be <intdict> a custom subclass of dict that stores only ints as
keys as well as values:

class intdict(dict):
def __setitem__(sel f, key, value):
assert isinstance(key, int) and isinstance(valu e, int)
dict.__setitem_ _(self,key,valu e)

or in Python3000 typeguard fashion:

class intdict(dict):
def __setitem__(sel f, key:int, value:int):
dict.__setitem_ _(self,key,valu e)

But <intdict> still overloads appendlist() i.e. a method that does not
work for any intdict is still part of it's public interface! This is
really bad design and should not be justified by a "practicali ty beats
purity" wisdom which should be cited with much care but not
carelesness.

Maybe also the subclassing idea I introduced falls for short for the
same reasons. Adding an accumulator to a dict should be implemented as
a *decorator* pattern in the GoF meaning of the word i.e. adding an
interface to some object at runtime that provides special facilities.

Usage:

d = intdict(extend= MyAccumulator)
hasattr(d,"tall y") True hasattr(d,"appe ndlist")

False

This could be generalized to other fundamental data structures as well.

Regards Kay

[Michael Spencer]

Kay Schluehr wrote:

Maybe also the subclassing idea I introduced falls for short for the
same reasons. Adding an accumulator to a dict should be implemented as
a *decorator* pattern in the GoF meaning of the word i.e. adding an
interface to some object at runtime that provides special facilities.

Usage:

d = intdict(extend= MyAccumulator)
hasattr(d," tally")
True
hasattr(d," appendlist")
False

This could be generalized to other fundamental data structures as well.

Regards Kay

Or similarly, something like the 'reversed' view of a sequence:

I could imagine a class: accumulator(map ping, default, incremetor) such that:

my_tally = accumulator({}, 0, operator.add) or my_dict_of_list s = accumulator({}, [], list.append) or my_dict_of_sets = accumulator({}, set(), set.add)

then: .accumulate(key , value) "does the right thing" in each case.

a bit cumbersome, because of having to specify the accumulation method, but
avoids adding methods to, or sub-classing dict

Michael

[Michele Simionato]

I am surprised nobody suggested we put those two methods into a
separate module (say dictutils or even UserDict) as functions:

from dictutils import tally, listappend

tally(mydict, key)
listappend(mydi ct, key, value)

I am -1 about a specific subclass of dict in the standard library, I
would not mind about a few new functions
in an utility module.

Michele Simionato