Is Python Slow? (Part II)

In a previous post I expressed my worries about Python being excruciatingly slow and I used a toy problem to compare the speed of Python to programs in other several languages, including C.

Of course, all kind of people complained that I couldn’t compare a dynamic, interpreted language with static, compiled languages. First, let met tell you that I sure can. First, the goal was to measure speed, and not the effects of type system of the language (although logically correlated) nor the programming paradigm: the amount of CPU used to solve a given problem was the primary (if not only) point in interest.

But to be fair to Python, I extended the tests to other interpreted, dynamic languages, such as Lua, Perl, PHP and JavaScript. I also added Pascal and Haskell in the compiled languages groups.

Failed Experiment

Experiments do not always work as planned. Sometimes you may invest a lot of time into a (sub)project only to get no, or only moderately interesting results. Such a (moderately) failed experiment is the topic of this week’s blog post.

Some time ago I wrote a CSV exporter for an application I was writing and, amongst the fields I needed to export, were floating point values. The application was developed under Visual Studio 2005 and I really didn’t like how VS2005’s printf function handled the formats for floats. To export values losslessly, that is, you could read back exactly what you wrote to file, I decided to use the "%e" format specifier for printf. Turned out that it was neither lossless nor minimal!

Suggested Reading: Prisoners Dilema

William Poundstone — Prionner’s Dilema — Anchor, 1993, 294 pp. ISBN 978-0385415804

(Buy at Amazon.com)

This book isn’t really an introduction to game theory, nor a von Neuman biography, nor a history lesson on the cold war era. Most of the book is devoted to either the cold war logic or to game theory, and little to von Neumann who, really, only serves as the main thread bringing game theory and the cold war together. Nevertheless, it’s a quite cromulent introduction, while not very math-oriented, to the fundamentals of game theory where two (or more) players are confronted and try to maximize their gain. Can or should player cooperate? If so, why?

If, like me, you think that the cold war is rather boring, just skip those part, it will still be a quite interesting read.

The Complex Beauty of Simplicity

As I have said before, some of my friends took the very wise decision to go back to school (that is, university) and, accordingly, they’re doing all the undergrad maths courses. As I try to help them whenever I can, I decided to ask them to solve a simple puzzle… or so I thought.

So the problem is as follows:

You have a circle of center , radius and some point , with . Find the projection of point against the circle with center and radius . The method should work whether is inside or outside the circle.

Leafing Through Old Notes

Leafing through old notes, I found some loose sheets that must have been, at some time, part of my notes of my lectures on external data structures. I remember the professor. He was an old man—I mean old, well in his 70s—and he taught us a lot about tapes and hard drives and all those slow devices. As a youth, I couldn’t care less about the algorithms for tapes, but in retrospect, I now know I should have paid more attention. So, anyway, the sheets contains notes on how to compute average rotational latency and average (random) seek time.

Foiled!

QuickSort, due to Hoare, is one of the best comparison-based sorting algorithms around. There are a number of variations, but the vanilla QuickSort does a great job… most of the times.

Indeed, there are occasions where QuickSort leaves its expected run-time to reach run-time, its worst case. But what does it take to push QuickSort into its worst behaviour?

Radix Sort on Floating Point Numbers

Phimuemue, in a recent post (at the time of writing, anyway) present his variation on sorting floating point values using radix sort. His implementation wasn’t dealing with the pesky sign bit so I offered a slight modification to his algorithm as a comment on his blog. But for some reason, he did not allow to post it.

So I’ll present my solution here.

Suggested Reading: Algorithms for Memory Hierarchies

Ulrich Meyer, Peter Sanders, Jop Sibeyn (eds.) — Algorithms for Memory Hierarchies — Springer, (Lectures Notes on Computer Science LNCS # 2625), 2003, 428 pp. ISBN 978-3540-00883-5

(Buy at Amazon.com)

This book is a collection of chapters on various topics pertaining to memory hierarchies and their algorithms, but written by several different authors, without any special uniformity in tone or topics; but that’s OK because it allows the reader to have a broad view of algorithms for memory hierarchies.

Suggested Reading: Advanced Data Structures

Peter Brass — Advanced Data Structures — Cambridge University Press, 2008, 492 pp. ISBN 978-0521-88037-4

(Buy at Amazon.com)

The first part of the book concentrates on search trees and variants, whether balanced trees, interval trees, or heaps. Chapters are dedicated to connected components and like algorithms, one to algorithms for strings, and one for hash tables. Follows appendices on computation, cache oblivious algorithms, etc.

Computing the Neutral Zone

Have you ever add to decide, you and your colleagues, where to go for lunch? Each time, it ends up being a committee, of course. It gets even worse when not only you have many colleagues, but also two offices, or two groups, at different locations. Since we work in a rather large city, we want to walk to the chosen restaurant, rather than drive, but in a way that is fair to either group.

So to settle the argument about where are the restaurants midway of both locations, we need a map, and some math.