Algorithm.co.il

Python

The Case Against Floating Point ==

Posted on by 3 Comments

While working on the clipping bug, I had to do some floating point comparisons. To handle this virtual mine-field, I used simple precision comparisons.

Not surprisingly, I wanted to know what’s ‘the right way’ to do this in Python. When I discussed this subject on #python, I was told to take a look at the decimal module, of which I wasn’t aware at the time.

Most experienced programmers know that you shouldn’t compare floating point numbers with ==. If you want to check floating point equality, you usually decide on a precision, and check either the absolute error, or the relative error. Hence, floating point == isn’t used, maybe except for rare circumstances. I would even venture to say that when possible, static checkers should emit warnings on floating point ==.

On the other hand there are the beginner programmers. Those usually use == by mistake, and will be surprised by the strange results they sometimes get back.

My suggestion is to do either of the following:
1. Change floating point == to behave like a valid floating point comparison. That means using precision and some error measure.
2. Change floating point == to raise an exception, with an error string suggesting using precision comparison, or the decimal module.

Since this change is not backwards compatible, I suggest it be added only to Python 3.
Personally, I prefer no. 2. It is clearer, and less confusing.

Arguments against this suggestion are:

1. This change breaks existing programs:
I believe it most likely triggers hidden bugs. Since the suggestion is to change it only in Python 3, Those programs will most likely be broken by other changes as well, and will need to be changed anyway.

2. This change breaks compatibility with C-like languages:
I agree. However, the already agreed on change of the / operator is even a stronger break. Most arguments for changing the / operator apply here as well.

3. Programmers will still need the regular ==:
Maybe, and even then, only for very rare cases. For these, a special function\method might be used, which could be named floating_exact_eq.

What are your thoughts on the subject?

Various Small Python Helpers

Posted on by 5 Comments

I’ve been working lately with arkon on various projects related to diStorm. One of these projects involved writing a solid Python API around an existing C API. This C API uses a lot of flags as arguments and return values of functions.
Since I want my code to be easy to use in an interactive shell, I’d like to return something that’s not just a number. The obvious solution is to use a Python Enum. There are many implementations going around, most of them equivalent. I’ve got the one I use. What I recently added though, is the SymbolInt:

def SymbolInt(value, name):
    class _SymbolInt(int):
        def __str__(self):
            return name
        def __repr__(self):
            return 'SymbolInt(%d, "%s")' % (value, name)
        def __eq__(self, other):
            if isinstance(other, str):
                other = other.lower()
            return int(self)==other or name.lower() == other
        def __ne__(self, other):
            return not self == other
    return _SymbolInt(value)

Short, and very much to the point, this makes exploratory API’s much more readable and usable. It is useful as a return value from enum functions as well.

Along with SymbolInt I wrote hexint:

class hexint(long):
    def __str__(self):
        return hex(self)[2:-1]
    __repr__ = __str__
    def __repr__(self):
        return hex(self)[:-1]

This one makes program addresses readable.

Lastly, here’s a little function that I found missing from itertools:

def head(iterable, num_items):
    for obj,i in zip(iterable,xrange(num_items)):
        yield obj

UPDATE: Don’t use this head() function, use itertools.islice instead. Thanks go to Erez for pointing that out.

Two Mathematical Bugs

Posted on by 2 Comments

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:

Counter Example for the Line Clipping Algorithm

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.

Solution for the Random Selection Challenge

Posted on by Leave a Comment

A few days ago, I wrote up two small Python Challenges. Several people have presented solutions for the first challenge, and I also posted my solution in the comments there.

However, the second challenge remained unsolved, and I will present a solution for it in this post.

[Read more…] about Solution for the Random Selection Challenge

Harvesting with threadmap

Posted on by 4 Comments

Dune 2 Harvester

From time to time, I need to harvest a website, or many websites. For example, to collect the data from IMDB to run the Pagerank algorithm. Other times I need to query some non-web servers.

Usually in such cases, I have a ‘read_single_url’ function that is called in a loop from a ‘read_all_urls’ function. The straightforward implementation of this will run slowly. This is not because read_single_url takes a lot of time to parse the websites it downloads. The delay is mostly due to the latency of network operations. Even on high bandwidth connections, your bandwidth utilization will be quite low.

To fix this, I wrote a function named threadmap that runs each call of read_single_url in a separate thread. Just like map, threadmap runs a given function for each element in the input sequence, and returns once all the calls are complete.

Here is an example use of the function:

threadmap.threadmap(query_server,
                    url_list,
                    max_threads=10,
                    on_exception=threadmap.IGNORE)

My first naive implementation just created a thread for each element in the list, and started them all simultaneously. This caused network IOErrors and other problems. This issue was handled by setting a maximum number of threads that may run at once.

The next issue I had to handle was exceptions. It is not obvious what is the best course of action once the inner function raises an exception. At the least, the exception has to be handled so that threadmap’s synchronizing code may be allowed to run.
My current implementation allows for a few different behaviors: ignoring the exception, aborting threadmap, retrying, and returning a default value for the problematic call. To implement these behaviors, I used the traceback module, after reading Ian Bickings’ excellent explanation of exception re-raising.

For those interested, here’s a copy of the code. I’ll be glad to read any comments or suggestions about it.

Fun with Matrices

Posted on by Leave a Comment

I’ll let the code speak for itself:

In [81]: m = Matrix(array([[1.0,1.0],[0.0,1.0]]))
 
In [82]: def my_sqrt(x, num_iters):
   ....:     r = 0.5*x
   ....:     for i in xrange(num_iters):
   ....:             r = 0.5*(r+x/r)
   ....:     return r
   ....:
 
In [83]: m*m
Out[83]:
array([[ 1.,  2.],
       [ 0.,  1.]])
 
In [84]: my_sqrt(m*m, 10)
Out[84]:
array([[ 1.,  1.],
       [ 0.,  1.]])
 
In [85]: m
Out[85]:
array([[ 1.,  1.],
       [ 0.,  1.]])

It’s always fun to see the math work out. At first when I learned that e^A for a matrix A may also be defined using the Taylor series in the usual way, I was really amazed. It still amazes me that this stuff works out so well. This is another kind of beauty.

LStrings and ASCII-Plotter at UtilityMill.com

Posted on by Leave a Comment

It seems Gregory is fond of ascii-art, as he took my scripts, and put them online at utilitymill.com.

UtilityMill.com is a cool new website, which allows you to run scripts as small web applications. What Gregory actually did, with just a few key-strokes, was turning my two scripts into web applications. While these scripts aren’t the most useful web applications in the world, I could think of a few others that are.

Gregory also thought of another use for the UtilityMill. Consider my post ‘Rhyme and Reason with Python’. Let’s say you want to try out my script as well, but you don’t want to go through the hassle of downloading it and all the required dependencies, and then figure out how to run it. If I set it up as a small web application there, I could have any reader be able to see the code and its output without any effort. I’ll be sure to try something like that in my next code-oriented post.

Small Python Challenge No. 3 – Random Selection

Posted on by 12 Comments

This time I’ll give two related problems, both not too hard.

Lets warm up with the first:

You have a mapping between items and probabilities. You need to choose each item with its probability.

For example, consider the items [‘good’, ‘bad’, ‘ugly’], with probabilities of [0.5, 0.3, 0.2] accordingly. Your solution should choose good with probability 50%, bad with 30% and ugly with 20%.

I came to this challenge because just today I had to solve it, and it seems like a common problem. Hence, it makes sense to ask ‘what is the best way?’.

The second problem is slightly harder:

Assume a bell shaped function p(x) that you can ‘solve’. This means that given a value y, you can get all x such that p(x)=y. For example, sin(x)^2 in [0,pi] is such a function. Given a function such as Python’s random.random() that yields a uniform distribution of values in [0,1), write a function that yields a distribution proportional to p(x) in the appropriate interval.

For example, consider the function p(x) = e^(-x^2) in [-1,1]. Since p(0) = 1, and p(0.5)~0.779, the value 0 should be p(0)/p(0.5)~1.28 times more common than 0.5.

As usual, the preferred solutions are the elegant ones. Go!

note: please post your solutions in the comments, using [ python]…[ /python] tags (but without the spaces in the tags).

Rhyme and Reason with Python

Posted on by 1 Comment

After reading xkcd’s blog, I went to LimerickDB.com. It looks and works just like bash.org, but for limericks. Quite amused with some of the limericks available, I wanted to try and compose my own.
The first one came out fine, but I got stuck without a rhyme for the second one:

a man named guido once thought
he’d invent a language well wrought
indentation as tabs

Uhm, no luck there… “tabs” does not rhyme well. Then an idea came… I could create a rhyme index!
How to do it?
First, I took my already written word index. Last time I used it was to solve a substitution cipher for my crypto homework.
Then, I looked for the phonemes for each word, using espeak – a text to speech program:

lorg@kild:~$ espeak -q -x hello
 h@l'oU

After doing so, I collected words that had similar phonemes endings, and there it was, a rhyme index:

In [84]: words.get_word_rhymes("tabs", word_index, rhyme_index)[:10]
Out[84]:
['crabs', 'stabs', 'macnabs',
 'dabs', 'cabs', 'scabs',
 'slabs', 'arabs', 'snobs',
 'thebes']

Note that better rhymes are listed first – according to the length of the match.
To create this list I didn’t use stress information, although with some more work it may be done.

Back to our limerick, we can see that “tabs” does not have really good rhymes. Better luck with indentation maybe:

In [86]: words.get_word_rhymes("indentation", word_index, rhyme_index)[:20]
Out[86]:
['kishion', 'alleviation', 'expostulation',
 'machination', 'syrophenician', 'proposition',
 'infatuation', 'computation', 'mansion',
 'meditation', 'aggression', 'anticipation',
 'clarification', 'logician', 'gratulation',
 'discretion', 'quotation', 'presentation',
 'dissolution', 'deprecation']

And we get (not the best limerick I admit):

a man named guido once thought
he’d invent a language well wrought
with space indentation
and good presentation
we all got the language we sought

My original ending line was “it left all the perl hackers distraught”… but it ain’t true, so I gave it up. The ‘distraught’ was found with my script as well.
If you want to look for your own rhymes, then you can use my hacked-up script, although it isn’t written well enough for my taste. (For example, don’t expect to see documentation :)
I’ll upload a better version once I refactor it.
To save you the trouble of generating the word index and the rhyme index from scratch, I used cPickle to store them. You can use them for lookups regardless of the script.

Interesting links – 4

Posted on by Leave a Comment

http://ivory.idyll.org/articles/advanced-swc/

“Intermediate and Advanced Software Carpentry in Python” is an excellent reading by Titus Brown. If you feel you’re good with Python but want to improve it, or if you are an experienced programmer that wants to get better, this is a good place to go. I liked it.

http://c2.com/cgi/wiki?AlternateHardAndSoftLayers

During the time I was working on my Compilation course, I was thinking about the challenge of writing yacc in yacc. Well, I went searching for “yacc in yacc” and stumbled across this page. It is a part of a very strange ‘pattern wiki’. It has fascinating discussions of the subjects in it, but I don’t like the old-style wiki navigation. Still worth a taste.

http://www.scottaaronson.com/writings/bignumbers.html

Do you know the kind of duel where two people need to name the biggest number? If you thought something along the lines of ‘hey, I’ll write something with a lot of nines’, well, you are in for a surprise. This article has a nice solution for the problem. Excellent read, especially if you are into computation theory.  I really liked that one.