Groupby (Python recipe) by Raymond Hettinger

ActiveState Code (http://code.activestate.com/recipes/259173/)

Zope Friendly Version. I use a Zope installation that uses Python 2.1 and it doesn't support iterators. Also, it doesn't allow variable names that start with '_'. So I made a modification to use in Zope for use in creating web reports. Just create a new script or a function within a script with the parameters seq and key (just like __init__ in the recipe). Use this code inside the function or script:

groupdict = {}
for item in seq:
  k = key(item)
  groupdict.setdefault(k, []).append(item)
return groupdict.items()

Since the Zope version that I have uses Python 2.1, it can't use iteritems, so it has to return an actual list. This means that a copy of the list of key, value pairs is created. This could drop performance if you have a large sequence.

redundant list creation. Note that in this line

self.setdefault(k, []).append(value)

an empty list is instantiated on each iteration.

I prefer to use for similar tasks a dict subclass with KeyError catched inside, like follows:

class idict(dict):
    '''self-initializing dictionnary'''
    def __init__(self,init):
        dict.__init__(self)
        self.init=init
    def __getitem__(self,key):
        try:
            return dict.__getitem__(self,key)
        except KeyError:
            if callable(self.init):
                self[key]=self.init()
            else:
                self[key]=self.init
            return dict.__getitem__(self,key)

Then the groupby could be defined as a function:

def groupby(seq, key=lambda x:x):
    d=idict(list)
    for value in seq:
        d[key(value)].append(value)
    return d.items()

This class also provides a simple way to count list entries:

def count_list_items(ll):
    d=idict(0)
    for l in ll:
        d[l]+=1
    return d.items()

Can someone put the idict in its own recipe? Recently I have used the idict class a number of times. It seems useful enough to warrant its own recipe.

Thanks, Jonathan.

idict() is pennywise and pound foolish. The cost of setdefault() instantiating an empty list is miniscule in comparison with the overhead of a __setitem__ call to idict().

An application of this nice recipe:

groupbyhead: Group a list of items according to the starting character(s) of items.

http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/259173

Getting rid of setdefault ; using defaultdict instead. def group(data, key=None):

____d=defaultdict(list)

____for v in data:

________k=key(v) if key else v

________d[k].append(v)

____return d.items()

defaultdict is New in version 2.5. Alas. I itch for it weekly.

The cost of setdefault() instantiating an empty list is miniscule in comparison with the overhead of a __setitem__ call to idict()

However, when calling d[key] many times with the same missing key, defaultdict will each time call its default, while idict fills the d[key], which is then no longer missing.

Is there a way to have defaultdict filling the key when it encounters a missing value ?

@ s_h_a_i_o Worth noting that groupby is now in the Standard Library's itertools module.