python histogram one-liner [duplicate]

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! ;)

Specify

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

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. – Saipan

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

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

Automation

Python 2.7 also has dict comprehensions. – Dentition

What is the variable xs in "for x in xs" ? – Vitia

@RobyB: The "xs" variable in this example is a list. In many code examples, "x" is a single item and "xs" is a list or array - this convention comes originally from the Haskell programming language. – Automation

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

:)

Stirring

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

Answer 3

import pandas as pd

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

Nostrum

Answer 4

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

Nikaniki

@Nikaniki I think you should take this novelty account further – Anaplastic

Why did an answer written in an unrelated programming language with no explanation get 9 upvotes? – Hermelindahermeneutic

Answer 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)}

Spiniferous

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

Answer 6

One that works back to 2.3 (slightly shorter than Timmerman's, I think more readable) :

L = 'abracadabra'
hist = {}
for x in L: hist[x] = hist.pop(x,0) + 1
print hist
{'a': 5, 'r': 2, 'b': 2, 'c': 1, 'd': 1}

Duplicity

Answer 7

For a while there, anything using itertools was by definition Pythonic. Still, this is a bit on the opaque side:

>>> from itertools import groupby
>>> grouplen = lambda grp : sum(1 for i in grp)
>>> hist = dict((a[0], grouplen(a[1])) for a in groupby(sorted("ABRACADABRA")))
>>> print hist
{'A': 5, 'R': 2, 'C': 1, 'B': 2, 'D': 1}

I'm currently running Python 2.5.4.

Epaulet

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

@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). – Epaulet

Looking up dict keys is O(1). – Lactose

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

Answer 8

Your one-liner using reduce was almost ok, you only needed to tweak it a little bit:

>>> reduce(lambda d, x: dict(d, **{x: d.get(x, 0) + 1}), L, {})
{'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2}

Of course, this won't beat in-place solutions (nor in speed, nor in pythonicity), but in exchange you've got yourself a nice purely functional snippet. BTW, this would be somewhat prettier if Python had a method dict.merge().

Noella

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

@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. – Noella

Answer 9

I needed a histogram implementation to work in python 2.2 up to 2.7, and came up with this:

>>> L = 'abracadabra'
>>> hist = {}
>>> for x in L: hist[x] = hist.setdefault(x,0)+1
>>> print hist
{'a': 5, 'r': 2, 'b': 2, 'c': 1, 'd': 1}

I was inspired by Eli Courtwright's post of a defaultdict. These were introduced in python 2.5 so can't be used. But they can be emulated with the dict.setdefault(key,default).

This is basically the same thing gnibbler is doing, but I had to write this first before I could completely understand his lambda function.

Meander