I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. What I’ll do is publish the article from a year ago or so here when I purchase the current issue.

January 2009 was an important change for me. It seems that the Editor was pleased enough with my pieces (and I presume so were the readers) that my commission each month expanded to three pages instead of the prior two (or, if you’re counting, 2000 words instead of 1300). Not quite a 50% increase in pay to go along with the 50% increase in surface area — ha! — but to be quite honest I didn’t particularly care, and still don’t: I really enjoy writing for them and the money they pay is pretty good anyway. The change in word count meant that I could start to do my topics in more depth. Before I would sometimes be struggling to contain the topic in the space, but now the extra room allowed me to cover more detail.

The first article in this new expanded section had to be a good one. I decided to cover one of my favourite data structures: the hash table or dictionary.

Even with the extra space, all I could cover was the basic hash table together with linear probing as a collision resolution mechanism (and example of open addressing) and the problems of clustering. Hash tables with open addressing is still one of my favourite ways of implementing a dictionary, and so writing the article was fairly quick.

I liked doing the figures too, although Figure 2 is a bit bizarre without some explanation (time is meant to be read from top to bottom, first we insert a record whose hash resolves to index 2, then one at 17, then one at 11, etc; the more we add records, the more collisions there are and they tend to cluster). The figure cries out for animation, as I discovered recently when I slipped in a couple of images of hash tables to my CTO video on seeing things in black and white. There I wanted to show how disruptive it can be when a hash table grows, and it too needed animation, especially in a video like that. I’ve since found out that Illustrator can produce Flash animations from a series of layers, etc, but I haven’t had a chance to play around with that as yet.

Double-take: a hash table “disruptive”? Indeed, yes, under certain situations. Much is made of the fact that insertion and search in a hash table is O(1), that is, it’s constant time whether there are 10 items in the table or 10,000. Not strictly true, as it happens, it’s more of an amortized O(1) over many insertions or searches. The reason is that, during an insertion, there may be a point when the load factor is too high (as explained in the article, for open addressing that’s assumed to be about 2/3 full), and the hash table has to be grown. This requires allocating a new array (traditionally it’s set to twice the size of the original), and then rehashing and inserting all of the current items into the new array. This is an O(n) operation and it happens every n items, so, amortized, it smears out to a constant addition factor over all n items. Whoopee for the big-Oh notation, but in practice, if you have a hash table containing a huge number of items, the time taken for this growth may be noticeable by the user or by a real-time process that’s not expecting it.

This article first appeared in issue 277, January 2009.

You can download the PDF here.

(Quick aside: PCPlus used to put part of their archive as PDFs on the DVD in the back of the magazine. They’ve now moved to a CD instead of a DVD, presumably to save on costs, and the archive is no longer on there. I hear they’re going to publish it online instead, sometime in the near future.)

For Wednesday, February 24 (#ds101), the Daily Shoot’s assignment was “There is often a conflict between traditional and contemporary. Make a photo that shows this tension.”

All righty, then. The very first thing that popped into my head, as it did a lot of people’s, was technology, with architecture coming in second place. For Colorado Springs, the only real place for taking a photo of the juxtaposition of the old and the new, in terms of architecture, would be downtown or the Old North End. I didn’t have much time at lunchtime to take the trip down there (it’s 12 miles or so from home), besides which I wasn’t coming up with any great ideas of the top of my head apart from showing the Pioneers Museum — that is, the old courthouse — reflected in the glass of the new one. It will make a good photo, but not this particular Wednesday, with my particular workload that day.

So I copped out to a certain extent and went the technology route. I’d just done calculator vs. slide rule, so this time I thought I’d make a little joke and did old-style dictionary opened at “traditional” and new style dictionary on an iPhone showing “contemporary”.

Not a great photo, I’ll admit. It was a bit rushed in crappy light: the poor old camera didn’t know how to expose the paper with the iPhone screen glaring forth. I’d like to revisit the subject one day — at least in the sense of photographing a traditional dictionary, perhaps with lots of bokeh.

(The main dictionary is the Shorter Oxford English Dictionary, and the one on my iPhone is an electronic version of the Concise Oxford English Dictionary.)

The next day’s task, Thursday’s (#ds102) was just... horrible. “Negative space can be just as important to a composition as your primary subject. Explore negative space in a photograph.” What the...?

First stop was wikipedia to see what it said about negative space. Pictures of vases with faces in the negative space? There seemed to be a germ of an idea in the description  “Negative space can be used to depict a subject in a chosen medium by showing everything around the subject but not the subject itself. Usage of negative space will produce a silhouette of the subject.” I really had no idea what to do. None at all. I was feeling upset from a couple of family phone calls that morning anyway, I was fresh out of ideas, so I just decided to drop that particular assignment.

Until I went out tonight to shoot the next assignment, when I serendipitously came across a shot that cried out negative space, at least to me.

I’d gone to the Fine Arts Center (FAC) downtown to be measured for my costume (earlier in the week I’d landed a part in Crazy for You, opening in May), and I was planning to wander around afterwards to try and satisfy the next assignment. It was getting dark, and I didn’t hold out for any great photos, especially as I’d just brought along my middle zoom (Canon EF 28-135mm f/3.5-5.6, my favorite lens for normal daylight stuff). I walked to my car in the car park, looked back, and there it was.

The sculpture in bronze in silhouette is of a naked family group facing the FAC main entrance. Although I’ve read the description plaque several times, I cannot remember the sculptor nor the name of the piece (and for some reason the FAC website does not describe it either). I’ll update this post later with the details.

So, a day late perhaps, but I’m quite pleased with the result. Note to self: take the monopod next time. It was a 1/15 sec exposure at f/3.5, wide open, and I was balancing the camera on a wall for stability.

Now playing:
Thompson Twins - Love on Your Side
(from Quick Step & Side Kick)