Rotating Arrays (part II)


Last week we had a look at Kernighan’s algorithm to rotate an array k position and concluded that it might not be optimal, as each element was moved twice. This week, we’ll have a look at another algorithm that moves some items more than once, but overall will do less than two exchanges per items.

Read the rest of this entry »

Rotating Arrays (Part I)


To “rotate” an array k position to the left (or to the right, doesn’t really matter) we could repeat k times a shift of one, using only one temporary variable. This method doesn’t use much auxiliary memory but is inefficient: it will do kn copies if we apply it to an array of size n. Surely we can do better.

Read the rest of this entry »

Learning Python


When you come from different programming languages like C and C++, where you are used to control very finely what the machine does, learning Python is quite disconcerting, especially when it comes to performance.

Without being exactly an optimization freak, I rather like to use the best algorithms, favoring O(n) algorithms over an O(n^2) naïve algorithms/implementations, so you can guess my surprise when after replacing the O(n^2) initial implementation by an O(n) implementation I did not observe the expected speed-up.

Read the rest of this entry »

Initializing Arrays


Initializing large arrays of data before use is always cumbersome but it seems to be unavoidable.

The first types of solutions fill the array with a value that denotes an empty entry. While this sounds straightforward, the choice of that value is not always easy. For floating points numbers, zero may or may not be a good candidate. If convenient (as a zero floating point value is encoded as binary zeroes filling the variable) it may be difficult in some contexts to use because zero may be valid. Fortunately, there’s always the possibility to initialize the array with NaNs, which can be tested and used correctly (but you need the POSIX functions to do that).

Read the rest of this entry »

The 10 (classes of) Algorithms Every Programmer Must Know About


In Tunnels of Doom!, I wrote that the disjoint sets algorithm is one of the very few algorithms every programmer should know. That got me thinking. Should? What about must? If everyone must know about disjoint sets, what other algorithms must every programmer know about?

I made a “top ten” list of algorithms and data structures every programmer must know about.

Read the rest of this entry »