Sorting Lists (part II)

Last week I showed you the radix sort on simple linked lists. This week, I will present a version of QuickSort modified to sort simply linked lists.

Sorting Linked Lists (part I)

The sorting algorithms we were taught in class were typically simplified versions of the algorithms that assumed that the data remained in memory and in contiguous memory locations, also known as an array. What we often have, however, are linked lists. Generalizing algorithms like the QuickSort to lists is not very hard in fact if we use a modification of the basic algorithm.

For lists with numerical keys (or values), there might be a simpler algorithm that scans the list in only one direction, so that simply linked lists are a perfectly cromulent data structure, that is, the radix sort.

Recycling Random Bits

It is not uncommon that for large-scale simulations you need a large volume of high-quality (pseudo)random numbers. The relatively short period of the C standard library’s rand function may make it impractical for your purpose; and you might need to resort to stronger generators such as the Linux-provided /dev/random and /dev/urandom pseudo-devices. But calling those is a relatively expensive process as /dev/random may stall until its “entropy pool” is repleted.

The /dev/urandom is the unblocked version of /dev/random, but it is also demonstrably less random. Moreover, one has to access either pseudo-devices through the file system, which in certain case introduces a noticeable impact on performance. Using other sources of randomness such as a hardware random number generator may also incur significant delays.

To avoid being stalled, I propose a simple method that will allow you to recycle bits from an expensive pseudo-random source without polling it too often.

Cutting Corners

Cutting corners is generally thought of as a bad thing. It generally is, I agree. But in some occasions, optimally cutting corners is the right thing to do. I can show you what I mean. Using the Logo programming language (precisely the KTurtle implementation), I devised the following experiment. Consider the following image:

Two circles drawn with KTurtle

Suggested Reading: A Field Guide To Genetic Programming

Riccardo Poli, William B. Langdon, Nicholas F. McPhee — A Field Guide to Genetic Programming — Lulu, 2008, 240 pp. ISBN 978-1-4092-0073-4

(Buy at Amazon.com)

This is not an ordinary textbook as it does not follow the expected pattern but is rather an extensive survey of the field of genetic programming. Each chapter introduces a major concept or issue in genetic programming and covers the subject in a rather authoritative way, supported by copious documentation—the last 57 pages of the books are occupied by the bibliography.

Suggested Reading: An Introduction to Genetic Programming for Scientists and Engineers

David A. Coley — An Introduction to Genetic Algorithms for Scientists and Engineers — World Scientific, 2005, 227 pp. ISBN 981-02-3602-6

(Buy at Amazon.com)

This short book introduces the major concepts in genetic programming under the angle of multi-objective optimization in high-dimensional spaces. We learn about the elementary operator of genetic programming such as cross-over, mutation, and candidate selection (with or without elitism). A good quick introduction to genetic programming, with just the right dash of math!

Coughing up bacon (or Why the Swine Flu won’t kill you just yet)

Last week, while friends and I were discussing the sensationalistic news coverage of the swine flu pandemic, I was joking that if you were not coughing up bacon, you were probably OK.

I fact, I wasn’t so much joking about the flu itself than about how (dis)information is presented in sensationalist news channels such CNN, Fox, or even Montréal-based LCN. Earlier this week, news were that the flu had already caused tens, maybe hundreds, of deaths, but that data was presented as if, you know, you just catch the swine flu and you die right away from it. However, on Thursday morning, on the radio, I heard that the Mexican authorities recounted “swine flu” death to… less than ten. To really understand what’s going on, you really have to do some research, and sometimes what you discover is radically different from what you’ve been told.

Different problems aren’t always different

Magic Squares are much less frequent than latin squares in computer science (on which we may come back in the future), but they have a number of (fun) applications.

Historically, magic squares are tied to numerology, alchemy and other esoteric sytems. However, as you may already know, I’m not interested in pseudoscience except to debunk it, so this post isn’t about using magic squares turtles to predict the level of the river running behind your house.

Albrech Dürer's Melancholia I

Compact Tree Storage

Implementing data structures in a way that uses efficiently memory should always be on your mind. I do not mean going overboard and micro-optimizing memory allocation right down to the bit. I mean organize data structures in memory so that you can avoid pointers, so that you can use contiguous memory segments, etc. Normally, minimizing storage by avoiding extra pointers when possible will benefit your program in at least two ways.

First, the reduced memory requirement will make your data structure fit in cache more easily. Remember that if pointers are 4 bytes long in 32 bits programming, they are 8 bytes long in 64 bits environments. This yields better run time performance because you maximize your chances of having the data you need in cache.

Second, contiguous memory layouts also allow for efficient scans of data structures. For example, if you have a classical binary tree, implemented using nodes having each two pointers, you will have to use a tree traversal algorithm, possibly recursive, to enumerate the tree’s content. If you don’t really care about the order in which the nodes are visited, what’s quite cumbersome.

It turns out that for special classes of trees, complete trees, there is a contiguous, and quite simple, layout.

How many eyeballs to make a bug shallow?

In the The Cathedral and the Bazaar, Eric Raymond said that “Given enough eyeballs, all bugs are shallow.” Of course, what he meant is when you have a large enough tester base and lots of developers, almost all bugs are found, characterized (i.e., how to make them reproducible and what are the effects) and fixed by someone in the developer group. This appears to me as somewhat optimistic and begs the question… how many eyeballs does it take to make a bug shallow?