Enigmatic Thought

If you’ve just updated to Firefox 3.6.4 and use the Flash debug player, you may have noticed a problem. While you’re debugging, Firefox is killing you’re flash player session. Here’s the quick fix:

1. type about:config in the firefox address bar
2. search for dom.ipc.plugins.timeoutSecs
3. double click and change the value to -1

This will disable the hang detector that was added. It’s the same reason I don’t do any debugging in Chrome (alongside the lack of HttpFox). Sometimes a break point needs more than 10-15 seconds for me to figure out what’s going on. Check out more details here

Related Posts (generated):

• Altering Flash Builder’s new menu
• Firefox and flex
• Flex in Eclipse tips
• Clever Code is dangerous
• Bugquash badges fixed

When we last left you, we talked about Big O Notation and how we can use that to compare two algorithms. That was all theoretical though, dealing with infinite sets of data. In the real world, you’ll find that sometimes a “bad” algorithm is really the best for your application.

Lets track down an example from the world of video games. You’ve got a ship that flying around trying to dodge asteroids, and the ship could fire bullets to blow the asteroids up. Let’s lay out some ground rules as well. We don’t worry about the asteroids hitting each other, and bullets can’t hit each other or your own ship. There’s two separate problems here, and we’ll divide the collision system between them. In the first, we have a single ship and a one or more asteroids (when there are no asteroids, the level is over). In the second, there are zero or more bullets (maybe there’s a limit, but I’ll assume the Zero-One-Infinity Rule) and one or more asteroids.

On the surface these seem identical, there is a target set, and a set to hit the targets. So let’s solve the complicated one first (bullets & asteroids). There’s a many to many relationship, so during the first pass we could compare each bullet to each asteroid and see if we register a hit. Since we’re looping twice, the Big O notation would be O(b*a) with b = # of bullets, and 1 = # of asteroids. We can do better than that though, thanks to some clever thinking. Let’s sort our lists of asteroids and bullets in the order of the y (vertical) coordinate. We know we can sort using lots of O(n log n) algorithms (quicksort, mergesort, and whatnot) and then we can use the concept of merging to work our way down the 2 sorted lists looking for matching x coordinates. Here’s some pseudocode:

asteroidList.sortY()
bulletsList.sortY()
asteroid = 0;
bullet = 0
while (bulletList.length < bullet && asteroidList.length < asteroid)
{
	if (bulletList[bullet].y < asteroidList[asteroid].y)
	{
		bullet++;
	}
	else if (bulletList[bullet].y > asteroidList[asteroid].y)
	{
		asteroid++;
	}
	else // y is ==
	{
		//check for collision and do work to handle multiple objects on same y point
	}
}

Of course you’d have to build a way to handle multiple object on the same plane, but it’d work out to about O(a+b) assuming everything is evenly distributed on the y axis. Combined with the initial sorting, your Big O notation would be O(n log n) (either n=a or n=b depending on which is larger) because O(n log n) is “larger” than O(a+b), which would simplify to O(n).

So we’ve figured out the collision detection right? What about the ship and asteroids? Since we know one value, O(s*a) is really O(1*a)=O(a) and our “clever” solution is actually slower than the original! In fact, depending on the number of bullets, we may have slowed the simple O(b*a) solution down as well.

So you’re not programming a game, so why should you care? Throw out asteroids, ships, and bullets and look at two sets of data you’re trying to merge. A small list of data may just need a brute force solution rather than spending time figuring out a “really nifty algorithm” which may be horribly inefficient with the amount of data your working on. Maybe you should just have everything pre-sorted so you don’t take the O(n log n) penalty, then O(a+b) can be no worse than O(a*n). Regardless, don’t just look at the algorithm ans what it does, but look at the data that will be pushed around when you have to decide how to accomplish a task.

Related Posts (generated):

• Big O Notation
• Why Algorithms Matter
• Flash Debug crashing in Firefox?
• Bugquash badges fixed
• Scientific Notation Patch Accepted

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.

Related Posts (generated):

• Scientific Notation Patch Accepted
• Let’s patch: Fun with Scientific Notation!
• ObjectUtil.compare() Patch attempt number 2
• Hold the HTTPService: Flex 3.4 gets a showstopper
• ObjectUtil.compare() Patch 3 (with feeling!)

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.

Related Posts (generated):

• Why Algorithms Matter
• Flash Debug crashing in Firefox?
• Scientific Notation Patch Accepted
• The Flex Component Lifecycle
• Altering Flash Builder’s new menu

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.

Related Posts (generated):

• Scientific Notation Patch Accepted
• HTTPService bug crushed in 3.x branch
• Hold the HTTPService: Flex 3.4 gets a showstopper
• Let’s patch: Fun with Scientific Notation!
• ObjectUtil.compare() Patch 3 (with feeling!)