Hash Functions (checksums, part II?)

On a number of different occasions, I briefly discussed Hash Functions, saying that if a hash function needn’t be very strong if the intend is to use it for look-up, contrary to cryptographic applications. But, unsurprisingly, it’s rather difficult to get a good fast hash function.

Coming up with a very good hash function isn’t easy, but we can at least make an effort to build one by understanding what makes a better hash function, especially by explicitly testing them. Let us have a try at building a good hash function (for look-up) from scratch.

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.

Programming Challenge: List Intersection

The problem of computing luminance was rather of a bit-twiddling nature (and some of my readers came up with very creative solutions—far better than my own), and the problem of the Martian calendar was a bit more deductive (and still not solved, though some of the readers came close to a solution); and for the third programming challenge, I propose something a bit more algorithmic/basic data structure in tone.

The problem I propose in this challenge arises in a variety of settings, such in (simple) search engines, but performing it efficiently is not always trivial.

Coding Maps (Part I)

Quite a while ago, I discussed map generation in the classic 80s-era game Tunnels of Doom. After a short correspondence with Kevin Kenney himself (who kindly answered my questions; and I hope he is aware that he contributed to the fascination of great many kids in computer science), I manage to, not exactly reproduce his algorithm, but create a number of fun variations.

Tunnels of Doom Combat Screen.

This raises the question as to how do we encode maps efficiently in the computer’s memory, not only for Tunnels of Doooooom but also for any number of other games.

Implicit Coding

I’m always playing around with data compression ideas, and I recently came across a particular problem that inspired this week’s entry about implicit coding.

The idea of implicit coding is to exploit some constraint in the data that lets you reconstruct one (or more) value(s) unambiguously from the others. The textbook example of implicit coding is to use a constraint such as a known sum. For example, If you have a right triangle you necessarily have that

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.

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.

RetroComputing

There are plenty of web sites and museums dedicated to the computers of yore. While most of them now seems quaint, and delightfully obsolete, there are probably a lot of lessons we could re-learn and apply today, with our modern computers.

If you followed my blog for some time, you know that I am concerned with efficient computation and representation of just about everything, applied to workstation, servers, and embedded systems. I do think that retro-computing (computing using old computers or the techniques of old computer) has a lot to teach us, and not only from an historical perspective.