Twibet: a recursive solution in Ptyhon

Today a friend told me she's struggling with solving the EuroPython 2011 Problem D, called Twibet. I wrote a quick solution and I'm publishing it here for those who are curious about it.
The key to my solution was the recursive traversal (traverse_graph) of a directed graph. The representation of the graph is a dictionary of the monks as keys and a list of the following monks as values.
Because running on the large input file raised a runtime error of  maximum recursion depth exceeded, I used a this little hack: sys.setrecursionlimit(10000).
UPDATE: Here are the solutions of the contestants.

	'''
	this is a solution of the EuroPython 2011 Problem D. Twibet
	http://code.google.com/codejam/contest/dashboard?c=1277486#s=p3
	'''
	def build_graph(input_list):
	di = {}
	for i in range(1, len(input_list)+1):
	di[i] = []
	for monk, followed_monk in enumerate(input_list, start=1):
	di[followed_monk].append(monk)
	return di
	def traverse_graph(graph, start, monks_today):
	monks_today.add(start)
	result = 1
	result += sum(map(lambda monk: traverse_graph(graph, monk, monks_today), \
	filter(lambda monk : monk not in monks_today, graph[start])))
	return result
	def solve_case(case_no, line):
	print "Case #%i:" % case_no
	input_list = map(int, line.split())
	for monk in range(1, len(input_list)+1):
	print traverse_graph(build_graph(input_list), monk, set())
	def main():
	import sys
	sys.setrecursionlimit(10000)
	lines = sys.stdin.readlines()
	for case_no, line in enumerate(lines[2::2], start=1):
	solve_case(case_no, line.strip())
	main()

view raw twibet.py hosted with ❤ by GitHub

Concurrent matrix multiplication in Python

We're going to demonstrate parallel matrix multiplication in Python.

Lets suppose we are performing the multiplication: P = A * B. We're going to calculate the result matrix row-by-row. The following function returns a row of a result matrix P. The arguments are a row of matrix A and the matrix B.

def calc_row_of_product_matrix(a_row, b):
    return map(lambda col: sum(starmap(mul,izip(a_row,col))), izip(*b))


We're going to use the multiprocessing module of Python to create a process pool containing as many processes as the number of CPUs we have and calculate each result row in a different process. Here are the two lines that does this trick:

def __mul__(self, b):
    pool = multiprocessing.Pool(multiprocessing.cpu_count())
    return pool.map(eval_func_tuple, izip(repeat(calc_row_of_product_matrix), self, repeat(b)))


Some explanation why is this code a bit nasty. Functions passed to the pool has to be picklable and because only the functions defined at the top level of a module are picklable, we needed to get the the row calculation function calc_row_of_product_matrix out of the class. Furthermore, to be able to pass two arguments to calc_row_of_product_matrix we also needed a helper function, which takes a tuple of a function and args, evaluates and returns the result:

def eval_func_tuple(f_args):
    return f_args[0](*f_args[1:])


Note that passing around the whole matrix B to all processes calculating result rows, or more precisely passing itertools.repeat(b) to  pool.map() visibly increases the memory consumption of the multiprocess version. This was not a real issue for me, as the bottleneck was CPU; anyway, this issue could be addressed by using the shared memory module of multiprocessing. For now we'll leave that as an exercise to the reader.

Here are the running times on my Intel Core2 Duo 3.16GHz box. For sufficiently large matrix (above 500*500) the running time of the multiprocess version is nearly half of the single process version.


100*100 matrix, single process: 0.0835670982343 
100*100 matrix, multiprocess: 0.351096555199 
200*200 matrix, single process: 0.79961114284 
200*200 matrix, multiprocess: 0.700980680681 
500*500 matrix, single process: 14.4003259234 
500*500 matrix, multiprocess: 7.99582457187 
1000*1000 matrix, single process: 118.078526896 
1000*1000 matrix, multiprocess: 66.8809939919 

Here you can see the single process version running with CPU usage of 50%:

Here you can see  the multiprocessing version running with CPU usage of 100%:

Here's the full code:

	import random
	import multiprocessing
	from itertools import starmap, izip, repeat, imap
	from operator import mul
	def calc_row_of_product_matrix(a_row, b, izip=izip):
	'''Calculate a row of the product matrix P = A * B
	Arguments:
	a_row is af A
	b is the B matrix
	returns the corresponding row of P matrix'''
	return map(lambda col: sum(starmap(mul,izip(a_row,col))), izip(*b))
	def eval_func_tuple(f_args):
	'''Takes a tuple of a function and args, evaluates and returns result'''
	return f_args[0](*f_args[1:])
	class multimatrix(list):
	def __mul__(self, b, izip=izip, repeat=repeat):
	'''Concurrent matrix multiplication with multiprocessing.Pool. '''
	pool = multiprocessing.Pool(multiprocessing.cpu_count())
	return pool.map(eval_func_tuple, izip(repeat(calc_row_of_product_matrix), self, repeat(b)))
	class itermatrix(list):
	@staticmethod
	def sumprod(row, col, sum=sum, starmap=starmap, mul=mul):
	'''Returns sumproduct of two vectors.'''
	return sum(starmap(mul,izip(row,col)))
	def __mul__(self, b, imap=imap, izip=izip):
	'''Matrix multiplication returning iterable of iterables'''
	return imap(lambda row: imap(lambda col: itermatrix.sumprod(row, col), izip(*b)), self)
	def iterate_results(result):
	'''Iterate over iterable of iterables,
	and returns elements in list of lists.
	Usage: if you want to run the whole calculation at once:
	p = iterate_results(itermatrix([[1, 3], [-5, 6], [2, 4]]) * itermatrix([[1, 4], [8, 7]]))'''
	return[[col for col in row] for row in result]
	def random_v(K=1000,min=-1000,max=1000):
	'''Generates a random vector of dimension N;
	Returns a list of integers.
	The values are integers in the range [min,max].'''
	return [random.randint(min,max) for k in range(K)]
	def random_m(N=1000, K=1000):
	'''Generates random matrix. Returns list of list of integers.'''
	return [random_v(K) for n in range(N)]

view raw matrix.py hosted with ❤ by GitHub

	from matrix import multimatrix, itermatrix, random_m, iterate_results
	import matrix
	import timeit
	if __name__ == '__main__':
	a = [[1, 3], [-5, 6], [2, 4]]
	b = [[1, 4], [8, 7]]
	adotb = [[25, 25], [43, 22], [34, 36]]
	A = multimatrix(a)
	B = multimatrix(b)
	prod = A * B
	assert(adotb == prod)
	print prod, "multi test OK"
	A = itermatrix(a)
	B = itermatrix(b)
	iterprod = A * B
	listprod = iterate_results(iterprod)
	assert(adotb == listprod)
	print listprod, "iter test OK"
	t = timeit.Timer("p = itermatrix(a) * itermatrix(a)", "from matrix import itermatrix, random_m; a = random_m(500, 500)")
	print "iterable product time:", t.timeit(number=1)
	t = timeit.Timer("p = itermatrix(a) * itermatrix(a); iterate_results(p)", "from matrix import itermatrix, random_m, iterate_results; a = random_m(500, 500)")
	print "list product time:", t.timeit(number=1)
	t = timeit.Timer("p = multimatrix(a) * multimatrix(a)", "from matrix import multimatrix, random_m, iterate_results; a = random_m(500, 500)")
	print "multi product time:", t.timeit(number=1)

view raw test.py hosted with ❤ by GitHub

Ngrams with coroutines in Python

This is how I define ngrams with coroutines

	def coroutine(func):
	""" A decorator function that takes care
	of starting a coroutine automatically on call """
	def start(*args,**kwargs):
	coro = func(*args,**kwargs)
	coro.next()
	return coro
	return start
	@coroutine
	def ngrams(n, target):
	""" A coroutine to generate ngrams.
	Accepts one char at a time """
	chars = collections.deque()
	while True:
	chars.append((yield))
	if len(chars) == n:
	target.send(chars)
	chars.popleft()

view raw gistfile1.py hosted with ❤ by GitHub

I need to filter text before generating ngrams and also, I want to process ngrams (in this case count bigrams)

	@coroutine
	def filter_chars(accepted_chars,target):
	""" A coroutine to filter out unaccepted chars.
	Accepts one char at a time """
	while True:
	c = (yield)
	if c.lower() in accepted_chars:
	target.send(c.lower())
	@coroutine
	def counter(matrix):
	""" A counter sink """
	while True:
	a, b = (yield)
	matrix[pos[a]][pos[b]] += 1

view raw gistfile1.py hosted with ❤ by GitHub

I combine my coroutines together

	counts = [[10 for i in xrange(k)] for i in xrange(k)]
	bigrams = filter_chars(accepted_chars, ngrams(2, counter(counts)))
	for c in open('big.txt').read().decode(enc): bigrams.send(c)

view raw gistfile1.py hosted with ❤ by GitHub

Full source can be found in my fork of rrenaud's gibberish detector.

stackverflow: the most upvoted Q/A tagged as Perl vs as Python

The most upvoted question tagged as Perl
The most upvoted question tagged as Python

Currently, for Python, it is the hidden gems in the language.
You just cannot upvote some of them enough.

On the other side, the most upvoted Perl question at this moment is about Unicode oddities. And the most upvoted answer will scare the shit out of you.

Start programming, learn Python

Recently I've been asked to send a few links to absolute beginners who want to start programming. As a language choice, I always recommend to start with Python. So I ended up to collect a list useful links for Python beginners:


Tutorials

• Learn python the hard way by Zed Shaw - (mostly recommended) http://learnpythonthehardway.org/
• How to think like a computer scientist by Allen B. Downey - (mostly recommended) http://greenteapress.com/thinkpython/
• Dive into Python - (this is recommended by many sources, but the previous two are preferred) http://www.diveintopython.net/
• Python intro class at Google - (this may be too advanced for absolute beginners) http://code.google.com/edu/languages/google-python-class/index.html

Ask for help

• Stackoverflow http://stackoverflow.com/questions/tagged/python
• Reddit, the Python subreddits http://www.reddit.com/r/python, http://www.reddit.com/r/learnpython

Official tutorials 

• Getting started http://www.python.org/about/gettingstarted/
• Begginers guide http://wiki.python.org/moin/BeginnersGuide
• Official tutorial - (this may be too advanced for absolute beginners) http://docs.python.org/tutorial/
• Official list of introductory books http://wiki.python.org/moin/IntroductoryBooks

Read some code
Students need to read real code but it is hard to find production code that is readable for novices.

• Various problems solved: http://en.literateprograms.org/Category:Programming_language:Python
• Peter Norvig's Python codes e.g.: spelling corrector, sudoku
• Chris Meyers, intermediate examples  http://openbookproject.net/py4fun/index.html

Practice, write code

• http://www.pyschools.com/
• http://codingbat.com/ 

Hunglish 2.0

Hunglish 2.0

Recently Daniel Varga and me have been working hard in our free-time on the Hunglish project and reached a milestone: the whole system around the sentence aligner have been streamlined and/or rewritten. Also it has been deployed onto a test machine and now can be tried by anyone. This new system is going to replace the old one soon, hence any feedback are highly appreciated.


New features

• Help us build a bigger corpus

You can upload a pair documents (one in English, the other one in Hungarian). The uploaded documents will appear in the search results in a few minutes.

• Duplicate filtering

Duplicate results were a problem in the previous version. We have tried to filter them out in the new Hunglish.

• Extended corpus

The original sentence database contained 2 million sentence pairs, which has been nearly doubled.

Planned features 

• Upvote / downvote

This is only implemented in the back-end, but we plan to add it to the user-interface.

• Other language pairs

We also plan to add other language pairs. You can make a suggestion for a new language pair, bonus points if you recommend a decent open source stemmer (preferably implemented in Java) for new languages.

• Your suggestion

Feel free to suggest a new feature!

So we're encouraging you guys to give it a try! Upload documents and search the new Hunglish corpus.
You will be considered a hero if you find and report a bug on the project page.

Politicans, please thermalize!

Inspired by an UP rant and this photo.