The Complexity of Containers

One thing that came on topic rather often recently, and especially in connection with Python, was data structure complexity and what kind of performance operations should offer. However, it’s not as simple as it sounds. First, algorithm operations to be performed dictate, to a great extent, what container, or abstract data structure, should be favored.

But sometimes, these data structures lend themselves to alternate implementations that have different run-time and memory complexities. Maybe we should have a look.

/* no comments (part II) */

In a previous installment, I discussed the quality of English in comments, arguing that the quality of comments influences the reader’s judgment on the quality of the code as well.

That’s not the only thing that can make code harder or easier to understand. Today (anyway, at the time of writing), I was working on something where arbitrary-looking constants would constantly come up. I mean, constants that you wouldn’t know where they’re from unless there’s a comment. A clear comment. Let’s see some of those.

Python References vs C and C++

As I’ve mentioned before, my new job will ask me to program more in Python than C++, and that’s some what new for me. Of course, I’ve criticized Python’s dismal performance on two occasions, getting me all kind of comments (from “you can’t compare performance like that!” to “use another language then” passing by “bind to external high-performance libraries”).

But it seems that my mastery of Python is still quite inadequate, and yesterday (at the time of writing, anyway) I discovered how Python’s by-reference parameters work. Unlike C or C++ that use explicit syntax to specify what kind of object we’re dealing with (either by value, pointer, or by reference), Python is a bit sneaky.

Suggested Readings: Programming Pearls

Jon Bentley — Programming Pearls — 2nd Ed, Addison-Wesley, 2000, 240 pp. ISBN 0-201-65788-0

(Buy at Amazon.com)

The central theme of this book is efficiency and economy of solutions of programming problems. However, if the book is globally interesting, it would greatly benefit from an update; the proposed programming style—independently of the gist of the solutions— is old school in many respects. The style should probably updated to take modern programming style into account, say, à la Alexandrescu and Sutter for C++.

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).

Compressing Voxel Worlds

A friend of mine, Arthur, is developing a voxel-based game and found himself having to deal with large volumes of data. Unlike 2½D games where the map is essentially a 2D expanse with occasional relief, his game allows the definition of things in full (discrete) 3D.

To avoid loading the entire map in memory, he made the wise design decision of making his world tile-based, so that it can, simultaneously, reduce the working set as well as having an essentially open map, by loading only a small set of visible world blocks at all time. So together we took a look at compressing these world blocks, and it turned out that we can do a lot with fairly simple algorithms and VLCs.

INT_MAX is a terrible NaN (Safer Integer Types, Part IV)

I came across a lovely bug lately. Integer arithmetic, especially in C and C++ it seems, is error-prone. In addition to the risk of having the wrong expressions altogether (a logic error, one could say), integer arithmetic is subject to a number of pitfalls, some I have already discussed here, here, and here. This week, I discuss yet another occasion for error using integer arithmetic.

Consider this piece of code, one that you have seen many times probably, at least as a variation on the theme:

Shellsort

The game is different whether we consider external data structures—that live partially or totally on disk or over the network—or internal data structures residing entirely in local memory. For one thing, none of the courses I had on data structures I had really prepared me to deal adequately with (large) external data structures; it was always assumed that the computer’s memory was somehow spacious enough to hold whatever data you needed.

However, when you’re dealing with files, you can’t really assume that you can access random locations to read, write, or exchange data at low cost, and you have to rethink your algorithms (or change plans altogether) to take the cost of slow external media into account. Sometimes an algorithm that doesn’t look all that useful in main memory suddenly makes more sense in external memory because of the way it scans its data. One of these algorithms is the Shellsort.

Suggested Reading: Find the Bug: A Book of Incorrect Programs

Adam Barr — Find the Bug: A Book of Incorrect Programs — Addison-Wesley, 2010, 306p. ISBN 0-321-22391-8

(Buy at Amazon.com)

This short book (306 p, but a quick read) asks us to debug 50 short programs written in 5 different languages: C, Python, Java, Perl, and x86 assembly. The book offers quite verisimilar code snippets, each of which containing exactly one bug; forfeiting the results. Barr proposes a taxonomy of bugs, from the logical bug to the off by one, and we must debug the programs with him.

C++ Logging

It seems that logging is something we do in about every program we write. Logging complements the standard output with richer messages and detailed information. And each time it seems like we’re asking ourselves how to do that exactly.

Of course, there are already existing logging frameworks out there, but I was wondering how much work it implied. I wanted something that would integrate seamlessly to the existing C++ streams: it had to behave exactly as a classical ostream from the programmer’s point of view, but had to insert timestamps and manage message priorities. The simplest way to do so is probably to have a class that inherits from ostream or similar and that already overloads all the operator<<s.