I found both python and map/reduce conspicuously missing in the recent discussion at ongoing about Wide Finder log parsing in Erlang. I have been very short of time, and thus I have been limited to read the discussion. But today I got a bit of time. Wanting to get into first principles first, and given that I don’t find Ruby particularly easy to read, I decided to rewrite it in python in “map/reduce” style:
import re
from collections import defaultdict
matches = (re.search(r"GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) ",line)
for line in file("o10k.ap"))
mapp = (match.groups()[0] for match in matches if match)
count=defaultdict(int)
for page in mapp:
count[page] +=1
for key in sorted(count.keys(), key=count.get):
print "%40s = %s" % (key, count[key])
The program uses the data file that Tim Bray published, and tries to be as declarative as possible. It requires python 2.5 due to the use of collections.defaultdict. The first two comprehensions “map” the file, i.e., the first one maps the file into an iterator that yields either a match or None, and the second one filters the stream of matches, removing the nulls, and retrieves the group.
After this, we need to reduce. I have not (yet) found a declarative way to reduce the stream, but a short loop does its job. The use of defaultdict(int) is a nice technique to get a map that will default to 0 but it is easy to read.
This code is one line shorter than the ruby example that Tim Bray shows and, barring the ugly python syntax for regular expressions, I tend to find it more elegant than the original. Note that it will handle easity the quarter Gig file, as the file iterator reads one line at a time, and the rest of the processing takes place one line at a time. It will start barking when the number of entries (and thus the dictionary) becomes really big.
I’ll try to keep constructing, bottom up, the code for the problem, and discussing the trade offs and gotchas, as time permits. But I thought that leaving here this short snippet while I can find time is better than let it rot in my Tomboy notes. :)
I wrote a comment on Tim’s blog about using MapReduce for the Wide Finder project. BTW I like the way you use the MapReduce idiom to write a regular python program.
Cheers,
Tom
Welcome, Tom.
The typical use case for Erlang (or for Hadoop, as you pointed) would be more like “do what Tim says in 500 machines and aggregate the results”. I skimmed on your comment, now I went to the real paper. When I said missing I meant mostly Tim, and it was before his fifth post appeared.
The funny thing about the code is I was going to use the classic map and reduce functions, but I remembered that reduce is doomed, and reading Guido’s post I found:
filter(P, S) is almost always written clearer as [x for x in S if P(x)], and this has the huge advantage that the most common usages involve predicates that are comparisons, e.g. x==42, and defining a lambda for that just requires much more effort for the reader (plus the lambda is slower than the list comprehension). Even more so for map(F, S) which becomes [F(x) for x in S].
As an added benefit, the code is much more similar to Erlang’s comprehensions. Actually using [] will make them in-memory lists, but using () will turn them into generators.
defaultdict as seen in the wild is almost always just a “bag”, a set-like object that allows objects to be in it multiple times. Using that structure would make the code a bit shorter. I threw together a little bag implementation: [link]
You should be able to do:
b = Bag(map_lines(file))
for count, page in b.mostcommon():
print ‘%40s=%s’ % (page, count)
This will probably slow the code down, but if Bag was written in C like defaultdict it wouldn’t.
defaultdict as seen in the wild is almost always just a “bag”, a set-like object that allows objects to be in it multiple times.
I remember the Bag from my old days as a Smalltalk programmer (Digitalk under MS-DOS, man I feel old) and I have always wondered why supposedly rich collection frameworks like the ones in java and python don’t have it. It is exactly what is needed for the reduce task here: counting.
Here I did what the original code was doing and what your code and Smalltalk uses as the implementation of Bag: use a dictionary to store the counts.
I even hesitated to use defaultdict to keep 2.5- compatibility, but now that major linux distros are moving to 2.5 I guess it is mainstream enough.
I have an obvious bug (that I have not yet fixed, but it is identified), in the routine that checks the logs for referrers. Plus a power supply burned tonight. The power supply has been replaced, but in the process of cleaning the entries I erased accidentally, and google’s cache is too old, the one proposing a short version by using a try: except: pass idiom to avoid having to check for matches vs. None. Please, do you have the code? I read it fast and can’t remember the name/URL.
In a sense,
def Filter(Iterator):
while Something in Iterator:
try: yield UnsafeOp(Something)
except: pass
is a useful filter in the chain. Not unlike the regex one (yield all matches...)
This is what I found to be fastest, beating Ruby by a full second on my test data; actually a list comprehension was slightly faster but at increased resource use. Oddly, ruby is penalized for using F.L.'s filter optimization - almost twice as slow.
counts = defaultdict(int) for match in (res.group(1) for res in (ongoing_re.search(line) for line in open(sys.argv[1]) if "GET /ongoing/When" in line) if res): counts[match] +=1
Here are the optimizations I would make:
(1) Initialize the regexp (as others have said)
r = re.compile(r"GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+) ")
(2) Filter out data that can’t match
matches = (r.search(line) for line in file("o10k.ap") if line.startswith("GET /ongoing/When/"))
(3) Add psyco
import psyco
psyco.full()