Algorithm Blogs

After reading my last post regarding __del__, you should know that __del__ + reference cycle = leak.
Let's say that you do need to use __del__, so you decide to avoid reference cycles. You write your code in such a way as to use the minimum necessary cycles, and for the ones that remain you use the weakref module.

You might still have cycles where you don't expect it - in references to methods.
Consider the following piece of code. Can you spot the reference cycle?

This code has the following reference cycle: a -> a.g -> a.f -> a.
How come?
When you call a.f like so: "a.f()" two things happen:
1. A.f is bounded to a
2. The bounded A.f is called with the first parameter getting the bounded value.

You may consider that "a.f" is syntactic sugar for the partial function application, A.f gets a as a first argument but doesn't get called yet.

When you use "a.g = a.f" what actually happens is a holding a reference to a bounded method, which holds a reference to a.

An idiom that uses these cycles is implementing state machines. Consider the following example code:

Of course, my code was a bit more complicated than that, but the basic idea remains. (My code usually created some kind of function table in __init__ used to lookup the next function, and lookups happened outside "state functions"). I've seen many state machine recipes include method references - and rightly so. It's a clear and easy way to code a state machine. (For example, this state machine recipe).
Be careful though - once you add __del__ to these simple recipes you might end up with a memory leak.

Short note: I was going to publish this post a few days ago, but kylev beat me to it. This just goes to show that other people encountered this kind of cycle.

A few days ago, I discovered I had at least one, maybe two mathematical bugs. The first bug is in the line clipping algorithm. Here's a quick reminder of what's going on there:

There are six points of interest: the four intersection points, and the two endpoints of the line. We sort the six points according to their parameter, and take the two innermost points as the endpoints of the clipped line. To check if the line is outside the box we make sure that the result points' parameters are between 0 and 1 (which correspond to the original endpoints).

Turns out this is not always true - here's a counter example:

In the counter example you can see a line, whose endpoints lie between the intersections. The algorithm described above will say this line lies completely inside the box. Clearly this is not true. How do we fix this? Simple actually. We check for each intersection point whether or not it is on the edges of the clipping rectangle. If at most one point is on - our line is outside. I hope this is the end of it. It will require more rigorous testing.

The second bug was in my solution to the random selection challenge. I wasn't too sure of my solution, but I really liked it, as its code is rather elegant. So when meeting someone I used to work with, I told her about it. After thinking about my solution a bit, she said it is probably wrong, and gave me the reason: While the probability of a point x passing the first stage is indeed (proportional to) p(x), the probability of it passing the second stage is not 1 (or constant). I still need to think about this one, so no easy fix yet. I guess this reopens the challenge, so if anyone feels like writing a good proof or a counter example for my solution, I'd be happy to see it. I'll be even happier to see a completely different solution.

While working with Python, a co-worker found a puzzling behavior... He couldn't get correct slices on an object he created. After puzzling over the problem, we found out the problem - __getslice__ seems to change its arguments: in a 32 bit argument, when the MSB is set, the argument is changed to 0x7FFFFFFF. After looking it up, it turned out that the bug was also present in the latest Python 2.5. It also turned out that __getslice__ is deprecated. Here is the link to the bug info. This was the first time I got to submit a Python bug. Kind of a mixed feeling.

[Update: This bug was closed. You can still read about it in the original bug info.]