Deck Editor and Schlemiel’s Algorithm

Years ago I wrote Forge’s first deck editor. It didn’t do anything fancy and you couldn’t search for anything. You really didn’t need to “search” much because Forge only had a couple hundred cards. I did work hard on the deck editor’s “sort” feature which let you sort cards by name, type (instant, creature, etc…), mana cost, power or toughness. (In my mind “sort” was good enough, so a separate search function wasn’t really needed.)

(From the upcoming set Avacyn Restored)

But there was a problem. As more cards were added, the deck editor’s sort function became slower and slower. At first I guessed that it was a problem with Java but it wasn’t. I thought I was implementing “sort” correctly and that was as fast as it could be. (Later, I learned the correct way to sort things using Java’s JTable.) This “slow sort” problem plagued Forge for a couple of years until the nice developers totally revamped the deck editor and now it is awesome. The new deck editor is actually fun to use because it works so well.

The old deck editor basically used a “n squared” solution that grows very quickly. For example, to sort 100 cards it might take 2 seconds, 200 cards - 10 seconds. But to sort 300 cards took 15 seconds. As you can see, the sort times grows fast very rapidly. For a funny explanation of the same thing, real Joel Spolsky’s explanation of Shlemiel the painter below.

(Begin Quote)

Shlemiel gets a job as a street painter, painting the dotted lines down the middle of the road. On the first day he takes a can of paint out to the road and finishes 300 yards of the road. "That's pretty good!" says his boss, "you're a fast worker!" and pays him a kopeck.

The next day Shlemiel only gets 150 yards done. "Well, that's not nearly as good as yesterday, but you're still a fast worker. 150 yards is respectable," and pays him a kopeck.

The next day Shlemiel paints 30 yards of the road. "Only 30!" shouts his boss. "That's unacceptable! On the first day you did ten times that much work! What's going on?"

"I can't help it," says Shlemiel. "Every day I get farther and farther away from the paint can!"

(End Quote)

Basically it is hard to know if you have the “right solution” when you code. A program can be fine until you add that one feature that just breaks everything. Life and computer programming are both comprises. The perfect solution does not exist.

Excelsior,
mtgrares

p.s.
Joel Spolsky is great and each article has more computer info than my 4 years in college studying computers. Read his blog and be enlightened. For those people who can follow some short code segments in C, Joel talks more about C and Shlemiel here.

Joel Spolsky’s book’s “Joel on Software” and “More Joel on Software” are the best things that I have ever read. They are more readable (and edited) than his blog.

Joel Spolsky’s Blog