03.04
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.
No Comment.
Add Your Comment