• On Algorithms

    So, generally speaking, I’ve typically adhered to the rule that those who develop software should be aware of various classes of algorithms and data structures, but should avoid implementing them if at all possible. The reasoning here is pretty simple, and I think pretty common:

    1. You’re reinventing the wheel. Stop that, we have enough wheels.
    2. You’re probably reinventing it badly.

    So just go find yourself the appropriate wheel to solve your problem and move on.

    Ah, but there’s a gotcha, here: Speaking for myself, I never truly understand an algorithm or data structure, both theoretically (ie, how it works in the abstract, complexity, etc) and practically (ie, how you’d actually implement the thing) until I try to implement it. After all, these things in the abstract can be tricky to grok, and when actually implemented you discover there’s all kinds of details and edge cases that you need to deal with.

    Now, I’ve spent a lot of my free time learning about programming languages (the tools of our trade that we use to express our ideas), and about software architecture and design, the “blueprints”, if you will. But if languages are the tools and the architecture and design are the blueprints, algorithms and data structures are akin to the templates carpenters use for building doors, windows, etc. That is, they provide a general framework for solving various classes of problems that we as developers encounter day-to-day.

    And, like a framer, day-to-day we may very well make use of various prefabbed components to get our jobs done more quickly and efficiently. But without understanding how and why those components are built the way they are, it can be very easy to misuse or abuse them. Plus, it can’t hurt if, when someone comes along and asks you to show off your mad skillz, you can demonstrate your ability to build one of those components from scratch.

    Consequently, I plan to kick off a round of posts wherein I explore various interesting algorithms and data structures that happen to catch my attention. So far I have a couple on the list that look interesting, either because I don’t know them, or because it’s been so long that I’ve forgotten them…

    Data Structures

    1. Skip list
    2. Fibonacci heap
    3. Red-Black tree
    4. Tries
      1. Radix/PATRICIA Tries
      2. Suffix Tries
    5. Bloom filter

    Algorithms

    1. Various streaming algorithms (computations over read-once streams of data):
      1. Heavy hitters (finding elements that appear more often than a proscribed freqency)
      2. Counting distinct elements
      3. Computing entropy
    2. Topological sort

    And I guarantee there’s more that belong on this list, but this is just an initial roadmap… assuming I follow through, anyway.

  • Review: Spin

    Review of Spin (Spin #1.0) by Robert Charles Wilson (9780765348258)★★★★
    (https://b-ark.ca/K6wWOa)
    Cover for Spin by Robert Charles Wilson

    Spin is Robert Charles Wilson's Hugo Award-winning masterpiece―a stunning combination of a galactic "what if" and a small-scale, very human story.

    One night in October when he was ten years old, Tyler Dupree stood in his back yard and watched the stars go out. They all flared into brilliance at once, then disappeared, replaced by a flat, empty black barrier. He and his best friends, Jason and Diane Lawton, had seen what became known as the Big Blackout. It would shape their lives.

    The effect is worldwide. The sun is now a featureless disk―a heat source, rather than an astronomical object. The moon is gone, but tides remain. Not only have the world's artificial satellites fallen out of orbit, their recovered remains are pitted and aged, as though they'd been in space far longer than their known lifespans. As Tyler, Jason, and Diane grow up, a space probe reveals a bizarre truth: The barrier is artificial, generated by huge alien artifacts. Time is passing faster outside the barrier than inside―more than a hundred million years per year on Earth. At this rate, the death throes of the sun are only about forty years in our future.

    Jason, now a promising young scientist, devotes his life to working against this slow-moving apocalypse. Diane throws herself into hedonism, marrying a sinister cult leader who's forged a new religion out of the fears of the masses.

    Earth sends terraforming machines to Mars to let the onrush of time do its work, turning the planet green. Next they send humans…and immediately get back an emissary with thousands of years of stories to tell about the settling of Mars. Then Earth's probes reveal that an identical barrier has appeared around Mars. Jason, desperate, seeds near space with self-replicating machines that will scatter copies of themselves outward from the sun―and report back on what they find.

    Life on Earth is about to get much, much stranger.

    I think of Greg Bear as the kind of writer who’s willing to take a big idea with big consequences, and then actually explore those consequences. Mr. Wilson does the same, here, in Spin, and I think executes it quite well. The mystery is well delivered, the narrative well paced, the characters interesting and fairly realistic, and the examination of the consequences of his idea, both on the individual characters as well as the earth (and universe) at large, is fascinating and compelling. Definitely worth a read.