t3knomanser's Fustian Deposits

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. (2¹⁰ = 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(n²), 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(n²) 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(n²). 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.

Here's a demo of my current project- an iPhone app called "Gravitone".

Not content to have exceeded the assignment's requirements by adding a graphical layer, I went a few steps farther: I added support for animation and multitouch gestures. The latest version of the source lives here, and it's chock full of comments this time.

Once again, it's under a Share-Alike-CC-license. Don't hand it in as your homework.

Stanford University is publishing video and assignments for their iPhone programming course online. I've been following it and doing the assignments, and man... I miss compsci classes. I've been having so much fun doing this. For those that recall me in college, I was a lazy underachiever in most of my classes- but not the programming ones. In those, I always took the assignment and exceeded the parameters. I would show other students how to do the assignments. I'd add little flourishes.

This has been such a breath of fresh air. By day, I slog through tedious code written in tedious languages to do tedious tasks. By comparison, programming on the iPhone is downright sexy. It's fun, it's fast.

But more than that, I'm enjoying my remote college experience. My brain is getting a gentle stretching, and I really like that. Of course, it's very gentle- the course material goes at a painfully slow pace and is treading over the basics of OOP with a leaden step. But then I pick up the homework assignments, and run past the requirements and show off, and I don't care how dull the lectures get.

Not to say I get nothing from the lectures. I finally "get" Objective-C memory management. ObjC has an approach that's someplace between Java-style Garbage Collection and C style malloc/free.

In any case, I've got my first non-trivial iPhone application done. The business logic is pretty trivial- do some stuff with polygon shapes- but the UI has drawing and animations, which is well beyond the goals for the current homework assignment. If you have an Intel Mac, you can download the SDK from Apple (free signup required) and run it if you like. The linked code is distributed under a CC-share-alike license: HelloPoly code.

If anyone is dumbshit enough to try and hand this in to the class, they're going to get owned, because it's pretty obviously not what the assignment called for.

I love Open Source. It's a great way to develop software. But it has its weaknesses. One of the main weaknesses is consistency. Take a look at these Android apps. When you look at these applications for the Google backed smartphone OS, what you'll see is a complete lack of consistency in the look and feel of applications.

I've done a little work with iPhone app development. I'm an avid user of a wide array of other iPhone apps. Apple provides a pretty standard set of UI widgets. There's some variation; the slider control looks different depending on where it's used, for example. Those variations are largely cosmetic.

If you want to have tabs in your application, there's a built-in tab control. It rests at the bottom of the screen as a set of buttons. Every app that wants to have tabbed screens will use the same widget and the same family of controller classes to do that. Someone could write their own, but it'd be a lot of work when Apple provides a good one already. It would also break the general look and feel- an app that didn't use the standard widgets wouldn't feel like an iPhone app anymore. Inconsistency is not user-friendly and a potential source of confusion.

As a general rule, every app should look more or less the same. We generally rely on the operating system to enforce that. It provides a library of controls and developers just drag and drop. The result is that, unless you go out of your way to be special, every application looks mostly the same as every other application. This gives operating systems a distinctive, recognizable appearance, and it helps minimize the learning curve on new applications.

This is a general rule. There are certain cases in which an application's functionality doesn't fit well in the established paradigm. Adobe products have always used the UI that works for their problem domain, and they've been very successful with that. I'm not trying to argue that every app should look the same, but they shouldn't be different just for the sake of being different either.

The iPhone OS goes a long way to forcing a consistent look and feel on applications, but apparently Android does not. Compare this with this. The "cab4me" app uses a tab control that looks more like a desktop app's control, while Ecorio looks more like the iPhone's approach. Then Locale does the more-like-a-desktop-app thing, but manages to look nothing like Cab4Me's approach.

If you browse through those screenshots, you'll see the same standard problem— a multi-tab interface— solved half a dozen different ways. None of them look alike. The position of the tabs tends towards the top of the screen, but the size of the click area varies. The chrome varies.

The sad reality is that no two of those apps look like they're running on the same platform. Everyone's come up with a new and novel way of solving the same problem. There's not even a consistent color scheme- something that most desktop OSes enforce, and something that carries accessibility concerns.

And that's a weakness of Open Source tools, operating systems and software. It cuts both ways; with no central authority behind the architecture, innovation proliferates at the expense of consistency. As weaknesses go, it's not too bad. It's something that could be addressed.

The big down side is that inconsistency is a Bad Thing when you're trying to promote user adoption. It hurts the Linux desktop, which already looks more consistent than this. I think that it's going to hurt the Linux smartphone.

The iPhone has a lot of weaknesses (being ruled as Apple's private little domain is not a good thing), but it certainly offers consistency. Everything looks like an "iPhone App", and is immediately recognizable as such, promoting usability, user adoption, and branding.