PythonWise

If it won't be simple, it simply won't be. [Hire me, source code] by Miki Tebeka, CEO, 353Solutions

Wednesday, April 22, 2009

Solving Euler Question 24

I'm learning Clojure by solving project Euler. Here is a python version of one of the solutions.

`#!/usr/bin/env python''' Solving http://projecteuler.net/index.php?section=problems&id=24Note that Python's 2.6 itertools.permutations return the permutation in order sowe can just write:    from itertools import islice, permutations    print islice(permutations(range(10)), 999999, None).next()And it'll work much faster :)'''from itertools import islice, ifilterdef is_last_permutation(n):    return n == sorted(n, reverse=1)def next_head(n):    '''Find next number to be 'head'.     It is smallest number if the tail that is bigger than the head.    In the case of (2 4 3 1) it will pick 3 to get the next permutation    of (3 1 2 4)    '''    return sorted(filter(lambda i: i > n[0], n[1:]))[0]def remove(element, items):    return filter(lambda i: i != element, items)def next_permutation(n):    if is_last_permutation(n):        return None    sub = next_permutation(n[1:])    if sub:        return [n[0]] + sub    head = next_head(n)    return [head] + sorted([n[0]] + remove(head, n[1:]))def nth(it, n):    '''Return the n'th element of an iterator'''    return islice(it, n, None).next()def iterate(func, n):    '''iterate(func, n) -> n, func(n), func(func(n)) ...'''    while 1:        yield n        n = func(n)def permutations(n):    return ifilter(None, iterate(next_permutation, n))if __name__ == "__main__":    n = range(10)    m = 1000000    print "Calculateing the %d permutation of %s" % (m, n)    print nth(permutations(n), m-1)`

Friday, April 03, 2009

pmap

`#!/usr/bin/env python'''Parallel map (Unix only)'''__author__ = "Miki Tebeka <miki.tebeka@gmail.com>"# The big advantage of this implementation is that "fork" is very fast on# copying data, so if you pass big arrays as arguments and return small values# this is a win# FIXME # * For too many items, we get "Too many open files"# * Handle child exceptionsfrom os import fork, pipe, fdopen, waitpid, P_WAITfrom marshal import dump, loadfrom itertools import takewhile, countdef spawn(func, data):    read_fo, write_fo = map(fdopen, pipe(), ("rb", "wb"))    pid = fork()    if pid: # Parent        return pid, read_fo    # Child    dump(func(data), write_fo)    write_fo.close()    raise SystemExitdef wait(child):    pid, fo = child    waitpid(pid, P_WAIT)    value = load(fo)    fo.close()    return valuedef pmap(func, items):    '''    >>> pmap(lambda x: x * 2, range(5))    [0, 2, 4, 6, 8]    '''    children = map(lambda item: spawn(func, item), items)    return map(wait, children)if __name__ == "__main__":    def fib(n):        a, b = 1, 1        while n > 1:            a, b = b, a + b            n -= 1        return b    items = range(10)    print "pmap(fib, %s)" % str(items)    print pmap(fib, items)`