How to compute letter frequency in a string using pythons built-in map and reduce functions

Question

I would like to compute the frequency of letters in a string using pythons map and reduce built-in functions. Could anyone offer some insight into how I might do this?

What I've got so far:

s = "the quick brown fox jumped over the lazy dog"

# Map function
m = lambda x: (x,1)

# Reduce
# Add the two frequencies if they are the same
# else.... Not sure how to put both back in the list
# in the case where they are not the same.
r = lambda x,y: (x[0], x[1] + y[1]) if x[0] == y[0] else ????

freq = reduce(r, map(m, s))

This works great when all the letters are the same.

>>> s
'aaaaaaa'
>>> map(m, s)
[('a', 1), ('a', 1), ('a', 1), ('a', 1), ('a', 1), ('a', 1), ('a', 1)]
>>> reduce(r, map(m, s))
('a', 7)

How do I get it to work nicely when there are different letters?

Answer 1

Sidestepping for a moment the question about your code, I will point out that one of the usual (and fastest) ways to count things is with the Counter class from the collections module. Here is an example of its use, in the Python 2.7.3 interpreter:

>>> from collections import Counter
>>> lets=Counter('aaaaabadfasdfasdfafsdff')
>>> lets
Counter({'a': 9, 'f': 6, 'd': 4, 's': 3, 'b': 1})
>>> s = "the quick brown fox jumped over the lazy dog"
>>> Counter(s)
Counter({' ': 8, 'e': 4, 'o': 4, 'd': 2, 'h': 2, 'r': 2, 'u': 2, 't': 2, 'a': 1, 'c': 1, 'b': 1, 'g': 1, 'f': 1, 'i': 1, 'k': 1, 'j': 1, 'm': 1, 'l': 1, 'n': 1, 'q': 1, 'p': 1, 'w': 1, 'v': 1, 'y': 1, 'x': 1, 'z': 1})

To use reduce, define an auxiliary function addto(oldtotal,newitem) that adds newitem to oldtotal and returns a new total. The initializer for the total is an empty dictionary, {}. Here is an interpreted example. Note that the second parameter to get() is a default value to use when the key is not yet in the dictionary.

 >>> def addto(d,x):
...     d[x] = d.get(x,0) + 1
...     return d
... 
>>> reduce (addto, s, {})
{' ': 8, 'a': 1, 'c': 1, 'b': 1, 'e': 4, 'd': 2, 'g': 1, 'f': 1, 'i': 1, 'h': 2, 'k': 1, 'j': 1, 'm': 1, 'l': 1, 'o': 4, 'n': 1, 'q': 1, 'p': 1, 'r': 2, 'u': 2, 't': 2, 'w': 1, 'v': 1, 'y': 1, 'x': 1, 'z': 1}

The code shown below prints the execution times for 1000 passes each of several methods. When executed on an old AMD Athlon 5000+ Linux 3.2.0-32 Ubuntu 12 system with two different strings s it printed:

String length is 44   Pass count is 1000
horsch1 : 0.77517914772
horsch2 : 0.778718948364
jreduce : 0.0403778553009
jcounter: 0.0699260234833
String length is 4931   Pass count is 100
horsch1 : 8.25176692009
horsch2 : 8.14318394661
jreduce : 0.260674953461
jcounter: 0.282369852066

(The reduce method ran slightly faster than the Counter method.) The timing code follows. It uses the timeit module. In the code as here, the first parameter to timeit.Timer is code to be repeatedly timed, and the second parameter is setup code.

import timeit
from collections import Counter
passes = 1000

m1 = lambda x: [int(ord(x) == i) for i in xrange(65,91)]

def m2(x):
    return [int(ord(x) == i) for i in xrange(65,91)]

def es1(s):
    add = lambda x,y: [x[i]+y[i] for i in xrange(len(x))]
    freq = reduce(add,map(m1, s.upper()))
    return freq

def es2(s):
    add = lambda x,y: [x[i]+y[i] for i in xrange(len(x))]
    freq = reduce(add,map(m2, s.upper()))
    return freq

def addto(d,x):
    d[x] = d.get(x,0) + 1
    return d

def jwc(s):
    return Counter(s)

def jwr(s):
    return reduce (addto, s, {})

s = "the quick brown fox jumped over the lazy dog"
print 'String length is',len(s), '  Pass count is',passes
print "horsch1 :",timeit.Timer('f(s)', 'from __main__ import s, m1,     es1 as f').timeit(passes)
print "horsch2 :",timeit.Timer('f(s)', 'from __main__ import s, m2,     es2 as f').timeit(passes)
print "jreduce :",timeit.Timer('f(s)', 'from __main__ import s, addto,  jwr as f').timeit(passes)
print "jcounter:",timeit.Timer('f(s)', 'from __main__ import s, Counter,jwc as f').timeit(passes)