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

[Reinhold Birkenfeld]

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.

So, would the `setdefaultvalu e' approach be more consistent in your eyes?

Reinhold

[Roose]

> How about the alternative approach of allowing the user to override the

action to be taken when accessing a non-existent key?

d.defaultValue( 0)

I like this a lot. It makes it more clear from the code what is going on,
rather than having to figure out what the name appendlist, count, tally,
whatever, is supposed to mean. When you see the value you'll know.

It's more general, because you can support dictionaries and sets then as
well.

I think someone mentioned that it might be a problem to add another piece of
state to all dicts though. I don't know enough about the internals to say
anything about this.

setdefault gets around this by having you pass in the value every time, so
it doesn't have to store it. It's very similar, but somehow many times more
awkward.

[Kay Schluehr]

Duncan Booth wrote:

Raymond Hettinger wrote:

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 )

How about the alternative approach of allowing the user to override

the action to be taken when accessing a non-existent key?

d.defaultValue( 0)

and the accumulation becomes:

d[key] += 1

and:

d.defaultValue( function=list)

would allow a safe:

d[key].extend(values)

+0

The best suggestion up to now. But i find this premature because it
addresses only a special aspect of typing issues which should be
disussed together with Guidos type guard proposals in a broader
context. Besides this the suggestion though feeling pythonic is still
uneven.

Why do You set

d.defaultValue( 0)
d.defaultValue( function=list)

but not

d.defaultValue( 0)
d.defaultValue([])

?

And why not dict(type=int), dict(type=list) instead where default
values are instantiated during object creation? A consistent pythonic
handling of all types should be envisioned not some ad hoc solutions
that go deprecated two Python releases later.

Regards Kay

[Max]

Paul Rubin wrote:

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.

Has anyone _not_ heard Jeff Probst say, "I'll go tally the votes"?!

:)

--Max

[Peter Hansen]

Max wrote:

Has anyone _not_ heard Jeff Probst say, "I'll go tally the votes"?!

:)

Who is Jeff Probst?

[Matteo Dell'Amico]

Kay Schluehr wrote:

Why do You set

d.defaultValue( 0)
d.defaultValue( function=list)

but not

d.defaultValue( 0)
d.defaultValue([])

?
I think that's because you have to instantiate a different object for
each different key. Otherwise, you would instantiate just one list as a
default value for *all* default values. In other words, given:

class DefDict(dict):
def __init__(self, default):
self.default = default
def __getitem__(sel f, item):
try:
return dict.__getitem_ _(self, item)
except KeyError:
return self.default

you'll get

In [12]: d = DefDict([])

In [13]: d[42].extend(['foo'])

In [14]: d.default
Out[14]: ['foo']

In [15]: d[10].extend(['bar'])

In [16]: d.default
Out[16]: ['foo', 'bar']

In [17]: d[10]
Out[17]: ['foo', 'bar']

In [18]: d[10] is d.default
Out[18]: True

and this isn't what you really wanted.

By the way, to really work, I think that Duncan's proposal should create
new objects when you try to access them, and to me it seems a bit
counterintuitiv e. Nevertheless, I'm +0 on it.
And why not dict(type=int), dict(type=list) instead where default
values are instantiated during object creation? A consistent pythonic
handling of all types should be envisioned not some ad hoc solutions
that go deprecated two Python releases later.

I don't really understand you. What should 'type' return? A callable
that returns a new default value? That's exactly what Duncan proposed
with the "function" keyword argument.

--
Ciao,
Matteo

[Magnus Lie Hetland]

In article <JbL_d.8237$qN3 .2116@trndny01> , 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
Yes, yes, YES!

*Man*, this would be useful.
def appendlist(self , key, *values):
try:
self[key].extend(values)
except KeyError:
self[key] = list(values)

Woohoo! *Just* as useful.

I'd *definitely* use these.

Hot 100% sure about the names, though. (add() and append() seem like
more natural names -- but they may be confusing, considering their
other uses...)

+1 on both (possibly allowing for some naming discussion...)

--
Magnus Lie Hetland Time flies like the wind. Fruit flies
http://hetland.org like bananas. -- Groucho Marx

[BJörn Lindqvist]

I like count() and appendlist() or whatever they will be named. But I
have one question/idea:

Why does the methods have to be put in dict? Can't their be a subtype
of dict that includes those two methods? I.e.:

..histogram = counting_dict()
..for ch in text:
.. histogram.count (ch)

Then maybe some more methods can be added tailor-mode for these two
types of dicts?:

..for ch in string.ascii_le tters:
.. print "Frequency of %s = %d." % (ch, histogram.freq( ch))

Or something, you get the idea.

--
mvh Björn

[Duncan Booth]

Roose wrote:

I think someone mentioned that it might be a problem to add another
piece of state to all dicts though. I don't know enough about the
internals to say anything about this.

setdefault gets around this by having you pass in the value every
time, so it doesn't have to store it. It's very similar, but somehow
many times more awkward.

Another option with no storage overhead which goes part way to reducing
the awkwardness would be to provide a decorator class accessible through
dict. The decorator class would take a value or function to be used as
the default, but apart from __getitem__ would simply forward all other
methods through to the underlying dictionary.

That gives you the ability to have not one default value for a
dictionary, but many different ones: you just decorate the dictionary
anywhere you need a default and use the underlying dictionary everywhere
else.

Some code which demonstrates the principle rather than the
implementation. dictDefaultValu e could be imagined as
dict.defaultVal ue, dictDefaultValu e(d, ...) could be
d.defaultValue( ...) although the actual name used needs work:

class dictDefaultValu e(object): def __init__(self, d, value=_marker, function=_marke r):
self.__d = d
if value is _marker:
if function is _marker:
raise TypeError, "expected either value or function argument"
self.__dv = function
else:
def defaultValue():
return value
self.__dv = defaultValue

def __getattr__(sel f, name):
return getattr(self.__ d, name)

def __getitem__(sel f, name):
try:
return self.__d[name]
except KeyError:
value = self.__dv()
self.__d[name] = value
return value

def __setitem__(sel f, name, value):
self.__d[name] = value

d = {}
accumulator = dictDefaultValu e(d, 0)
accumulator['a'] += 1
aggregator = dictDefaultValu e(d, function=list)
aggregator['b'].append('hello' )
d {'a': 1, 'b': ['hello']}

[Kay Schluehr]

Matteo Dell'Amico wrote:

Kay Schluehr wrote:

Why do You set

d.defaultValue( 0)
d.defaultValue( function=list)

but not

d.defaultValue( 0)
d.defaultValue([])

?
I think that's because you have to instantiate a different object for

each different key. Otherwise, you would instantiate just one list as a default value for *all* default values.
Or the default value will be copied, which is not very hard either or
type(self._defa ult)() will be called. This is all equivalent and it
does not matter ( except for performance reasons ) which way to go as
long only one is selected.

[...]
By the way, to really work, I think that Duncan's proposal should create new objects when you try to access them, and to me it seems a bit
counterintuitiv e.
If the dict has a fixed semantics by applying defaultValue() and it
returns defaults instead of exceptions whenever a key is missing i.e.
behavioural invariance the client of the dict has nothing to worry
about, hasn't he?

And why not dict(type=int), dict(type=list) instead where default
values are instantiated during object creation? A consistent pythonic handling of all types should be envisioned not some ad hoc solutions that go deprecated two Python releases later.

I don't really understand you. What should 'type' return?
A callable
that returns a new default value? That's exactly what Duncan proposed

with the "function" keyword argument.

I suspect the proposal really makes sense only if the dict-values are
of the same type. Filling it with strings, custom objects and other
stuff and receiving 0 or [] or '' if a key is missing would be a
surprise - at least for me. Instantiating dict the way I proposed
indicates type-guards! This is the reason why I want to delay this
issue and discuss it in a broader context. But I'm also undecided.
Guidos Python-3000 musings are in danger to become vaporware. "Now is
better then never"... Therefore +0.

Regards Kay