Well, I made a list almost a year ago...let's see how I did:

OLPC: Yep, I was right on this one...

3G iPhone: Yep, that too.

Competitor to the Nintendo DS: Yep.

Consolidation of Cell Phone Industry: Not yet...but I still think it will happen.

Android's non-success: I was wrong on this one - they've done pretty well, though not the blockbuster some people thought they'd be. I think this year is really the year to see who's right.

Microsoft keeps bleeding cash: yep.

Yahoo: Yes, on all counts.

AMD: yes, on all counts

So far, so good. I'll have to make some new predictions in May...I'm feeling good about this year, especially with the economy in turmoil. If my predictions are right, I'll be a happy man. I'll hit the details later, but here's my short list: Citigroup, Ford, more bad news for Sprint and Yahoo, good news for Intel.

Tomorrow is the last day of my D1 year. There's too much to do, and I'm too stressed to sleep. WTF? (u like the cure?)

[2am update - can't type. Wrists on fire. FUCK]

The Celestial Seasonings factory is surrounded by plague-carrying prairie dogs.

This is not a drill. Notify Sleepytime Bear immediately.

Since I don't want to think about all the work I have, here are some predictions of what will happen in the tech industry over the next 6 months:

• The OLPC Project will continue to die, and be reborn as something that can compete in the ultra-low-cost laptop market. It will die there, too.


• The 3G iPhone will come out, and it will sell like hotcakes. Palm and Microsoft will suffer most of the blow


• The iPhone will be the first serious competitor to the Nintendo DS, and spawn a small ecosystem of games developers


• The cell phone industry in the US will consolidate. Who eats who? I'm betting that T-Mobile eats Sprint, or a good portion of them (Nextel spins off, only to be bought?)


• Google's Android is as big a consumer success as Linux was. *cough*


• Microsoft keeps bleeding cash.


• Yahoo keeps bleeding everything. Somebody -not Google - makes an attempt to buy them, and is rebuffed.


• AMD continues to lose in the desktop/laptop space, and barely hangs on in the server space.

In short, I'm waiting for Sprint and Yahoo to bottom out, and for Apple to top out.

My code has two weakpoints and one annoyance:

1. Filtering is still as slow as anyone else's filtering


2. Sorting the first time is fast. Sorting the second time is fast, but could be faster (annoying).


3. *Reversing* a sorted column is slow.

The filtering issue is something I'm going to address later, but the last item on the list is just plain crazy. Suppose you have a classroom full of kids, and you want to sort them from shortest to tallest. Then, once they're sorted, you realize you wanted them tallest to shortest. This should be EASY, since all you're doing is reversing their order - they're already sorted in both orders once they're sorted at all. The only difference is what you call the 'front' of the line.

Reversing should be fast, but it's not. Here's why...
Table rows are stored as a linked list, which means that you always have to start at the beginning of the list and walk forwards. Getting to the first kid is always faster than getting to the one behind him, which is always faster than getting to the one behind him, and so on. Getting to the last kid is always the slowest. Think of a stack of cards, sitting on a table. You want to reverse them, so you take a card from the top of the stack and put it down as the bottom of a new stack. Then you repeat, grabbing the last card and putting it on the top of the new stack. This is pretty fast, since you're only touching each card once. Right?
The problem is that linked list doesn't let you touch that top card without touching every other card, and it doesn't let you put the card on top of the new pile without touching every card in the new pile. So you actually wind up touching every card many times - instead of 52 card-touches, it's 2074.

The solution isn't that clever, but it works. What we want to do is reverse from the *bottom* of both stacks of cards. Now we grab the *bottom* card in the old deck, and make it the new bottom card in the new deck. Each time, we slip the bottom card underneath the new pile until the card that was originally on top of the deck has been inserted at the bottom of the new deck. Grabbing the bottom card is really fast (think about the kid at the front of the line), and doesn't require you to go through any other cards. Inserting the card at the front of the line is also fast, since you don't need to touch any of the other cards either. Now it really is 52 card-touches.

This cuts my reverse speed down to something much more manageable, but it still requires that I sort everything first. I decided to add a cache after all, but a dirt-simple one: every time I sort by a column in ascending order, I save the entire table for later. If I sort by that same order again, I just swap the current table for the sorted one (which is instantaneous). If I'm sorting in reverse order, I can jump directly into reversing without sorting.

The whole thing added 9 lines of code.

You pick a problem, download solutions from the internet, and try to beat all of them.

One of the projects I'm working on for the Summer of Money is a bit of simple, web 2.0 wizardry. Suppose you have a table, which is drawn from a database like so:

ID	Name	Date
23	Buzz Lightyear	3/4/06
198	George Bush	1/29/09
007	James Bond	5/06/63

It would be nice to be able to sort this table by ID, or name, or date. For longer tables, it might be nice to filter, showing only the rows whose name contains "James" or whose date is in '09. There are two basic ways to manipulate this data: (1) Reload the table, asking the database to give you the information in sorted/filtered order or (2) have the browser do the sorting/filtering itself.

Option 1 requires a round-trip to the server, which is murderously slow on modems or with large tables. Reloading the whole page is also just really inelegant and annoying. We could use a Web 2.0 solution, and use AJAX to magically reload the table without the whole page...but we're still making a round-trip to the server. Even worse, this requires a little more magic on the backend, to receive and respond to the AJAX request. I'd prefer to keep backend code as simple as possible.

Option 2 is also AJAX-y, but there's no server-round trip. The browser already has all the data, so why not write a sorting/filtering algorithm on the client? I decided to go with this one, and looked around for some solutions online.

I found quite a few, but many required massive AJAX toolkits that I didn't want to download just for this one piece of functionality. The remaining ones were a mixed bag - some of them were dog slow, using inefficient insertion sort or bubble sort algorithms. A few of them used the dramatically faster quicksort algorithm, so I decided to focus on those.

Most of those programs were hundreds of lines long, and used a lot of event-binding to do their job. The best of those programs required custom CSS annotations on all the table columns, to give the program hints about how to sort the table. This meant muddying up the HTML, when all I wanted was a simple drop-in solution. I'm also a pretty efficient programmer, and I felt that I could do the job in half the amount of code.

So I decided to write my own.

I started with a simple object, called SmartTable. A SmartTable is initialized by passing in the id of any table on the web page. SmartTables contain a few simple properties and methods:

• pointer - a pointer to the object itself


• table - a pointer to the DOM object of the table we're talking about


• sortCol - the index of the column we're sorting by (starts at '')


• sortAsc - are we sorting in ascending order? (starts at 'true')


• buildHeaders() - a function that adds the UI magic for sorting and filtering, and provides hints for the sorting algorithm


• sortBy(sortCol) - given the index of the column we want to sort, sorts the table by that column


• filterBy(filterCol, filterValue) - given the index of a column and a value, show only the rows of the table for which that particular column contains that particular value


• quicksort - the actually sorting algorithm

buildHeaders() loops through each column in the table, finds the first row containing data, and determines whether that column contains numbers, text, dates, or currency by matching the data against a regular expression (it can be expanded to look for other data). If the column contains DOM nodes (eg - a number hidden inside a link node), it drills into the DOM to find the text. It then stores the datatype as an attribute in the column header. In our example table, these attributes would be "number", "text" and "date". Then it adds behaviors to those headers, so that clicking on a header sorts the table (calling sortBy()), and double-clicking brings up an input field for the filterValue. Entering a value and hitting 'enter' calls filterBy(), and leaving that field hides it again.

filterBy(filterCol, filterValue) loops through every row in the table, looking for whether or not the filterCol of that row contains our filterVal. If it doesn't, we hide that row by changing the CSS. Pretty simple.

sortBy(sortCol) looks at the datatype attribute that was set for the sortCol header, and chooses a comparison function (comparing Dates, for example, is different than comparing numbers). It then passes the table into our quicksort function, along with the comparison function.

quicksort looks at the sortCol for each row, uses the passed-in comparison function, and determines the correct order of the rows. It re-arranges the rows if necessary, which can sometimes mean moving the same row multiple times.

Flush with my success, I decided to try my program against the fastest of the open-source ones, using an enormous table with a thousand entries. My program loaded faster, since I don't do any of the complex prep work that the other program does...but somehow it was able to sort the table in one-tenth of the time! I needed to do better. It turns out that the other program creates a cache of the table when it loads, basically saving a lot of hints that allow it to sort faster. The cache takes time to build, which explains the startup delay, but ultimately gives much better performance. I added a simple cache to my code as well, but the sophisticated cache of my competitor was still making it about 4-5x as fast.

Then I noticed that their program kept track of when a sorted table was being sorted by the same column, but in reverse order. In that instance, they never needed to resort, since they could just reverse the rows and trust that the opposite of Ascending order was Descending order. Clever! I added this to my code as well, but it didn't change the fact that the initial sort was still much slower.

I thought about it. Did I need to make a more sophisticated cache? If so, how? I didn't want to deal with hashing algorithms, and I wanted to keep my code simple. What was the main problem with the speed anyway? When I sorted a simple thousand-item array, quicksort ran in under a second. The main speed hit was coming from sorting a table of DOM nodes, and there didn't seem to be much of a way to get around that.

Or was there?

I modified the sortBy method, adding an extra step. I walked down the table, creating two arrays:

• values[] - all of the values in the sortCol, in a speedy, flat array


• indices[] - all of the indices of those columns, in a speed, flat array. Initially, this array is just 0, 1, 2, 3.. and so on.

I pass both arrays into quicksort, which sorts values[] the way it normally does. When it finds entries that need to be switched, it *also* switches those entries in indices[]. So if values[3] is swapped with values[8], my indices row also swaps 3 and 8. The end result is a sorted values[] array (which I don't care about) and a new, greatly-messed-up indices[] array, which tells me the sorted order of the rows in my table. If we're sorting by ID in the table above, flat[] starts out being [23, 198, 007] and indices is [0, 1, 2]. After quicksort, flat is [007, 23, 198] and indices is [2, 0, 1]. sortBy() takes indices, and arranges the table rows (one by one, with no duplicate movement) in the correct order.

Since sorting an array is about a hundred times faster than sorting DOM nodes, quicksort runs at lightning speed. I still have to move DOM nodes around, but now I only do it once per row, since quicksort has given me the correct order in advance. This cuts row assignment from O(n log n) to O(n). Quicksort, of course, is still O(n log n), but the time required for each operation is so small that it's almost negligible. Row assignment has to be done no matter what, since ultimately we still need to rebuild the table. Cache or no cache, we still take that speed hit. Do I really need a cache, if the only difference is running the sorting algorithm? It turns out that I don't - quicksort is so fast with arrays that the difference is only noticable on tables with thousands of entries. And with a cache that large, the browser starts eating memory and swapping anyway. NO CACHE NECESSARY.

I ran the test again. I'm more than twice as fast as the open-source algorithm. Without a cache!

Not only that, but my code is simpler. I don't do all the fancy hinting, and I don't use a cache.
Their code: 1077 lines
My code: 190 lines

As far as I can tell, I now have the fastest, simplest smart-table javascript code out there. Suck it, bitches.

A wonderful debater. An extremely intelligent guy. Jeffy gave the only 29 I have ever witnessed - unquestionably the best speech I've ever seen. I can't believe he was only 26.

I've been helping my father pack up the house since yesterday. So many boxes, and too little time. It's bizarre to empty a third house with him, and I had some flashbacks to the first time we packed up a house. Then, of course, was the move to the house in Cranston -plenty of things have never come out of the boxes from that one. And now some of those same boxes are off to Brazil, which is probably where they'll stay. I wonder if that's where he'll stay, too.

I'm so glad you asked.

Well, for one thing, I finally finished my two-year stint as part of the National Teaching Fellowship at Citizen Schools. I took a week to regroup afterwards, and then settled into my new job.....at Citizen Schools. Technically, my job title is "Applications Specialist," but really, I think consider myself the "Minister of all things data" My job consists of organizing and optimizing the way we use information within the organization. Also, I change the way people think about using data at the company. It's amazing - people think of data as shapeless, formless...connections are incidental, or perhaps just unimportant. But I'm the kid who used to clean other people's rooms, who has liked nothing better alphabetizing their bookshelves. For someone who loves data, who sees it as living, flowing beautiful representations of ethereal power...this is like a dream come true.

So that's what I do, for 25 hours a week. The other 25 are spent working on the Computer Science curriculum I've been developing for the last year. Right now, though, I'm gearing up to teach at the summer camp over at Northeastern. You can check out the project here, if you're interested. I might put up some lesson plans, if anyone's interested.

This fall, I'll be recruiting volunteers to help teach the curriculum at schools all over the city.. With any luck, I'll be getting some funds to take this nationally. Woohoo!

Tomorrow morning, at 6am, we leave for 8GA Graduation. It's been a hell of a year. Sleep-deprived and hungry, I'm writing the final goodbye letters for my kids. Talk about emotion...this is the hardest part of the job.

This has been a most productive afternoon. I'll close the remaining holes next week, provided I have the time free from work.

One of the benefits of a home-made blogging tool is that it took a long time before spam bots started using it. If you're a spammer, it's cheaper to make a bot that abuses LiveJournal, MovableType or Blogger than to go after some weird tool that a single person on the planet uses.

But this is definitely the year that bots are smart enough to look for things that behave like blogs. I wonder how smart they are...if I change the name of the 'submit' button to something else, will they know what to do? Will it trick the bots? Well, I've updated the site accordingly, so let's see what happens.

The featured picture today is rain taken in the Colorado Rockies, at nearly a mile above sea level. It was an exciting rain, up in the mountains - full of possiblity and adventure.

That is directly the opposite of the rain that's fallen on Boston for the last week. It's been cold, windy and it's schedule to go on for days more. Isn't it supposed to be April showers and May flowers? I didn't sign up for this. Mother Nature, you suck.

I can only hope that the flowers that bloom at the end of the week are profitable. I am still waitlisted at Hugsey (see? I know the lingo), and I may find out by the end of next week. I'm applying for two jobs at Citizen Schools, and I may receive offers on both by about the same time. The Partners In Learning grant is still something I'm pursuing, and I think I may have a real shot at it. No matter which of the three options I consider for next year, I have to consider the possiblity that I may run a large, regional computer science program after school.

So it's a world of possiblities, and it's not out of the realm of those possiblities that none of them will turn out. I may be rejected yet, I may be not get a single offer from Citizen Schools. I may move out to California and start from scratch. Who knows?

Yeah, that was real easy...

This whole week, it is supposed to be sixty degrees. Fantastic.

A man on the train asked me what month it was. "April," I replied. He started screaming, "Oh my GODDDDD!" I laughed a little - his distress was like a little joke, just for me. He got off at the next stop, running and swearing. I leaned my head back and let the sun hit my sunglasses and my colorful tie: today I am dressed up for an interview. I look more like Miami Vice than a program director, but that's okay - I won't take no crap, and I'll solve the problems of the world's children using my devil-may-care attitude and my dashing good looks.

Seriously. I feel happy today.

The countdown...EXTENDED!

I've been waitlisted for their PhD program. Here's hoping...

One down, one to go.

For Lent, I've been thinking about giving up a lot of things. Here are the rejected ideas:

• Cheese


• Alcohol


• Sleeping past 6am


• Chocolate


• Black t-shirts


• Music or Television of any kind

What did I decide to go with? Brace yourself...

Sarcasm.

What are you giving up?

From MSN News:

"Old octopuses become what we call senescent, or senile, reaching the end of their life. And sometimes their actions are very inappropriate."

In adjoining urinals at John Harvard's...

Tall Man: I don't know, man. It's just...it's just so violent.

Short Man: That's messed up.

Tall Man: It really scares me, you know? And it hurts! Does...does your girlfriend ever get like that?

Short Man: (laughing) F*&k no, man! God damn...