Ceasar's Mind

Follow me: @Ceasar_Bautista

Posts Tagged ‘python

How to use default arguments with namedtuple

with 8 comments

I was running into some trouble earlier today trying to figure out how to use default argument with namedtuple.

According to the docs:

Default values can be implemented by using _replace() to customize a prototype instance:

>>> Account = namedtuple('Account', 'owner balance transaction_count')
>>> default_account = Account('<owner name>', 0.0, 0)
>>> johns_account = default_account._replace(owner='John')

This is of course not really what I was looking for.

Searching around some more led to the Python mailing list where a software engineer by the name of Issac Morland suggests exactly what I was looking for.

2. It would be nice to be able to have default values for named tuple fields.
Using Signature it’s easy to do this – I just specify a dictionary of defaults
at named tuple class creation time.

To which Raymond Hettinger (the creator of collections) responds:

This came-up before, but I’ll take another look at it this weekend. If it
significantly complicates the API or impacts performance, then it is a
non-starter; otherwise, I’ll put together an implementation and float it on
ASPN for comments.

And the trail ends. Not sure what the full story is.

In any case, the solution is fairly simple. Just subclass the result of namedtuple and override __new__ as follows:

from collections import namedtuple
class Move(namedtuple('Move', 'piece start to captured promotion')):
    def __new__(cls, piece, start, to, captured=None, promotion=None):
        # add default values
        return super(Move, cls).__new__(cls, piece, start, to, captured, promotion)

As you’ll notice, super is being used a little weird here, with cls being passed to both super and __new__. I’m not quite sure why that’s neccessary, but I can say I’ve tested it and it does work.

EDIT: It appears this question on SO explains the weirdness with using super together with __new__. tldr; __new__ is a static method, not a class method, so it requires an explicit passing of cls.

Written by Ceasar Bautista

2012/03/19 at 15:30

Posted in Uncategorized

Tagged with

Recursive Python Considered Harmful

with 11 comments

It somewhat recently occurred to me that recursion, despite it cleanliness, improves readability at a significant cost in memory. By piling on the stack trace, at best we get a function that uses O(n) memory, and quite possibly even one that is even worse. Given that any recursive function can be written using a while loop with O(1) memory bounds, recursion seems quite a poor choice for all practical purposes.

I brought this up at work and Alexey explained that while this is true, many (particularly, functional) compilers are intelligent enough to optimize the code for you if you use tail-recursion. Being unaware of the concept, I looked up how to convert a regular recursive function into a tail-recursive function and discovered I was wasting my time since Guido has decided not to implement tail-recursion in Python.

This begs the question then, is recursion ever useful in Python or should we go back to our code and start writing those while loops?

As I see it, there is only one reason to use recursion in Python and that is when you plan to memoize your function (which makes the function take up O(n) memory anyway). (Additionally, it may be helpful to write functions out as recursive functions in order to assist in proving things, but I think, again, the function would almost certainly need to be memoized or transformed.)

In all other cases, I believe while loops are the way to go. Besides the obvious problems with memory, there are a few other points worth mentioning.

For one, Python caps the stack height at 1000. While for some functions this may be okay, if you have any interest in scaling, this limit is way too small.

Additionally, function call overhead is Python is extremely slow. (Source: the official Python wiki.)

Anyway, that’s my two cents.

Written by Ceasar Bautista

2011/10/23 at 00:51

Posted in Uncategorized

Tagged with ,

Python Tips

leave a comment »

The “with” statement

This is just incredibly beautiful code.

Check out the source for more details on Python’s “with” statement if you’re interested.

Get current directory

Too useful not to know.  Source is here.

max and min accept a sorting function

Instead of writing out this:

def best(candidates, scoref):
    '''Use scoref to find the candidate with the highest score.'''
    highest_score = float('-inf')
    best = None
    for candidate in candidates:
	candidate_score = scoref(candidate)
        if candidate_score &gt; highest_score:
            highest_score = candidate_score
            best = candidate
    return best

You can just write:

max(iterable, key=scoref)

Don’t forget the “key” keyword, or Python will think you are comparing the list against the function. This is pretty cool because it makes things like getting the max value in a dictionary trivial.

>>> a = {'a': 1, 'b':2, 'c':3}
>>> a
{'a': 1, 'c': 3, 'b': 2}
>>> max(a, key=lambda x: a[x])

Written by Ceasar Bautista

2011/08/02 at 22:26

Posted in Uncategorized

Tagged with ,

Prime Generator

with 2 comments

Inspired by the last post, just thought this was too cool not to share. The function generates primes!

def prime_gen():
    '''Generate primes.'''
    offset = 2
    index = offset
    sieve = range(offset, offset ** 2)
    found = []
    while 1:
        start = index ** 2
        end = (index + 1) ** 2
        sieve.extend(range(start, end))

        num = sieve[index - offset]
        if num:
            sieve = sieve[index - offset:]
            offset = num
            yield num

        i = 0
        while i &lt; len(found):
            curr = found[i]
            j = start / curr * curr
            while j &lt; len(sieve) + offset:
                sieve[j - offset] = 0
                j += curr
            i += 1
        index += 1</pre>

Written by Ceasar Bautista

2011/07/10 at 03:57

Posted in Uncategorized

Tagged with , ,

The Quadratic Sieve

with 3 comments

Just got done with a terrible day of magic numbers. To spare everyone the trouble, here’s a fairly clear version of a quadratic sieve for generating prime numbers that ought to be self-explanatory and easily modified– as opposed to many other algorithms out there.

def primes(n):
    '''Get all primes up to n.'''
    n = int(n)
    if n < 2:
        return []
    sieve = range(n)
    sieve[1] = 0
    root = n ** 0.5
    index = 0
    while index <= root:
        if sieve[index]:
            i = index ** 2
            while i &lt; n:
                sieve[i] = 0
                i += index
        index += 1
    return [x for x in sieve if x]

Written by Ceasar Bautista

2011/07/10 at 02:49

Posted in Uncategorized

Tagged with , ,