import com.enigmaticThought.blog;
Nate has fixed the BugQuash badge display, so everyone who has contributed to the Flex SDK can show the world. I’ve added mine back to the sidebar and I need to hunt another bug to earn my orange belt. As thanks for harassing him (idling in a chat room and asking every so often) he added me to the Test Page.
There are many ways to solve a problem, which is why algorithms matter, but how do we choose which one to use? Maybe a flash game needs to do some collision detection, or perhaps a flex app holds a large set of data and needs eliminate outliers. Before we start looking at problem solving strategies, we need to learn some terminology, so we will begin with the big one, Big O notation.
Big O notation allows us to describe an algorithm using a limiting factor. That means we take a look at a single aspect of an algorithm, for example speed, and try and determine what type of calculation has the most impact on that aspect. Then from this factor write a simple equation that the algorithm is no worse than. Typically this is in relation to the size of the input, so Big O notation is typically show in relation to the number of elements (n). Since Big O notation is all theoretical (it never uses real numbers, just fake math) it is assumed that only really big numbers of n matter.
For example, if there is a better algorithm for 20 elements, it’s assumed that the difference is insignificant enough that it doesn’t matter. So, if an algorithm a is 5% better than algorithm b with 20+ items, but 50% worse for less than 20, it would take 220 items for the two to be equal. Then for every item over 220 algorithm a is better. Since we assume big numbers, a is “always” better than b.
In mathematical terms, this means we only have to deal with the order of an algorithm. What does this mean? If an algorithm’s speed is n^2+20*n+45, then the n^2 term is the limiting factor. While term 20*n matters a little when n is small, when n is 200, n^2 is 40000 while 20*n is 4000, less than 10% of the end result. Again, we’re dealing with big numbers, so the higher the n, the less the smaller order terms matter. Big O notation simplifies the math for us by ignoring other terms completely. So the Equation is O(n^2) in Big O. Even better, Big O ignores coefficients, so 20*n^2 and n^2 are considered the same, O(n^2). This is because the coefficients are typically related to the system the algorithm is running on. The same algorithm could have many different coefficients thanks to variations in systems and implementations, but it is no worse than O(n^2).
Let’s look at sorting, where there are many algorithms so we can get a better idea of how to compare Big O notation. Insertion Sort is an O(n^2) algorithm while Merge Sort is a O(n log n) algorithm. Since n log n is smaller than n^2 for large numbers, Merge Sort is always faster than Insertion Sort. If you don’t want to do any kind of math, you can use a function graphing tool to get a visual representation of which increases slower.
Unfortunately, proving an algorithm’s worse case is not always easy, especially for complex algorithms. Fortunately for us, we can get by with estimating based on known algorithms. When I talk about specific algorithms or methods, I’ll make sure to point out the Big O value. Unless you’re working on a formal proof, you can usually get by with a simple “This is similar to merge sort” and thus assume you’re dealing with n log n.
And that means the 3.4 showstopper, double responses to HTTPService have been fixed. You can get 3.5 direct from the source.. I don’t know what the deal is with the build date, or why they waited 3 months for a full 3.x release rather than a 3.4.1 patch release. Especially since the bug was fixed a week after 3.4 came out.
In the world of Flex, it’s easy see what is being done while ignoring how it happens. Thanks to data binding, Catalyst, and lots of handy libraries it’s easy to get into the “make it work” way of thinking. I’m not talking about how to add a button to a form, or how to display a dataset in a grid, I’m talking about how to manipulate that data or perhaps to pull information out of it.
At it’s simplest, an algorithm is a series of steps to accomplish a goal. For example, an algorithm to clean dishes would be:
But that algorithm isn’t the only way to wash dishes. Perhaps you have a dishwasher that takes care of these three steps, but requires an initial “rinse large food pieces off” step. So there are many different ways to accomplish the same goal.
When you create a function, you are creating an algorithm. The majority are simple and straightforward, so you probably don’t worry about them. But there’s the few that can become the entire focus of your time. You have a dataset to chew through, or you want to work in some nifty transitions. You could end up spending the majority of your time on a relatively small piece of code because that’s the heart of your application. This is where the code side of the component lifecycle gets stretched and where any improvement will have a significant impact.
So, as I can, I’m going to create a series of posts about algorithms. You’ll learn how to compare them, different approaches to solving a problem, and some terminology. Don’t worry if math scares you or if Wikipedia’s Analysis of Algorithms makes your head hurt. There are plenty of people like Dijkstra, Euler, and Turing who are smarter than me and already did the hard stuff. We’ll just learn from their hard work and go on our merry way. I’ll try and cover both practical stuff and some of the high-concept stuff that makes computer science people excited. Hopefully this will turn into an algorithms education for normal people.
The patch I mentioned way back in Let’s patch: Fun with Scientific Notation! was finally accepted and is now live in the 3.x branch. This fixes SDK-16241, which dealt with scientific notation.
I removed the Bug Quash badge since it’s misreporting, but this is my fourth patch accepted. I was hoping for 5, but if you followed the Bug Hunting series, my big fix for object comparisons was accepted with some caveats, meaning I didn’t get credit.
The 4 month delay is obviously due to the push for Flex 4. Though the trunk is somewhat off limits to community patches depending on your reading of the Submitting a Patch page on Adobe’s site. “We are starting Flex 4 development in /flex/sdk/trunk, so the trunk is in flux and patches submitted against it are less likely to be accepted for now.”