Sunday, September 25, 2011

Algorithms that need improving

There’s nothing worse than being at the mercy of a poorly designed algorithm. You’ll be sitting there, knowing that if you were just given half an hour with their source code and maybe a programmer of theirs to explain the basic design, you could improve it

One of the classic examples is the ‘estimated arrival time’ on my GPS. A well-calibrated estimate should be too fast about half the time, and too slow about half the time. In the GPS case, however, their estimate is an understatement of your true travel time in about 95% of cases. The only, only time you’ll get there earlier than the GPS estimate is if you’re speeding for a significant fraction of the journey.

As near as I can tell, their estimate of speed is to take the total distance travelled and divide by the speed limit for each of the roads you’re travelling on.

For a company that makes GPS devices for a living, this is shockingly lazy. The big problem is that it seems to make zero adjustment for stop signs and traffic lights, meaning that it always takes too long. Traffic is another one that would be useful, but that’s probably harder to do. Still, it wouldn’t be hard to get a rough estimate – find major arterial roads, and increase the estimate by 50% if it’s between 7:30 and 9:30 or 5 and 7 on a weekday. I am highly confident that even something this simple would reduce the mean squared error in estimated travel times. That’s even without taking historical traffic data.

One that was even more infuriating was the one for the lifts in an old apartment of mine. The building was about 40 stories tall, and had about 4 elevators. During the interminable minutes spent waiting there every day, I deduced tha the algorithm would only send an elevator to the lobby if a) someone had pressed the down button, and b) the elevator in question was the lowest of the four. So what would happen is that you’d have elevators sitting there at floors 28, 35 and 39, and another one going up from floor 5. You’d sit there, watching the floor 5 elevator slowly make it’s way up each of its stops, and the other three would sit there doing nothing until the elevator that started at floor 5 reached floor 28. Only then would the floor 28 elevator start going down to the lobby.

This, as you can imagine, drove me absolutely batty. Talk about pure deadweight loss because some moron can’t add in a line saying:
‘If {No Elevator in Lobby} then send {lowest floor elevator with no buttons pressed} to lobby’.

Hundreds and hundreds of man hours were wasted in my building every year because the elevator company didn’t know what they were doing.

This is the kind of thing that almost nobody takes into account when choosing a building to live in – how quickly do the elevators seem to arrive? As my grandmother used to say, act in haste, repent at leisure. Or in this case, repent in slow minutes of agitation every day.

No comments:

Post a Comment