python histogram one-liner

Question

There are many ways to write a Python program that computes a histogram.

By histogram, I mean a function that counts the occurrence of objects in an iterable and outputs the counts in a dictionary. For example:

>>> L = 'abracadabra'
>>> histogram(L)
{'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2}

One way to write this function is:

def histogram(L):
    d = {}
    for x in L:
        if x in d:
            d[x] += 1
        else:
            d[x] = 1
    return d

Are there more concise ways of writing this function?

If we had dictionary comprehensions in Python, we could write:

>>> { x: L.count(x) for x in set(L) }

but since Python 2.6 doesn't have them, we have to write:

>>> dict([(x, L.count(x)) for x in set(L)])

Although this approach may be readable, it is not efficient: L is walked-through multiple times. Furthermore, this won't work for single-life generators; the function should work equally well for iterator generators such as:

def gen(L):
    for x in L:
        yield x

We might try to use the reduce function (R.I.P.):

>>> reduce(lambda d,x: dict(d, x=d.get(x,0)+1), L, {}) # wrong!

Oops, this does not work: the key name is 'x', not x. :(

I ended with:

>>> reduce(lambda d,x: dict(d.items() + [(x, d.get(x, 0)+1)]), L, {})

(In Python 3, we would have to write list(d.items()) instead of d.items(), but it's hypothethical, since there is no reduce there.)

Please beat me with a better, more readable one-liner! ;)

Solution 1

Python 3.x does have reduce, you just have to do a from functools import reduce. It also has "dict comprehensions", which have exactly the syntax in your example.

Python 2.7 and 3.x also have a Counter class which does exactly what you want:

from collections import Counter
cnt = Counter("abracadabra")

In Python 2.6 or earlier, I'd personally use a defaultdict and do it in 2 lines:

d = defaultdict(int)
for x in xs: d[x] += 1

That's clean, efficient, Pythonic, and much easier for most people to understand than anything involving reduce.

Solution 2

It's kinda cheaty to import modules for oneliners, so here's a oneliner that is O(n) and works at least as far back as Python2.4

>>> f=lambda s,d={}:([d.__setitem__(i,d.get(i,0)+1) for i in s],d)[-1]
>>> f("ABRACADABRA")
{'A': 5, 'R': 2, 'B': 2, 'C': 1, 'D': 1}

And if you think __ methods are hacky, you can always do this

>>> f=lambda s,d=lambda:0:vars(([setattr(d,i,getattr(d,i,0)+1) for i in s],d)[-1])
>>> f("ABRACADABRA")
{'A': 5, 'R': 2, 'B': 2, 'C': 1, 'D': 1}

:)

Solution 3

$d{$_} += 1 for split //, 'abracadabra';

Solution 4

import pandas as pd

pd.Series(list(L)).value_counts()

Solution 5

For python 2.7, you can use this small list comprehension:

v = list('abracadabra')
print {x: v.count(x) for x in set(v)}

View more solutions

Comments

[msw]

"one liner" and "more readable" aren't mutually exclusive, but they're close

[Peter Milley]

Not an answer, just some comments: First, dict((x, L.count(x)) for x in set(L)) works perfectly well (at least in 2.6 or so, possibly earlier versions too), so there's no need to introduce the extra list in your example above. Secondly, if you don't care about one-liners then this is a job tailor-made for defaultdict from the collections module. Replace d = {} with d = collections.defaultdict(int) in your original histogram function, and then you can skip the if x in d: bit.

[mykhal]

Peter Milley: yor almost dict comprehension works even in Python 2.5.2! thanks, i was not aware of this syntax

[Grant Paul]

Python 2.7 also has dict comprehensions.

[Mike Graham]

This solution is O(n log n). There are several simpler linear solutions provided here.

[PaulMcG]

@Mike - are you sure? Beware of lurking complexities. Iterating over the list is obviously O(n), but what is the complexity of the repeated looking up of each key in the summarizing dict? It's not O(1).

[Mike Graham]

Looking up dict keys is O(1).

[tokland]

This solution (without the sorted call, of course) is ok when your iterable is already sorted, otherwise it's too expensive, as Mike stated.

[Matti]

tokland, isn't dict.update() the same as what you mean by dict.merge()

[tokland]

@sblom: you've kill a functional cat ;-) dict.update() works in-place while dict.merge() wouldn't (check Ruby's Hash#merge, Hash#update). Even if we didn't care for purity, as dict.update() does not return the updated dict, it couldn't be used in a one-liner lambdas.

[RickyA]

Cool indeed, but I have to agree on @msw 's comment on readability. If I'd see someone push this to our repro I would have a serious discussion with him...

[BC.]

@perl I think you should take this novelty account further

[Ohumeronen]

I find this to be the most elegant solution. Nice!