Archive for the 'Python' Category

Essential Python Reading List

March 19, 2008

I just noticed the blog Word Aligned, which has lots of great python stuff there, among which I found the Essential Python Reading List. Word!

Pyglet graphics for Python

March 5, 2008

Always slow to jump on the bandwagons, so I’m just now discovering Pyglet, and OpenGL context for Python. I’ve mucked about many times with OpenGl applications using GLUT, Tk, or WxPython, and I know that it can be really difficult to compile and install the context and the code. Thus, I was pleasantly surprised when Pyglet compiled and installed in seconds, without problems or warnings.

The application that drew me to Pyglet was the game of life in pyglet program that I saw pop up on Reddit. It took me all of 10 minutes to download/install pyglet, and install/run the program.

Can’t say I’m a pyglet expert yet, but I like what I’ve seen thus far.

Python snippet to get list of words

February 20, 2008

Here are a quick little snippet to get a Python generator object of the words from the Unix wordfile:

def get_wordgen(fname="/usr/share/dict/words"):
    return (line.strip() for line in open(fname))

You can pass this through Set() if you need to do membership tests (in a simple spell check, for example), or even use list() if you need the whole thing in memory.

Scientific packages in Python I just discovered

February 20, 2008

I like to think that I’m abreast of the best of the scientific packages in Python, but I just discovered several cool packages today:

  • SymPy, a symbolic math package in Python, which actually is part of the Sage program that I like so much;
  •  sfepy, a finite element analysis package in Python (also symfe, for symbolic finite element analysis).

New in Python 3: Extended unpacking

February 18, 2008

Let me jump on the “me, too” bandwagon by echoing: This is really, really cool!

The Py Side of Life: New in Python 3: Extended unpacking

Testing whether a number is a square integer

February 13, 2008

In an earlier post I mention that I didn’t know of a good method to determine whether a number was an integer squared or not. I spent some time looking into this and here’s what I came up with.

The naive solution

squares = Set(i*i for i in xrange(1,BIG)); def is_square(n): return n in squares

doesn’t really work for large values of BIG, since it has to compute all of those elements.

Googling around led me to the beast that is the integer square root. The wikipedia page led me to the following page, which had the following Python implementation:

def isqrt(n):
    xn = 1
    xn1 = (xn + n/xn)/2
    while abs(xn1 - xn) > 1:
        xn = xn1
        xn1 = (xn + n/xn)/2
    while xn1*xn1 > n:
        xn1 -= 1
    return xn1

Thus one can simply use:

def is_square(n): return isqrt(n)**2 == n

Sweet.

D’oh moment from Project Euler

February 12, 2008

I don’t think that the caliber of my posts has necessarily been so high that people will be shocked by overt stupidity from me, but I just discovered some in myself, and stupidity is one of the things that is better shared.

One of the things I’ve had to do very often in Project Euler is figure out whether some long number is an integer or not. So I’ve defined the following function, that I’ve used over and over again:

def is_int(f): return int(f) == f

It actually works pretty well in any number of cases, until the floating point number f starts getting big. However, that doesn’t mean it should be used all of the time.

One place where I’ve used this function incorrectly is figuring out whether a square root is integral, for example, in looking for Pythagorean triplets. It’s much better to test whether a**2+b**2 is square, than whether sqrt(a**2+b**2) is integral. However, since for really huge numbers this requires generating a long list of square integers, I don’t feel too stupid about this. (Does anyone know of a clever way to test whether an integer is a square??)

What I do feel stupid about is in checking whether a rational fraction is integral. I caught myself doing this:

is_int(a/float(b))

which is staggeringly stupid. I was flipping through some of the forum solutions to Project Euler, and noticed one of the Pythonistas was using the much more intelligent

a % b == 0

One of those things that seems stunningly obvious once you see it, but, for whatever reason, I didn’t see it. (Hangs head in shame.)

Thoughts on Pascal’s triangle in Python

February 11, 2008

For a Project Euler problem I had to work on a generator for Pascal’s Triangle. Ultimately, it didn’t emerge as the right way to solve the problem, but I arrived at an interesting implementation that I’d like to share.

The naive implementation is:

def gen_pascal():
    last = []
    while True:
        n = len(last)
        row = [1]*(n+1)
        for i in range(1,n):
            row[i] = last[i-1]+last[i]
        last = row
        yield row
    return

This is pretty similar to any number of implementations you can find on the web. Works quite nicely, too, except it requires 2*n storage, which gets big if you’re interested in really large triangles.So I started thinking about automatic ways of generating only a row at a time, and yielding an iterator for that row rather than a list, to reduce the memory usage. Again, the obvious way to generate the elements are:

def fact(n):
    if n <= 0: return 1
    return prod(xrange(1,n+1))def combos(n,m): return fact(n)/fact(n-m)/fact(m)

def combos_slower(n,m):
    if m == 0 or n == m: return 1
    return combos(n-1,m-1)+combos(n-1,m)

def gen_pascal_row(n):
    for r in range(0,n+1):
        yield combos(n,r)
    return

So this version doesn’t use any memory, but actually takes a great deal of computation (roughly N^3??) per new element, which seems a bit wasteful, and starts to bog down even sooner than the naive version.

I played around with an alternate way to generate the combinations, in part inspired by the naive version:

 def combos_slower(n,m):
    if m == 0 or n == m: return 1
    return combos(n-1,m-1)+combos(n-1,m)

but, as the name implies, it was even slower still.

Ultimately I settled on this version:

def gen_pascal_row_fast(n):
    el = 1
    yield el
    for m in range(1,n+1):
        el = (el*(n-m+1))/m
        yield el
    return

which only takes 4 operations to make a new element, and no memory, which I think is pretty cool. Of course, I don’t kid myself that I’m the first one to think of this, but I still wanted to share it, especially since, as it turns out, I can’t use it for the problem I’m trying to solve in Project Euler.

Sage: great free mathematics software

February 1, 2008

Sage is an open source effort to replace the commercial math codes like Mathematica, Matlab, Magma with a free product of equal quality. It uses Python, my favorite language, as the glue that holds together a variety of existing open source math programs (Pari, Maxima, Numpy, Scipy, Blas, Lapack, etc.).

Such a product is a real revelation to me. I rarely have need for a symbolic math program, so that even though I have access to Maxima and Mathematica, I use them rarely enough so that when I do need them, I’ve completely forgotten the required syntax. But when I need the program, I really need it, which requires a long slog through the documentation. However, I use Python almost every minute of every day. But Python has its problems as well. Getting users to install all the various widgets required to run one of the pieces of software I write is itself very time consuming. Sage has solved all of this, as far as I can tell, by simply distributing all of the source code with the program. This makes for a rather time consuming build procedure, but one that worked for me the first time I tried it.

I’ve already mentioned how much I love Project Euler, and it’s gratifying to see Python making such a respectable showing on the statistics page there. However, I found that my versions of some very critical programs, like testing whether a number is prime, or computing the number of integer partitions, were enough slower than fast implementations, that my programs often took much longer than those written in Mathematica, for example. Sage solves all of these problems for me quite ably, and lets me use Python to write the code that drives the functions.

The graphics are worth noting as well. Sage has integrated the best Python plotting package (matplotlib) into a Firefox-driven duplicate of the Mathematica notebook into something that is both simple to use and elegant. They even have a free web portal for the program, where you can sign up for a free account and try things out.

Very slick and very, very well done. In all seriousness, I haven’t been this excited since I discovered Python for the first time.

End Links:

You Used Perl to Write WHAT?!

January 27, 2008

Nice article entitled You Used Perl to Write WHAT?! Most of the pros/cons apply to Python as well. Python programmers like to feel all superior to their Perl counterparts, but knowing when not to use a language is as important as knowing how to use a language. IMO, the ease of using Pyrex to write a C extension, or the maturity of packages like numpy remove some of the limitations to high performance computing. And I think that CGI and web.py make the web a perfectly valid place for Python to play.