The CFM-00

Parallel computing is the next paradigm shift, everybody knows this, but not everyone is taking the proper action to face it adequately. One thing to do is to read on the subject and force oneself to code using threads and various degrees of parallelism; and that’s pretty easy now that a quad core machine doesn’t cost all that much. But the next step, distributed computing, necessitates, well, more than one machine, and if you have different levels of memories and communication channels, all the better.

So out of a bunch of old x86 PCs, I’ve decided to build my own portable mini-cluster with 8 nodes. Nothing all that impressive, but still plenty of fun to build.

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.

Deep Unit Testing?

Unit testing helps you make sure that your code is working properly but the black-box approach has its limits. In fact, in a complex program with (unsurprisingly) complex behavior, black-boxing becomes a major hindrance to testing. So what are the options? There are several options, but they all seem to have their inconveniences; some violate the basic tenets of object oriented programming, some introduce additional occasions for bugs. I think that there’s no easy solution.

Things I never, ever, want to hear. Ever.

Things I never, ever, want to hear. Ever.

• In theory,… No, I don’t want to know what you think the code does, I want to know that it actually does—especially if you’re the one that wrote the code. If you haven’t verified, validated by actually testing stuff in a systematic manner, you have failed. Have you validated the functions with stringent unit testing? No? then get out of my face and go write code to test your code. Validate your hypotheses. Always.

Avoiding the Junkyard

Developing software isn’t easy. No, I’m serious. It’s not. Every year that passes brings us more experience, and sometimes reality bites us real hard in the ‘rear.

For example, people do not always remain with a project until it completes. Often, people join a team for a summer, or for a year or two, then leave. That’s normal and expected. Of course, if the project is large, or the stay short, the code portion that was assigned to a particular individual may not be completed by the time he leaves. Can you manage to leave a team gracefully?

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.

Adding Keywords in Emacs

As you already know—if you read my blog before—I use Emacs as my primary editor, for C, C++, Python, LaTeX, etc., and I’ve grown fond of the clunky ol’ piece of software. Still, once in a while, I need an extra, potentially weird customization.