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

[Paul Rubin]

"El Pitonero" <pi******@gmail .com> writes:

What about no name at all for the scalar case:

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

I like this despite the minor surprise that it works even when
a['hello'] is uninitialized.

[Bengt Richter]

On Sat, 19 Mar 2005 07:13:15 -0500, Kent Johnson <ke****@tds.net > wrote:

Bengt Richter wrote:

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)

How about an efficient duck-typing value-incrementer to replace both? E.g. functionally like:

>>> class xdict(dict):

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

A big problem with this is that there are reasonable use cases for both
d.count(key, <some integer>)
and
d.appendlist(ke y, <some integer>)

Word counting is an obvious use for the first. Consolidating a list of key, value pairs where the
values are ints requires the second.

Combining count() and appendlist() into one function eliminates the second possibility.

I don't see a "big problem" ;-)

d.addval doesn't eliminate the functionalities if you want them. You just have to spell them
d.addval(key, <some integer>)
and
d.addval(key, [<some integer>])
respectively.

My example interactive stuff in a previous post shows both of these using xd['x'] and xd.['y']:
"""

xd = xdict()
xd {}

Default integer 1 arg creates initial int value xd.valadd('x')
xd {'x': 1}

Explicit list arg create initial list value xd.valadd('y', range(3))
xd {'y': [0, 1, 2], 'x': 1}

Explicit int increment adds to existing int xd.valadd('x', 100)
xd['x'] 101

Explicit list arg extends existing list with contents of increment list
which you can of course optionally use with a length-1 list to achieve the .append effect xd.valadd('y', range(3,6))
xd['y']

[0, 1, 2, 3, 4, 5]
"""

Granted, d.appendlist will result in more efficient code, since the temp list arg
[<some integer>] does not have to be created and the type of the existing dict value
does not have to be tested as generally. OTOH, you can create and extend tuple
or even custom object values using valadd, and extend with alternate sequences that
get converted to the existing type if its contructor knows how to accept alternatives.

So I think you are not prevented from doing anything. IMO Raymond's Zen concerns
are the ones to think about first, and then efficiency, which was one of the motivators
in the first place ;-)

Regards,
Bengt Richter

[John Machin]

Raymond Hettinger wrote:

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

+1 for each.
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.
+1 to EACH of the above 3 points.

A question directed to the folk who had to look up "tally" in the
dictionary: Which dictionary includes "setdefault ", "updateBy", etc?

The performance issues with the existing constructs are:
[MANY]
the performance improvement matches the readability
improvement.
Agreed.


ISSUES
------

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

appendtolist is better than appendlist

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.

My use cases for tally:
(1) Yes the text-book "word" frequency gig applied in production
data-matching etc applications
(2) quick stats like from SQL "group by" e.g.
customer.tally( state)
customer_value. tally(state, dollar_value) # real or *DECIMAL*

Use cases for appendlist: many; in general, how else do you implement a
one-to-many relationship in memory??

[Reinhold Birkenfeld]

John Machin wrote:

Raymond Hettinger wrote:

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

methods:

+1 for each.

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.

+1 to EACH of the above 3 points.

A question directed to the folk who had to look up "tally" in the
dictionary: Which dictionary includes "setdefault ", "updateBy", etc?

Are you kidding? If you know what "set" and "default" means, you will be
able to guess what "setdefault " means. Same goes for updateBy.

Of course, I had to look up setdefault in the Python docs the first time
I ran across it, but in the case of tally, I would have to look up both
in the Python docs and in my dictionary.

Reinhold

[Raymond Hettinger]

[Bengt Richter]

IMO Raymond's Zen concerns
are the ones to think about first, and then efficiency, which was one of the motivators in the first place ;-)

Well said.

I find the disassembly (presented in the first post) to be telling. The
compiler has done a great job and there is no fluff -- all of those steps have
been specified by the programmer and he/she must at some level be aware of every
one of them (pre-instantiation, multiple method lookups and calls, multiple
dictionary accesses, etc). That is too bad because the intent could have been
stated atomically: d.appendlist(k, v). Instead, the current idiom turns you
away from what you want done and focuses the attention on how it is done:
d.setdefault(k, []).append(v). That is too many steps for what should be an
atomic operation (in the eyes of the programmer and code readers).

Likewise, d.tally(k) is as atomic as this expression can get. Any other steps,
added verbiage, new types, extra arguments, or whatnot are an unnecessary waste
of brain cells.
Raymond Hettinger

[Paul Rubin]

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

I find the disassembly (presented in the first post) to be telling.
The compiler has done a great job and there is no fluff -- all of
those steps have been specified by the programmer and he/she must at
some level be aware of every one of them (pre-instantiation,
multiple method lookups and calls, multiple dictionary accesses, etc).

If the compiler can do some type inference, it can optimize out those
multiple calls pretty straightforward ly.

[John Machin]

Reinhold Birkenfeld wrote:

John Machin wrote:
Are you kidding? If you know what "set" and "default" means, you will be able to guess what "setdefault " means. Same goes for updateBy.

No I'm not kidding -- people from some cultures have no difficulty at
all in mentally splitting up "words" like "setdefault " or the German
equivalent of "Danubesteamnav igationcompany' sdirector'swife "; others
from other cultures where agglutinisation is not quite so rife will
have extreme difficulty.

And "Updateby" sounds like a village somewhere in the Danelaw :-)

[David Eppstein]

In article <JbL_d.8237$qN3 .2116@trndny01> ,
"Raymond Hettinger" <vz******@veriz on.net> 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 )

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.

The other dictionary based accumulation I've used but don't see here is
with sets as dictionary values, i.e.
dictionary.setd efault(key,set( )).add(value).

I suppose it would be possible to appendlist then make a set from the
list, but if you were to take that minimalist philosophy to an extreme
you wouldn't need count either, you could just appendlist then use len.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

[David Eppstein]

In article <GoX_d.9343$qN3 .2772@trndny01> ,
"Raymond Hettinger" <vz******@veriz on.net> wrote:

Also, in all of my code base, I've not run across a single opportunity to use
something like unionset().

In my code, this would be roughly tied with appendlist for frequency of
use.

--
David Eppstein
Computer Science Dept., Univ. of California, Irvine
http://www.ics.uci.edu/~eppstein/

[Ron]

On 19 Mar 2005 11:33:20 -0800, "Kay Schluehr" <ka**********@g mx.net>
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)

-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
accumulation s seems to be a bad idea. I would move this stuff in a
subclass.

Regards Kay

-1 for me too.

I agree with this. The other dictionary functions are all data
nuetral. Adding special methods to handle data should be in a
durrived class and not a built in. imho.

# Roll your own specialized dictionaries.

class NumDict( dict):
def count(self, key, 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)

mydict = NumDict()

n = 0
for k in list('abcdefg') :
n += 1
mydict[k] = n

print mydict
# {'a': 1, 'c': 3, 'b': 2, 'e': 5, 'd': 4, 'g': 7, 'f': 6}

mydict.count('c ')
mydict['e'] = ['a']
mydict.appendli st('e', 'bcdef')
print mydict
# {'a': 1, 'c': 4, 'b': 2, 'e': ['a', 'bcdef'], 'd': 4, 'g': 7, 'f':
6}
This isn't that hard to do. I don't think the extra methods should be
added to the base class.

Ron