Beej's Bit Bucket

Some links to enjoy:

• Insanely deep fractal zoom in HD. If you’re not on drugs, this relentless exploration of the Mandlebrot Set’s periphery will make you feel like you were.
• A quick overview of OGRE 3D, a neat free 3D engine.
• A potentially interesting way of patching Python on the fly for asynchronous I/O; I didn’t pursue it, but it seems like a not-bad idea on the surface.
• The Soundex Algorithm, a not-so-complex algorithm for categorizing words by their sounds. Good for finding words by sound.
• Recent Progress in Quantum Algorithms. Seems like one of the more approachable essays.
• Quick overview on making threadsafe functions.
• ACM Programming Competition World Final Problems for 2010. I participated in the contest a couple times back in school, years ago! Was never on the winning team, though, sadly.
• Bugfix for Phoenix, a 1980 coin-op arcade game.  Retro-awesome.

Right now, the GoatDetector is notifying you: "Goats detected"!

The idea of Design Patterns in computer science is one of many ideas that hadn’t be formalized when I was first learning about computers, but that’s not going to stop me from talking about it, now is it? :-)

The basic idea is that there are a number of recurring problems that occur in a variety of projects, and there are “design patterns” that can help solve these problems in a fairly well-defined way. They aren’t algorithms, exactly; they’re more like software design structures that help data flow in useful ways.

For instance, let’s say you have a class and you want to instantiate a single instance of that class that everyone else can get a reference to and use. There’s a pattern for that (The Singleton Pattern), but today I’m talking about another one: The Observer Pattern.

Read more…

There was an infamous professor at my university with a multiple choice exam question:

What is the correct spelling of Edsger

(A) Dykstra

(B) Dikstra

(C) Dijkstra

(D) Dyjkstra

I never did forget how to spell it—it’s the fact that I-J-K appears in order that helps you to remember.

Anyway, one of Dijkstra‘s most famous algorithms is one to find the shortest path through a graph. The graph is a set of vertices connected by weighted edges.  Or, more concretely, a set of cities connected by roads of varying lengths. The question is, what’s the shortest path from Copenhagen to Stuttgart?

Read more…

DOMs rule. You can load the entire XML into memory and traipse random-accessy all over the DOM tree.

But what if your entire DOM won’t fit in memory?  No, “Hit the pub” is not an acceptable answer in this case.  (If it is, it’s a coincidence.)

What you can do is use an “event-based” XML parser. This parser will read your XML file and execute callbacks at important places, like when a tag begins and when it ends. A couple of such parsers are Expat and SAX. I’ll use SAX for this example because it’s quite popular, though the mechanism is similar in Expat.

Read more…