You are viewing t3knomanser

t3knomanser's Fustian Deposits

More drek than you can pull from an elephant's arse.

How Random Babbling Becomes Corporate Policy

IOCCC Original Winner

Mad science gone horribly, horribly wrong(or right).

Navigation

April 8th, 2011

Recently, I've been at the center of a trend. That trend is complete strangers asking me "Are you ____?" A quick summary.

For example:

Are you Jewish


The Event: While walking to my bus stop, I saw two lost-looking Orthodox Jews standing on the sidewalk. They stopped me and asked if I was Jewish.
My Theory: I have a big schnoz and was wearing a dark fedora.

Are you related to the lead?


The Event: During an intermission at the opera, someone in the row behind me stopped to ask if I was somehow related to the male lead in the show.
My Theory: We both have pony-tails? I'm really at a loss here.

Are you a dancer?


The Event: At the grocery store, I was moving from one aisle to the next when a portly black man stopped his cart and asked if I was a professional dancer. He was quite specific about the "professional" part. When I said, "No," he added, "Well, you really look like one."
My Theory: Apparently I look fitter than I think I do. But also, this was a moment after where I made a semi-flouncy, over-pronounced "After You…" gesture to someone coming the other way. I do flounce. I cannot deny this.

February 18th, 2011

If you could turn back time, how far back would you go?

First question listed was submitted by ninja_possum. (Follow-up questions, if any, may have been added by LiveJournal.)

View 2213 Answers



-10,000 years, at minimum. Tomorrow is always better than today, especially when you can't fact-check.

February 16th, 2011

Bob Morlang

Share
IOCCC Original Winner
When I was working at Tri-Mount, we had these camp trucks. They were army surplus, and while they could take a beating, they only sort of worked. And they took lots of beatings. Never in a million years could they have passed a roadway inspection, but they could haul a tent platform from one side of the mountain to the other. When they ran, anyway. To give you an idea of how they were usually maintained, the camp handyman filled the tires with cement so that he wouldn't have to keep a compressor handy to re-inflate them.

There were two trucks, and usually when one broke down, the other was still operable. But one week, both trucks broke down, and they were seriously broken. Nobody believed that they'd work again. One day, I walked past the area where they were sitting and found Bob Morlang elbow deep in one of the trucks, with parts scattered around him. Keep in mind- Bob was with Troop 7, and not a camp employee. He was a guest at the camp, but he volunteered to take a look at the trucks because he knew we needed them.

There was only one problem: he didn't really know much about the sorts of engines in the trucks. "But it's no big deal," he told me, "I can figure it out."

And he did. In the course of a few afternoons, he ripped apart the engines, figured out how they were supposed to work, and then put them back together so that they did work. By the time he was done with them, they were in the best condition that they'd ever been.

I didn't have all that much Interaction with Bob Morlang, but he made a massive impression when I first met him- which was asking him to counsel me on the Atomic Energy merit-badge. Bob was the only counselor in the Council for it, and it just so happened that he worked as an engineer at the Indian Point Reactor. When I sat down with him to learn about that subject, I got much more- Bob was so much of a polymath. Our sessions working on the badge diverged into all sorts of subjects.

I was only 12 or 13 at the time, and my impression of him was that he was the real-world version of MacGyver. For a young nerd, that's an incredible first impression, and it sticks with you.

I'm very sad to say that Bob Morlang recently passed away at the age of 50. He was leading scouts from Troop 7 on a snowshoe hike around Camp Tri-Mount and had a heart-attack. From what I understand, it was sudden and final. He was an incredible person, and the world has lost something special.

Obituary</i>.

November 30th, 2010

About Computer Programming

Share
IOCCC Original Winner
I'm trying to run a short, informal survey. What are some things that come to mind when you think about computer programming? What do you think it involves? What do you think it's like? If you have programming experience, feel free to reply anyway, but please note that.

September 2nd, 2010

pwd or "where am I?"

Share
IOCCC Original Winner
Apples pointed out I hadn't updated my LJ in a looong time. I do read my friends page, and I do comment routinely, but I haven't done much posting.

But I'm not dead. In fact, I've been active writing and posting in a variety of places. So here's a "where's Remy" list:

February 8th, 2010

Dear Pittsburgh

Share
johnny cash
Dear Pittsburgh,
You may or may not know this, but your city is in the Northeast. Yes, the "Northeast" includes New England, and the "Mid-Atlantic" states of New York, New Jersey, and Pennsylvania. Now, one little known fact about the Northeast is that, during the winter, the skies will shit snow like they just ate Satan's chili.

I bring this up, because it snowed recently. Quite a lot, actually. 21 whole inches. Which definitely is a problem, I understand that. But it stopped snowing Saturday afternoon. Maybe I'm spoiled by having lived in Upstate NY, where this sort of snow is common, but in general, 48 hours after a snow storm, it's generally expected that the streets are plowed. Actually, it's usually much less than that- like 12 hours.

I bring this up, you see, because it's more than 48 hours since the snow ended. And not only is my little podunk street not plowed (or paved with something durable, but that's another kvetch), but none of the streets in my neighborhood are plowed. On Sunday, I helped some overly ambitious neighbor find their way back to their parking space after realizing their car wasn't going to make it 20 yards down the road, and today I helped a UPS driver out of the same snow. The same snow, just to remind you, hasn't been plowed.

This is just a reminder. It does snow in Pittsburgh. And when it snows, we generally expect that the streets are plowed. Snow removal is one of those expected services that the city should be providing. My sidewalk, patio, (very short) driveway and a section of street have all been shoveled by my wife and myself. I've unstuck other people's vehicles, and hit my neighbor's (also very short) driveway. I don't think it's a lot to ask for a plow to run down at least one of the streets in my neighborhood. You don't even need to hit mine. One of the more major streets would be nice. Just enough, for example, that I could walk to the grocery store without falling all over the place.

Like I said: just a reminder.
Sincerely,
Somebody who will not be voting for the incumbent councilman in District 8.

//My dad was in city politics when I was growing up. The two jobs of a city councilman:
//Keep the streets paved, and keep them clear of snow.
"Remy," they say, "we've got an application for you to design. Here's the specs."

The application they want is a pretty straightforward data pump application. Like 90% of what my company needs, it involves picking up records from one place and putting them down someplace else. In this case, the data in question represents item information and it comes from the health and safety database and goes to our production processing database.

At first glance, things like this seem like they should be simple, but in practice, they never are. I started asking questions- "Hey, these different types of data you need moved, are there any dependencies between them?"

"Oh, no. Nope. Definitely not."

Well, actually, yes, yes there are. The base record, the item, is supposed to be created inactive, according to the spec, but all of the other data we're moving- technical parameters, formulas, etc. require the underlying item to be active.

Which means, when somebody makes changes in the health and safety database, there's no guarantee the majority of those changes will ever make it over to the production process database, since we can't process half that data until somebody flips a switch in the production process database.

At this point, I make the natural suggestion: "Maybe we should go back to the user's requirements and work from there."

"There are no user requirements," I'm told. Instead, the analyst working on this project reverse engineered the process by looking at some existing code. Code that does a similar role (pulling from a different health and safety database to populate the production processing one), in a process that's being replaced by the one we're building.

Today, days after I had a milestone to finish my technical design, the analysts send an email to a user, "Hey, how do you guys want this to work?"

When I gave my estimate for this project, I was pretty generous. And this is why. Because "just make it work like the old thing" is not a valid set of requirements. The "old thing" has a bunch of assumptions buried in its code built around how the old systems behave. Assumptions that may no longer be valid. Every IT project should be built around what the users actually need.

January 27th, 2010

Neologism: Unomatopeia

Share
Tom Baker
As we all know, onomatopoeia is when a word sounds like what it represents. "Boom", "Bang", etc. Unomatopeia is when a word sounds like what it represents if only what it represented had a sound.

For example: "The cute little sparrow poinged around the sidewalk looking for breadcrumbs." A sparrow hopping makes absolutely no noise, yet "poing" is exactly the noise it would make if sparrows jumping made noise.

"He lurped at her from across the bar," is another one. When we describe someone as "lurpy", there's a vivid sound to that that describes exactly that sort of… lurpy behavior.

Unomatopeia deserves to enter the vernacular.

December 21st, 2009

House: Gotten

Share
irfutur
We have keys and garage door opener. Paperwork is signed, and a gigantic check has been handed over. This evening, after dinner, we marked our territory by bringing over some boxes and pissing in the corner. Well, okay, we only did one of those. Point is: ours. Yoink. Snagged.

The previous owner did forget to clear the win out of the house, but we're okay with an excess of win. He was also cool enough to leave the patio furniture and some fireplace stuff.

Maybe we moved the win in with us, because everything went smoothly. Closing took twenty minutes, give or take. The bank's agent was a pro, and he banged his way through the paperwork one-two-three. Since neither we nor the seller really felt much need to quibble, that was it.

Our realtor was stunned. Granting that we basically handed this deal to her on a platter, she was just waiting for something to go wrong. But, no. Yoink, house scored, and a package of win delivered for Solstice.

November 23rd, 2009

Literacy

Share
IOCCC Original Winner
I'm in training for two days this week (which is annoying, to an extent, because I have 2 days of work that needs done this week, and only one day in which to do it before going on vacation, which means I'm likely going to need to work on Friday, not that this has anything to do with anything). The training is focused on applying "Lean" principles to data analysis. "Lean" is a buzzword laden approach to evaluating and improving the efficiency of a process. Stripped of buzzwords, it's not a bad set of techniques. Nor is it gospel, contrary to some of the enthusiasm of its pointy-haired proponents.

Regardless, I'm looking for the good parts of the training. One of the key focuses has been on value stream maps. Essentially this is a flow-chart used to understand who does what in which sequence to generate output. In a factory analysis, you'd use it to analyze the manufacturing process so that you could identify waste.

The key thing to note about them is that they focus on inputs and outputs. There are some raw materials at the start, which are the initial step to the first process, which does something to the raw materials. This process hands its output to the next step, which does its own thing generating yet another output. And so on, until eventually, you get the finished good. Along the way, you want some metadata about each step, like its costs and the value it adds to the final product.

I'm sitting there in class, and thinking: wait, inputs, outputs, and chains of processes? This is functional programming.

So I started taking notes, but not in English. I start scribbling away in Haskell, prototyping some functional programming ideas that relate to the problems represented by a Value Stream Map. I'm till not too experienced with Haskell, so it's a little cumbersome, but there's a distinct value, to me, in being able to explain ideas in code.

But then, I remember: Haskell is a literate language.

In most languages, you write code and annotate it with natural-language comments to explain what that code does. In most cases, this means that you have to mark your comments with some special character, for example, in C, you'd write something like this:
/*
Take two numbers and add them
*/
int MyFunc(int a, int b) { return a + b; }
The comment is on the line that starts with "/*" and ends when it hits the "*/".

Haskell, by default, takes a similar approach (one line comments start with "--", and multi-line comments are enclosed in "{-" and "-}". But you can tell it, "Hey, be literate." Instead of requiring you to mark your comments, you instead need to mark your code. A literate Haskell program would look something like this:
Take two numbers and add them
> MyFunc a b = a + b
When you're trying to take notes and then illustrate them with code, or when you're writing code in an experimental fashion, this becomes a really good way to sketch out your ideas.

I'm still not blown away by Haskell's dependency on whitespace, but it's got a lot of other features that make it really good for rapid prototyping of logic. I still don't grok "monads", which means non-functional problems (like IO or random numbers) are still a challenge for me, but it's still a really fascinating language. As parallelism gets more important in software design, so will languages like Haskell.

November 14th, 2009

I've been hearing all sorts of stuff about Haskell lately. It's a programming language that has all of my favorite features: it's a functional language, it uses pattern matching on function definitions, and it's got a very sparse, simple, syntax.

While it doesn't have quite the rarefied elegance of LISP, it has one other really fantastic feature: it uses lazy evaluation all the time. In contrast, pretty much every other language uses eager evaluation most of the time.

For example, if I did this in pretty much any language:
x = 2 * 2
It would execute 2 * 2 and put the result into x. This is eager evaluation. In Haskell, on the other hand, it doesn't execute anything, it just creates what's called a "thunk" and says, "hey, if anybody ever wants to know what's in x, tell them it's 2 * 2. I won't figure out what 2 * 2 is until someone actually wants to know what's in x."

This has some weird effects. For one, you never know precisely when a line of Haskell code is going to execute. It doesn't execute code in order, only as needed. Some code will never execute, because Haskell never decides it needs the results of that expression. And because of all that, you can do something in Haskell that you can't do in most languages: create infinitely long data structures.

For example, I could define a function like this in Haskell:
makeList n = n : makeList (n + 1)
*

That defines a function called makeList that takes one parameter (n). After the "=", it explains what it does: take n, and construct a list (:) with the result of calling makeList on the value n + 1. If I invoked makeList 0, it would return a list like this: [0,1,2,3,4...∞].

Obviously, it's impossible to create an infinitely long list, but since Haskell doesn't actually evaluate the list, I can actually call makeList 0 and get back a thunk capable of producing an infinitely long list.

But it gets better- since the function is recursive, Haskell can execute any arbitrary number of recursions without needing to produce the entire list. So, for example, if I wanted to get all of the list after the first element, I could write this statement:
tail (makeList 0)

That returns a list containing all integers from 1 on up. And if I wanted the 1,000,000th number in that list? I could actually grab it, and Haskell would execute up to that number, and no more.

I can understand why mathematicians like this language. It's the first one that has a really good grasp of how to handle infinities.

*This is not the most elegant way to write an infinite list in Haskell. Much more easily, I could write: [1,2,..]. [1,2,..] !! 1000000 would return the 1,000,000 element of the list (the number 1,000,000 in this case).

November 6th, 2009

I'm putting Minna's name on this, but she may desire edits. Right now, we're in the process of buying our first home, and we've taken our time doing it. The main reason for taking our time: avoiding the mistakes so endemic to buying a home, and learning about the process. We initially started the homebuying process before leaving Albany, over two years ago. We've been engaged in homebuying ever since.

Homebuying

The Process

Before you can buy a home, you need to understand what you're in for. This is a high-level view of the steps:
  • Save
  • Find a place
  • Put in an offer
  • Get it inspected
  • Get a mortgage
  • Close

Each of these steps is surprisingly complicated. At every step, someone is out to rip you off. At least one someone, probably a bunch. The entire industry of real estate is built around ripping people off. So this homebuying guide is going to focus on avoiding getting ripped off, and avoiding the many pitfalls that most first-time homebuyers fall into. It's only through some good fortune that we've avoided some of them, and some education has helped us avoid the rest.

One note: this assumes that we're talking about conventional, fixed rate mortgages. For some people, an adjustable rate mortgage may make sense, but in most cases, it's a risky gamble. ARMs played a big role in the economic problems we're seeing today, so let's just avoid them and let people who have some experience buying and selling property worry about them. A first time homebuyer should never consider an ARM.
Read more...Collapse )

The remaining steps, getting an inspection, getting a mortgage, and closing, are ones I haven't done yet. But, once your offer has been accepted, you have a clock ticking to accomplish two major tasks: get an inspection and apply for a mortgage.

Depending on your local rules, and the stuff you put in your offer, you're going to have about 10-15 days to get these tasks done, so it is important to jump on them quickly. I applied for a mortgage today, but it takes days or weeks to get an approval back (depends on the bank, your credit rating, and how their underwriting process works). But when you apply, you do lock in your interest rate, usually for 60 days. This means, when we're approved, we're locked in for a 4.375% interest rate which is suhweet.

As for the inspection, you do want to find an American Society of Home Inspectors (ASHI) certified inspector, and there's a lot of things to consider in that step.

Everything I've covered so far in this post has been stuff I've actually done. Since I haven't actually gotten approved for a mortgage or had a home inspected, I will refrain from commenting further on them, for now. Expect a part two next week, discussing the inspection, and future installments as I cover the remaining steps.

November 3rd, 2009

Well, that was sudden

Share
run the fuck away
Last week, we noticed a listing for a property that was interesting. Our sort of place, from the pictures. Not perfectly located, but well located for us. It's one mile from all the little shops we like, and closer to even some of the other shops we like. Near a park, on a quiet, quiet street.

We saw an open house on Sunday, got a buyer's agent and saw it again on Monday night, went back to her office, wrote up an offer, and submitted it. It was accepted today. So… we're buying a house, in Shadyside. 2BR, 1.5 bath. The first floor is a gorgeous open plan space. Kitchen is brand new; the stove has never even been used. A new patio was installed. Furnace, hot water, all new. The upstairs isn't quite as nice, but certainly nice enough. The washer and dryer are antiques and will need to be replaced.

It's not under contract with us yet; we need the realtor to bring over some paperwork. Tomorrow I'll try and hire an inspector, and then we'll work on getting the mortgage. We're excited, and a little trepidacious.

October 25th, 2009

I've discussed Idea Mining before: every idea that pops into your head, jot it down. When you're looking for inspiration, or have some time to develop some idea, poke around in your mine and see what grabs you.

I started using Evernote, which had the advantage of syncing, but recently switched to Notational Velocity. It lacks syncing, but is much more lightweight. When I'm sitting at my computer, the amount of friction in jotting down new notes is minimized. It's a great tool, but by switching to it, I gave up syncing. This means, for example, I can't jot ideas on my phone and have them show up on my computer.

At least, not by default. But I'm not going to be thwarted by such details. So, I sat down, banged out some settings and scripts that let you sync emails in your GMail account to Notational Velocity.

What follows is a high level overview of the steps. It's not hard to do, although it took a little doing to figure out.

You're going to need the following things:
  • OSX Leopard or later
  • Developer tools installed (on your OSX install disk, or downloaded from Apple)
  • Notational Velocity
  • A Gmail account with IMAP enabled

Configure Notational Velocity


Once you have Notational Velocity installed, you're going to need to make one settings change: on the Notes tab of the Preferences window, change "Store and read notes on disk as:" to Plain Text Files. Note also the Folder that you store your notes in on this pane.

Configure Gmail

You need to enable IMAP from the settings pane.

You also need to configure a filter for a pseudo-address. In the filter section of settings, create a filter along these lines:
Matches: to:([your email]+mine@gmail.com)
Do this: Skip Inbox, Apply label "Notes"

This means that, every time you send an email to [your address]+mine@gmail.com, it's actually going to come to your account, but get labeled with Notes (which is a folder in IMAP).

Get SSH Prepared


This step, sadly, does involve a little command-lineage. You can only connect to Gmail's IMAP interface over SSH, and fetchmail needs the certificates where it can find them for this to work.

From /Applications/Utilities fire up Terminal, and type the following:
openssl s_client -connect imap.gmail.com:993 -showcerts

This command will output a big pile of of text, but up at the top, you'll see a large block of output that starts with:
-----BEGIN CERTIFICATE-----
(a big bunch of characters here)
-----END CERTIFICATE-----
(there are two of these blocks, you want the first one, which is actually for imap.gmail.com.

Copy that text (including the BEGIN and END lines) and save it to a file called ~/.ssl/certs/gmailimap.pem. You will likely need to create those directories before you can save it.

You need one more certificate, which you can download from here (where it says "Equifax Secure Certificate Authority (Base-64 encoded X.509"), and save it as ~/.ssl/certs/equifax.pem.

To make these certs usable by fetchmail, you have to run one last command at the command line:
c_rehash ~/.ssl/certs.

This step is a lot easier if you know your way around the command line. The bulk of this SSH section was adapted from here.

Notes.pl

Download this file and save it in ~/Scripts (a directory you'll need to create). You'll also need to make it executable, which involves another command-line bit:
chmod +x ~/Scripts/notes.pl

Open that file in a text editor and change the first two lines per the instructions in the file. Basically, you need to tell it where to find your mail (/var/mail/[your mac username]) and your Notes folder (remember I told you to keep track of that).

This script parses your local Unix mail (deep inside OSX, it has nothing to do with Mail.app or Thunderbird or anything you normally use for email) and turns what's there into notes in Notational Velocity.

We're almost done. The last step is to…

Configure Fetchmail

If you're using Snow Leopard or Leopard, fetchmail is already installed. It's a powerful tool for one task: downloading email from remote systems and putting them on yours. Specifically, into the local Unix mail.

Fetchmail works off of a configuration file. Create a file called ~/.fetchmailrc. In this file, you'll need to paste these settings:
set daemon 1300 #the number is the number of seconds between polling attempts

poll imap.gmail.com proto IMAP port 993 user "youraddress@gmail.com" password "yourpassword" keep folder "Notes" ssl mda "/usr/bin/procmail -d %T" postconnect "~/Scripts/notes.pl && > /var/mail/yourmacusername"

Change "youraddress" and "yourpassword" to your Gmail username and password. Change "yourmacusername" to whatever your username on your Mac is. It may contain spaces, in which case you'll need to escape them like so: /var/mail/Remy\ Porter. Note, that is a "\" followed by a space.

To test this much, send yourself some emails that should be turned into notes (don't forget the +mine!), and then, at the command prompt, simply type the command:
fetchmail.

Once it works, we want to make sure it runs every time you log on, so download this file and put it in your scripts folder. From the command line, type:
chmod +x ~/Scripts/fetchmail.command.

Now, in your OSX System Preferences, go to Accounts, select yours, and add a Login Item that runs fetchmail.command.

TADA!

Using It

Now that you've got it set up, send an email to youraccount+mine@gmail.com. The subject line is the note title, in Notational Velocity, and the body is the content of the note. It'll sync however frequently you want it to, by modifying the indicated line in your .fetchmailrc.

Also, if you want to be able to read notes on your phone, you could use something like Dropbox, which is what I do. Also, the way this works is to append to an existing note. There's no real way to edit.

Warnings

I'm not super sure how this will work if you have multiple accounts on your Mac that you want to use this. You may need to instead configure fetchmail.command to run as a system startup item, and then there may be issues with using "~/Scripts"- you may need to use an absolute path. The Googles are your friend, if that's what you decide you want to do.

October 14th, 2009

This has been irking me for a long time, but in light of Stross's anti-Star Trek rant and this rant about sexist/feminist influences in SF, I think it's time for me to put this idea down on page.

Joseph Campbell killed genre fiction. Mostly SF, but genre fiction in general. It wasn't his fault. Joseph Campbell did something fairly brilliant: he saw a way to take traditional stories and build them together into a single taxonomy. He found elements that crossed cultures (although it's definitely got a Western bias) and synthesized a sort of "grand unified theory" of mythology and literature.

I'm not here to debate the veracity of this idea. Campbell is right in enough ways that his ideas have explanatory power, even if there are cases that fall outside of his scope.

Sometime between when he had those ideas and today, people blew his findings out of proportion. Repeatedly, I've dealt with people that use Campbell to defend unoriginal literature, claiming he proved that all stories were the same anyway. Those not as well read might not name-drop Campbell, but they like to trot out the "finite number of stories" canard.

It's simply not true. While there are some commonly used story templates, there are as many unique stories as there are ways to arrange words into meaningful sentences.

And this gets us back to the death of genre fiction. Modern science fiction, especially in TV and movies, takes the stance that stories are the same, and are inherently about the characters, and that science fiction or fantasy is just another costume to dress the same story up in. Some might consider this the "literary" tradition. In this approach, all the trappings of the setting exist only to drive up the special effect's budget and provide trailer-fodder, while the story could be told equally well in any other setting. Star Wars is the most obvious example of this: sword and sorcery fare in spaceships. But pretty much every Star Trek episode from some point in the middle of the TNG era also fits the bill.

What you find is that the setting is just props and costumes. For some stories, that's fine, but genre fiction used to be about exploring ideas. Whether it's taking a modern idea and casting it in a different light by analogy or imagining a world drastically altered by some new technology or idea, in classical genre fiction, it was always the ideas that took center stage.

In some cases, notably the likes of Heinlein and Asimov, the result was cardboard characters that generally could be grouped into a handful of niches, few of which ever truly leapt off the page. At the same time, these books are rife with ideas. Different social codes, technologies that reshape society in strange ways.

I'm not trying to say that character driven drama is bad and idea driven drama is good. But the best genre fiction can do both. Sterling's Holy Fire builds a fascinating world, and then shows it to us through the eyes of a newly rejuvenated octogenarian learning about the gerontocracy from the ground up. Vonnegut, of course, was a master of mixing bizarre ideas with likable characters.

My main complaint is that the pendulum has swung away from "big ideas", at least in mainstream sci-fi. It's hardly dead, but sometimes, it feels like somebody slit genre fiction's throat.

October 13th, 2009

"Breathtaking" code

Share
IOCCC Original Winner
Words like "breathtaking", "stunning", "astounding", "amazing", and "incredible" are not positive words. Oh, they're often used in a positive context, but in reality, they only convey a sense of wonder and disbelief. They can be applied to something horrifying just as easily as something delightful.

Such has been my experience over the past few days.

Once upon a time, some fragment of the giant behemoth I work for needed an application to manage some inventory tracking and similar tasks. They found an external contractor that would make it for them. In that era, the app was built in VB6 with an MS Access back end. Horrible, yes, but hey, it was the 90s.

Well, now it's time to upgrade. So they go back to the same contractor. "Hey, we want it to be .NET and use SQL Server. Here's a check."

Well, it wasn't that easy, of course. There are policies. Checkpoints. Oversight. I was part of the oversight, and my job was to get the application through our "gates". Since this was a purchased application, we didn't care if it was terribly well designed, so long as it worked. We weren't going to have to maintain it. So we got some design diagrams from the contractor, sanity checked them, and then called it a day.

More fool I.

Last week, I hear, "Hey, that application- they're not satisfied with the support from the vendor. They want to bring it internal. Hey, Remy, find out what you need to do to make it fit with our standards."

Now, when we develop an app internally, or have a contractor develop an app that we intend to support, the auditing requirements are much stricter. We don't care if an outside vendor has to suffer under horrible support issues, but if we're wasting time on stupid support work, we're unhappy.

So, the first step then, would be to audit the application via a code review. I sat down in a room with three other developers, we pulled up the code, and we started skimming through it.

It was breathtaking.

The first, most glaring thing, was that the actual design and the provided diagram had no relationship to each other. That didn't bode well. And it was all downhill from there. As a sampling of some of the amazing things we saw:
  • One window in the application has all of the business and data access code bundled up in it. It's like they took all the functions and dumped them into a bucket.
  • But not all functions. For example, when that main window wants to log an error message, it calls out to a class called "Utility". When it does that, the Utility class makes a call against the main window. Not only is the code just a disorganized pile in a big bucket, but sometimes the bucket says, "Hey, you gotta go look in another bucket to find that!" and when you do, the other bucket says, "Nope, it's actually back out in the original bucket."
  • All of the database access stuff is hard coded strings. With no SQL injection protections.
  • It stores passwords in plaintext
  • The most stunning thing, however, is what the application does every time it launches. Every time the application launches, it attempts to add columns to a bunch of tables. If those columns already exist, this would cause an error, so it just ignores the errors. Since, once the app has run once, the columns will exist, that means every time a user runs the app, it's trying to add columns to tables for no damn reason.
There's more, but I won't bore you with the details. I wrote a 2,200 word code review document. Normally, these documents follow this form: "File X, Line 128, variable strFoo should be named foo, we don't use Hungarian Notation." For even large projects, they don't tend to get that long, just because they're so terse. This, this was a 5 page essay. I couldn't even call out flaws by line numbers, just because the developer was so clearly incompetent. I've dealt with some bad code in my day, but this is just special.

There's a punchline. They started development using .NET 1.x, and then partway through switched to .NET 2.0. In .NET 1.x, there was no built in FTP functionality. If you wanted to do FTP, you needed to write your own class to do it, or steal some. Microsoft's developer documentation site, MSDN, had an MSFTP code sample, which demonstrated how one could implement their own FTP code. The developer copypasted this- despite the fact that .NET 2.0 had all the functions he needed- and included a class called "MSFTP" in his project.

He couldn't just use the class as it was, however. There were some quirks in our FTP server it didn't handle. And while he was at it, he added a "Dispose" method to handle cleanup, replacing Microsoft's use of the "Finalize" method. This is actually a good .NET technique for technical reasons that are irrelevant here, so he obviously read a book. He didn't read it closely enough, because his Dispose is actually implemented wrong, but that's neither here nor there.

In the comment above his "Dispose" method, he had the gall to include this:
'M$ should have implemented this. Man, this code is sloppy.

When I read that, I just started cracking up.

Until I saw how much my company paid for this. And then I started crying.

October 4th, 2009

Good seats

Share
IOCCC Original Winner

Good seats
Originally uploaded by t3knomanser.

September 25th, 2009

Weekend Revolutionaries

Share
Rippy the Razor Animated
The G20 protests haven't gotten too out of hand, but there's a lot of broken windows. Thus far, only 66 arrests and 6 injuries, nothing serious or life threatening from what I can get from the news.

But there was something else I caught on the news that gave me pause: some of these kids out on the streets are under the impression that they're fighting a revolution. They wear masks because the government could "vanish" them away into a prison. The various G-20 protest organizing sites use the terminology "revolution" and "images of revolt".

What an incredible degree of inflated self-importance. These kids show up for their "revolution" for a few days, throw some rocks, pretend that they've done something and taken a significant risk to life and liberty, and then go back to their lives. A few months later, some other protest-worthy event comes up, rinse and repeat.

They're revolutionaries like a guy driving a Prius is an environmentalist. As someone pointed out, Pittsburgh was home to the Homestead labor strikes. Steel workers wanted to unionize and it turned into a gun battle between them and the Pinkertons. Cannons were involved.

That puts a little pepper-gas in perspective, doesn't it?

With all that in mind, I would like to clarify a few things for our visitors:
  • Protesting is awesome. Seriously, enjoy the fact that you live in a country where this can happen. The Beijing G20 Summit in 2005 didn't see these kinds of protests- and we all know why.
  • Permits are awesome too. Chants of "Who's streets? Our streets!" resonate on a deeply emotional level, but the reality is large clusters of people pose a safety risk. So when the police attempt to disperse the crowd, they're not doing it to silence anyone, they're doing it because they are concerned about property damage, injury, and the ability of emergency vehicles to get through. Also, people actually live and work on those streets, and they have just as much right to use them as a protest does. There is no conspiracy to silence you, and requiring permits for large gatherings is not an unreasonable requirement.
  • There is no revolution. Don't kid yourself. If there were a revolution, you wouldn't do this for the few days when G20 was in town, but every day. You wouldn't be facing down pepper-gas and rubber bullets. You'd be dealing with real bullets, made of metal, that would kill and maim you.
  • The idea that the protesters and the police are adversaries is a dangerous and wrong idea. Everyone is responsible for keeping an event like this safe. Only someone deficient in basic humanity would actively wish harm on the protesters or the police.
  • Property damage is not communication. It's shitheaded jackassery. If you want to achieve social change, you need people to build a consensus. Smashing windows isn't a good way to do that.


I could go on, but this covers the key points. As I said, dont be a jackass, and you'll go far.

Also, Pamela's was one of the places that got its windows smashed. That's just not cool man, not cool at all. Pamela's is a Pittsburgh institution and home of the best pancakes in America. Not. Cool.

September 22nd, 2009

I'm Local Famous

Share
Tom Baker
Last week, I put together DontBeAG20Jackass.com, and started sharing it with the world. Today, my phone has been ringing left and right as local news agencies call to ask about interviews and the like.

Today, I was on the local TV station, with this interview, and tomorrow I'll be on the associated radio station for a five minute interview in the morning. The local newspaper has a brief blurb about me on their paywalled-site (I'm not sure how they expect to make money, but they're trying).

Based on watching the traffic and such from the site, I'm going to put together an after-action-summary this weekend, because I learned a few things doing this.

September 18th, 2009

I Still Live: Updates

Share
IOCCC Original Winner
I am still alive. I have not fallen off the Internet. Since the last time I actually got things together to post, life has continued unabated, and all sorts of fun and interesting things happened, mostly of personal interest.

A few things of a more global interest:
HitTrack, my first iPhone application, got approved and now languishes in the iTunes store. It's nothing spectacular, but it's a workable D&D hit point tracker application, with some nicely done eye candy.

Of more current interest, I assembled Don't be a G20 Jackass, a site that allows people in and around Pittsburgh to sign a polite request that, when the G20 protesters show up next week, that they keep in mind that people actually live here, and would very much like it if the city government doesn't have to pay huge lump sums to clean up and repair damage. I don't think it'll matter, but it was a fun, easy project, and at least grants the illusion of efficacy.

Also, I have a laptop for sale: a Core Duo MacBookPro, 2GB RAM, 2GHz processor, 100GB HDD. Let me know if you're interested.

July 11th, 2009

Morons oppose security

Share
tesla
Today, ImageShack was hacked by some anonymous children seeking to get their manifesto out there. If nothing else, it does a good job of showing off that the differently-abled can still master basic computer security tools.

Actually, I'm pretty sure this is a prank. They ramble on and on about the evils of "full disclosure". But nobody in the security industry advocates full disclosure. To the contrary, responsible disclosure is the most common approach security researchers take. When a researcher identifies a vulnerability in a software product, the first thing they do is approach the vendor to alert them to it. The vendor is given a reasonable period of time to work out a patch, before the details are revealed to the public. In some cases, the only people who get full details are the people responsible for the software- everyone else gets alerted to the vulnerability.

But in any case, the objection is: why disclose vulnerabilities at all? Why not keep them a secret, thus keeping the bad guys from exploiting them?

Because many of the bad guys are pretty smart. If I'm smart enough to find a security vulnerability, there's good odds that there's a bad guy who is also smart enough to find it. So when a vulnerability is discovered, it's good to assume that the bad guys already know about it too. Maybe they haven't exploited it yet, but they could be working on it. You certainly don't know what they know or what they're doing, and you can't control it either.

Keeping it a secret doesn't keep the bad guys from finding it, but it does keep the good guys ignorant. If the good guys don't know about the vulnerability, they don't know what they can do to defend themselves. Until the vulnerability is patched, they're sitting there exposed- and without disclosure, in blissful ignorance.

Okay, but why full disclosure? Isn't it enough to say, "Hey, I found a vulnerability?" Nope, because the software vendor's response is: "No you didn't. Prove it." And this is where the "science" aspect of computer science kicks in. The researcher has just published the results of an experiment: "I performed test X, and got result Y, which means I just pwned this system." Merely publishing the results is not enough to prove you've done it- you also need to show your work. You have to distribute your methodology, so other people can replicate your work.

The sucky thing, of course, is that, if the bad guys haven't found out about the vulnerability, they certainly have now. Which brings us back to responsible disclosure: a researcher should give a vendor a window in which to resolve the problem. The fact that this window closes is vital to keeping the vendors honest. There have been plenty of occasions in which researchers have alerted software vendors to a vulnerability, and the vendor has ignored them.

Fixing bugs costs money, and fixing security vulnerabilities looks bad- like they're admitting weakness. A company, acting on its short-term best interests, may choose to ignore reports from the security community. But if the researcher discloses the vulnerability to the public- well, now the vendor has to act.

July 7th, 2009

On critique

Share
IOCCC Original Winner
With the recent spate of money-making, blockbuster films that are heaping piles of suck, people complain that it's unfair to call a movie bad- it's just opinion. There are no objective standards.

There are objective standards. When picking a hammer, many of the details may be a matter of the user's taste, if the hammer is unable to drive nails, we would all agree that it's a bad hammer. If your aunt knits you a sweater with no arms, while it was a sweet sentiment, we would all agree that it's a bad sweater. If someone were to take a great number of words, selected at random, put them onto page and call it a novel, I think we would all agree that it's a bad novel.

While there is a lot of room for opinion, in any creative endeavor, there are metrics for success and failure. There are, mostly qualitative, but some quantitative measures for whether a creative work is "good" or "bad".

My purpose here is not to write a treatise on critique, which I'm sure has been done better by someone else, who has devoted a great deal more time and effort to the subject. But as a critical dilettante, here's how I approach a critical examination of creative works- regardless of medium.
Read more...Collapse )

July 3rd, 2009

Idea Mining

Share
run the fuck away
So, I've been doing "this thing", the thing being "idea mining". I'm the sort of person that gets all sorts of random ideas during the day. At the time, they always strike me as interesting, but they're always transient. Idea appears, it looks interesting, and then it's forgotten as I go back to the actual task at hand.

Later, I sit down, and try and remember it, and WHOOSH. Nothing. It's gone.

So, a few weeks ago, I decided to start trying to record those ideas. The name of the practice is idea mining. The goal is to collect ones ideas and thoughts, organize them, and use them later as sources of inspiration and action. Or maybe pass them off to someone better positioned to act on them. Or just put them aside because they're impractical, or just plain dumb. Whatever.

Step One: Record


The first step in building an idea mine is recording your ideas. The obvious choice would be a notebook. I personally use Evernote on my iPhone. A handheld digital recorder, a PDA, whatever. Some people like Wikis.

Regardless of what you chose, it has to be:
a) Something that you always have with you - you can't record your ideas in it if it's not there
b) Something that is low friction and quick - you aren't going to record your ideas if it takes a significant amount of effort to record them
c) Something that is easy to work with later

That third point is my main reason for sticking with Evernote, but again- it doesn't matter what you use. Focus on the goal- record ideas when you have them. I'm the sort that does his best thinking on the toilet or as he drifts off to sleep, so my phone is great. If you do your thinking in the car, a digital recorder might be better.

It also takes some discipline. I know, several times, I've been near sleep, had an idea, and had to force myself to sit up and scribble it down. I try and say things like, "Oh, you'll remember it tomorrow," or "it's not that good an idea anyway".

And you'll have that thought a lot. "It's not a good enough idea to be recorded." Irrelevant! Maybe you're right, maybe you're wrong, but record it no matter what. Even if you ignore everything after this step, record every idea. Don't try and only record the good ones, because you're not always going to be able to tell, and the goal here is to build up the habit of recording your ideas. Once you get into the habit, you're going to get more ideas.

My experience with this step was that, for the first week, I was a virtual font of ideas. It tapered off and I went through a dry spell for a few weeks, and now I'm getting up a steady output of a few ideas a day, coupled with a few longer "jot of the day" notes- several paragraphs expanding on an idea of interest to me.

Step Two: Organize


You're going to be generating a lot of data, here. You're going to need to spend some time going through it. Fortunately, you've got all your ideas recorded, so there's no real rush on this. Even if you get backlogged, the ideas are still written down some place, and you won't forget them now.

How to organize them is up to you. Using Evernote, all the notes I record on my phone are synced to my home computer. In my Evernote client, I can tag the notes, using tags like, "good idea", "bad idea", "impractical", "actionable", "todo", "done", etc.. I tag by topic too, like "mad science", "writing", "hook", "character".

Again, the techniques to use here are largely up to you. Unlike recording, which requires immediate action, this can be done at your leisure. Just don't lose anything, because the last step is:

Step Three: Mine them thar' ideas!


Keep the organizing and acting steps separate. Periodically, check your "actionable" ideas, see if there's anything you want to tackle. When you're working on a creative project and are stumped, head back to your mine and see if there's anything in there that works for you. Use it for inspiration. Use it as a todo list. Use it as a personal reference.

My experience, after having done this for a few weeks, is that you're in for some surprises. You'll have more ideas than you think you will, even through those dry spells (in the past month, I've logged 206 notes, for an average of 6.9/day- not Manfred Macx territory, but not too bad). You'll have more bad ideas than you'll ever expect, (one of mine was a portable bidet, another was that a late night talk show hosted by William Shatner would be awesome, and an idea for a movie starring Eminem and Steve Guttenberg called, "What Mathers?"), but you'll also have a bunch that make you go, "Hey, that's pretty clever."

The final goal, of course, is to act on some of these ideas. Or hand them off to someone who can. Add a little creativity to the world, and turn ideas into end products.

June 26th, 2009

That extra pudge is a side effect of the panorama process. He's husky, but not quite that husky.

June 19th, 2009

Ship of Theseus

Share
Podlek
The Ship of Theseus is one of those old philosophical saws. It came up in conversation the other day, and so I skimmed the Wikipedia article, only to be surprised that none of the sources cited took the same attack to the problem that seemed intuitive to me.

So, on the off chance this is a relatively original idea, I decided that I should get it written up.

For those unfamiliar, the Ship of Theseus poses this problem: If you take a ship, and replace every component of the ship, until nothing original remains, is it the same ship? At what point does it cease to be the same ship?

Common sense tells us, of course, that it is the same ship. And everyone from Aristotle forward has tried to explain why that is, with the occasional jerk that takes the stance that it isn't the same ship.

The Aristotelian approach was to separate the formal cause and the material cause of the thing. It's a fairly Platonic approach, which isn't surprising: there's the "idea" of the ship, and the "material" of the ship- even as the material changes, the idea stays the same. Pirsig's concept of patterns is a less Platonic approach to the same idea: there's the pattern of a ship which is made up of subpatterns in the form of the different components; changes to the subpatterns don't change the over-pattern.

The other big approach is "four dimensionalism"- which, at first glance, was my preferred approach to the subject. If you view the ship not as a three dimensional object, but a four dimensional one, where its history and future are one long line, and the 3D ship is just one temporal slice out of that line, you can easily resolve this conundrum.

Except, of course, that to be complete, one would have to have a 4D timeline for all of the components, and suddenly the ship is less a ship, than a generalized area where the timelines for other objects occasionally merge.

I'm not a fan of any of these approaches, in part because they all share an unspoken assumption: that the world is composed of objects, and that these objects are distinct from one another.

Our sense organs receive inputs from the world, a whole hierarchy of processing centers pick up those signals and organize them into structures. When you look at the pathway of just the visual processing centers, you can clearly see the evolutionary steps that built the rather complex visual system we have. At low levels, we have simple abilities like recognizing lines, and increasingly complex abstractions get built up from what is, at the lowest level, the stimulation of light sensitive cells.

Photons excite your rods and cones, which in turn send signals across your nervous system, which get processed by various neurological systems and result in a mental model of the world, where those photons are interpreted as "a ship".

A large purpose of our brains is to convert the inputs to our senses into models that can be manipulated and acted upon. If my brain is able to identify that ship as Theseus's ship, and not my ship, I know not to trespass, less I earn myself an ass-kicking. And by being able to distinguish those sensory impressions as "a ship" and not, "ocean", I can do nifty things like not drown because I thought I was standing on a boat's deck while really I'm on the ocean floor.

It sounds absurd, but we know that, when failures occur in this processing system, really bizarre results can occur. Like the rather famous story of a man who thought his wife was a hat.

The point I'm trying to dig down to is this: the world is not a collection of objects that we can interact with. The world is continuous. The identity of objects as distinct objects is not a fact of the world, but a fact about our understanding of the world. The pile of matter that constitutes Theseus's ship is just a pile of matter.

The problem of Theseus's ship is not one of the identity of objects: objects don't have an identity. The identity of objects is a perceptual thing, born from our own minds' organizing principle. Our brains are object oriented. The world can be understood in these terms, but as the Ship of Theseus problem shows, there are edge cases that can give us bizarre results when we start trying to analyze what about an object provides it with its identity.

God, I hope that made sense.

June 16th, 2009

Safe Communications

Share
run the fuck away
Given the events transpiring in Iran, now's a good time for more people to fire up Tor, an "onion router". Essentially, it's a Peer-to-Peer anonymizer that helps keep your Internet traffic confidential. The more peers on the Tor network, the better the network performs and the more anonymous it is.

Tor also acts as a proxy, so if you or someone you know is living in a country where Internet traffic is restricted, using Tor allows them to bypass web censorship. With browser plugins to make it easy to use, anyone with only a small amount of technical know-how can get unfiltered web access whether their government or employer likes it or not.

You can download Tor, and quickly benefit from its security benefits, if you're concerned about staying anonymous online. If you want to help others bypass censorship, you must run in relay mode. It's easy to setup, and will only take you a few minutes. It will even do its best to talk to your router to configure services so that you don't have to.

By simply leaving a Tor relay node running on one computer on your network, you can help guarantee anonymous, unfiltered access to the Internet for anyone in the world. No muss, no fuss.

If someone lives in a country with web censorship, they may have a hard time getting access to the Tor install files. So, if you have some web space, consider mirroring the install files. Pass the link discreetly to those that might be interested in such things. I'm setting up my own mirror right now.

June 14th, 2009

Riots in Iran

Share
IOCCC Original Winner
At this very moment, things are spiraling out of control in Iran. Frightened by a suddenly politically active youth bloc, the government did the only thing you can do if you're a repressive, theocratic, and generally vile government: it tampered with the election results. It didn't just tamper- "tampering" implies that they wanted to conceal their actions. They fabricated election results. They released election results that have as much grounding in reality as Lord of the Rings.

The message was clear: "Go away. We do not want you involved in the political process. Return to your cynicism and go away. Fuck. You."

Fuck you indeed. Since the announcement of the fabricated results, the Persians have taken to the streets, and they're still out there. Marching, rioting. They are mad as hell, and they're not going to take it anymore. As of this morning, protests are still moving through the cities.

It's too early to tell where this is going to go. The government is scrambling, raiding dorms, arresting anyone that could rally the people, cutting power, Internet, telephones, and now hunting satellite phones. But word is still getting out, people are still getting organized.

This may be the beginning of the end for the current regime, and good riddance to bad rubbish. For Persians and for the rest of the world, this violent upset could be the best thing to happen to the region, and it's been a long time coming. This could be the death of Iran's theocracy.

Which raises the question, where's the US news media? It's not that they're not covering the story- it's getting headlines, here and there. But they're focusing on other things. Last night, as people were taking to the rooftops in Iran. CNN's top story was the Six Flags Bankruptcy.

Not only was the Internet the best place to get up to the minute reports, it was the only place. Considering Iran's role in the US's foreign policy, this is patently ridiculous.

All this said, there's painfully little we can do. But some people in Iran are still online. Discuss the subject, and let the people of Iran know that the world supports them.

June 9th, 2009

I'm the KOOL AID MAN!

Share
Tom Baker


//Oh yeah!

June 6th, 2009

Minna and I haven't been too hot on buying a house. We're saving a big wad, and waiting for the right thing to come along. We're not going to stress about it, we're not going to angst over it. Our apartment is nice, cheap, and enough for anything we need.

In short, we're a Realtor's worst nightmare. They can't leverage us. "I've got another offer in, so you need to act quick!" No, no I don't. If I don't get this place, there'll be something else. Each place I've looked at is nicer than the last, and at a better price.

We looked at a place today, and we were feeling pretty good about it. We tagged along on someone else's showing, so we didn't meet the selling agent. In order to save a few bucks, Minna and I are willing to brave the process without a buyer's agent, if the seller's agent is willing to cut their commission from 6% down to 4-5%.

I thought this was pretty reasonable, and I've talked to some Realtors that were fine with such arrangements. This Realtor, on the other hand, gave me shit over it. "Oh, I'm way too busy to handle both sides of the transaction for a mere 4-5%."

Yeah, because we've eaten up so much of your day by getting you to show the house (oh, right, we didn't!). And, like a regular buyer's agent, we've dragged you to a million houses while looking for something we like (oh, right, we didn't!).

If we brought in our own buyer's agent, she'd get 3%. I'm offering her 1-2% on top of that all for the glorious chore of signing some papers. It just makes no sense to me- I'm offering you more money for doing pretty much nothing. It just boggles my mind. Even worse, she was such a raging bitch about it, that I don't even want her to get even the 3%- I don't want to do business with her. It's not that she was rude, or really lost her shit, she just started ranting at me well past the point where I was ready to drop the subject. I'm trying to cut you a deal, I'm trying to work out something were everybody wins. It's fine to say "No thanks," but she ranted at me about it well past the point where I cared anymore, and was just trying to end the phone call politely.

It's sad, because it was a nice place, but the condo fee was too steep anyway- $200/mo is just more than we could afford on top of taxes and mortgage. She had an offer in anyway (she claimed, and I believe it), so she can just hope that goes through, because I'm not going to counter offer, and if I see she's the selling agent on another property I'm interested in, I'm going to avoid it. It'd have to be something really special to get me to deal with her.

There's a reason Levitt equates NAR with the KKK (Freakonomics is an excellent read, by the way).

June 4th, 2009

On the Order Of

Share
IOCCC Original Winner
Programmers, when they're really concerned with being efficient, will often start talking about "Big O" or "Order". There's a lot of interesting math behind this, but what it boils down to is a very simple concept- how many operations does it take to solve a certain problem, using a certain algorithm? I'm going to simplify things here, ignore the difference between so called "Big O" and "Little O" and not worry too much about the theoretical underpinnings. This also isn't the only metric used to evaluate how efficient an algorithm is, but it's a major one.

For example, if I hand you a deck of cards, and I tell you to find the Ace of Spades, how many cards would you have to look at in order to find it? Assume you start at the top, and keep drawing cards until you find the one you want. In the best case, the very first card you flip is the one you're looking for. That's on the order of one operation, written as O(1). But, that's the best case. What about the worst? If it were the last card you flipped, that would have taken 52 operations- O(52), or, to be really programmery, O(n), where "n" is the number of cards in the deck. By being general, we can extrapolate this to any collection of cards- be it a full deck, less than a full deck, or even a collection of something else entirely- like an address book.

When talking about the "O" of an algorithm, programmers don't like to worry about constants. We don't like "52"- that's far to specific. "n" is much more useful. But similarly, if there were an algorithm with O(2n+1), we're going to ignore the 2 and the +1 and just call in O(n). Doubling it once just isn't a big enough change to really count. It's details and small stuff, and if "n" is sufficiently large, it just doesn't matter.

Now, searching each individual card in the deck isn't terribly clever, but if the deck is shuffled, that's really all you can do. Picking out randomly, going from top to bottom, bottom to top, it just doesn't matter. But if the deck were sorted- now that could be useful. Think about the phone book- it's sorted, and you don't have to search every single name to find the one you're looking for.

If you were writing a computer program to find a name in the phone book, you'd start by going to the name in the middle. If it's the name you're looking for, great, you're done. If not, does it come before or after the name you're looking for? Once you know that- you've just eliminated half of the names. Take the remaining half, and go to the middle. Repeat the previous process until you find the name you want. Each operation (name you look at) eliminates half of the remaining names. Searching a sorted list is very effeceint, and in this case, it's on the order of "lg n". (lg is the log base 2, or "what power do I have to raise 2 to to get "n"). This, by the way, is called "binary search" and is the goto searching algorithm to use in any search.

In our naive search, where we just checked every element, it's O(n). In a deck of 52 cards, that's 52 operations. Not that bad, but what if I had a list of 1,024 items? That's 1,024 comparisons. But if we used the binary search, it's O(lg n)- 10 comparisons. (210 = 1,024). That's a savings of 1,014 comparisons, in the worst case.

Programmers tend to break down algorithms into a few major categories based on their Big O.

Stuff that's O(lg n) is very fast stuff. They scale really efficiently to big sets of data (1,000 elements is 10 operations, a million elements is 20 operations, a billion elements is only 30 operations!).

O(n) isn't as liked, and most O(n) algorithms can be turned into O(lg n) if you're very clever and find ways to cheat (for example, if you need to search an unsorted list, it'll always be O(n), but if you sort it first, even though sorting is expensive, you'll make it up if you search a lot).

Sorting is really expensive, in comparison. The best sorting algorithms are O(n*lg n). That means, for a set of a thousand elements, it would take 10,000 operations to sort. Ugh, but some problems just can't be made any easier. O(n*lg n) is the best you'll get for sorting algorithms, and there are whole classes of problems that fall into this category.

Worst is O(n2), or even larger exponents. This is the demon of programmers. For example, the first sorting algorithm that most CompSci students learn is the Bubble Sort. It's very simple to understand and implement, but it's an O(n2) sort. But, to sort 1,000 elements, you have to do 1,000,000 operations. Algorithms that run in "polynomial" time are ones that programmers hate. It's worth noting that there are a lot of problems that, as far as we know, can't be solved any faster. There's a whole family of problems that are called "NP Complete", which, right now, can only be solved in polynomial time. Whether or not it's possible to find a better way to solve these problems is an open question.

This was brought up today because I'm working on Gravitone, an iPhone instrument that uses gravity to generate music. I took a very naive approach to the problem, and simply cycle through all the masses and objects in the world and apply gravity to every other object. My algorithm is O(n*m), where n is the number of orbs in play, and m is the number of masses. Sort of polynomial, and if I were to try and scale it up so that the orbs could effect each other, it'd be O(n2). Ugh, polynomial time? That's expensive. Or is it?

I did some research in gravity simulation, and found that the best algorithms out there run in O(n*lg n). The one I looked at specifically was called the "Barnes-Hut algorithm", and it's very clever, and something I'll probably use for a different application. It's also fairly complex to implement, and requires a lot of memory, despite being very fast (memory/speed are a common trade off).

It's faster, but should I use it in this application? No!

In my application, I've capped it at 15 orbs in play and 5 masses in play, which means it's going to take 60 operations.

That's 20 objects total, and in the Barnes-Hut algorithm, 20 * lg 20 ≈ 60 operations.

For very small data sets, sometimes, really expensive seeming algorithms are okay. Now, the Barnes-Hut algorithm would be better- it would scale better, and it would allow me to have the different orbs attract each other, and the masses- it'd be a much more compelling simulation, but that's not the point of the application. I don't need the power offered by Barnes-Hut.

All that said, I think making a Barnes-Hut simulation on the iPhone would be kinda neat. Maybe a game, or a different instrument.
Powered by LiveJournal.com