Tuesday, December 30, 2008
Sunday, December 21, 2008
HD Tetris
Link.
I think the applet size is dependent on monitor resolution, I'm not sure. Here's what it looks like on my screen: linked for big.
I think the applet size is dependent on monitor resolution, I'm not sure. Here's what it looks like on my screen: linked for big.
Friday, December 19, 2008
Tuesday, December 16, 2008
Math ∩ Reality
CS.
I don't think I've ever had such an intense argument about Big O.
Specifically whether an algorithm that is performed polynomial time constitutes being efficient.
I take my opposition's argument to be as such, it is considered technically feasible to solve any problem of NP class complexity (see Cobham's Thesis), therefore it could be considered a threshold for defining efficiency. In other words, it's a necessary condition.
My position is that Big O is simply a tool for analysis. Since there's so much context involved, an algorithm can't be considered efficient just because it computes in polynomial time. That is, not sufficient and not even a necessary condition. I'm not going to strawman here, so let's assume whatever program in question isn't racking up unnecessary cycles with a do{ }while(i<99999) or something equally asinine like that.
Case 1: If an algorithm has worst case O(k^n), but the chances of the worst case are 1 in a thousand, it may still be practical to take it over something with with a fixed O(n^2) time. Plus, in real life you can often choose to avoid worst case scenarios. For instance, a set may be sorted initially with a Quicksort implementation, but additional elements are added by Insertion.
Case 2: Coefficients are omitted from Big O, that's understandable from a mathematical stand point. From optimizing the algorithm (not with respect to hardware, just to itself), you might shave off a fraction of the computational time, but if you switch processors from a 386 to a Yorkfield cluster, the time is going to be reduced by magnitudes. That is what the coefficient represents. But you can't ignore coefficients in real life. Say your hardware performs a certain operation much faster than others and you're getting bottlenecked, it might be worthwhile to organize small chunks of your input even with an exponential time function because you're going to gain back that time in the end. In similar fashion, say you're bottle necked by memory and not processing power, it might make sense to write something that takes O(k^n) computing power and O(n log n) memory as opposed to something that takes O(n^2) of both.
As a minor point, my opponent argues that in an infinite set, polynomial time will always trump exponential time and for small sets efficiency doesn't matter anyways. But see, efficiency isn't relevant for small sets because the coefficient is 10 to the power of such a large magnitude (unless you're using a Celeron LOLOL) that it dwarfs everything else. If the coefficient makes that big of an impact, then it stands to say there may still be a large set less than infinity that computes faster with a routine in exponential time than one in polynomial time, depending on how it takes advantage of the hardware.
And realistically speaking, if your set is large enough to seriously look at Big O and your best case is O(n^3), you're probably in trouble anyways. Not to say you're not just as screwed with O(k^n), but now I'm back at the shot in the head vs shot in the chest analogy (see: last post).
For the record, the debate was ended by, "you see, I don't care about real life".
1. I know both Insertion sort and Quicksort are polynomial time operations. What I'm saying is, the latter averages O(n log n) while the former averages O(n^2), yet the former remains more efficient in some cases.
2. I also know Big O usually only refers to worst case, but lets not miss the forest for the trees shall we?
3. That is not to say computational analysis is useless. That's like saying what's the point of ideal gas law if gases aren't ideal? Well, if you're looking at nitrogen at 1 atm, 20°C you can guess that it's going to be a fairly accurate model. Ramp it up 400atm though, and it might be a good idea to break out the compressibility charts. ;)
4. I just wanted to put that chem analogy there. The fact is, the majority of the time polynomial time is preferable to exponential time in every way and Big O holds. But that's not what I'm arguing against.
I don't think I've ever had such an intense argument about Big O.
Specifically whether an algorithm that is performed polynomial time constitutes being efficient.
I take my opposition's argument to be as such, it is considered technically feasible to solve any problem of NP class complexity (see Cobham's Thesis), therefore it could be considered a threshold for defining efficiency. In other words, it's a necessary condition.
My position is that Big O is simply a tool for analysis. Since there's so much context involved, an algorithm can't be considered efficient just because it computes in polynomial time. That is, not sufficient and not even a necessary condition. I'm not going to strawman here, so let's assume whatever program in question isn't racking up unnecessary cycles with a do{ }while(i<99999) or something equally asinine like that.
Case 1: If an algorithm has worst case O(k^n), but the chances of the worst case are 1 in a thousand, it may still be practical to take it over something with with a fixed O(n^2) time. Plus, in real life you can often choose to avoid worst case scenarios. For instance, a set may be sorted initially with a Quicksort implementation, but additional elements are added by Insertion.
Case 2: Coefficients are omitted from Big O, that's understandable from a mathematical stand point. From optimizing the algorithm (not with respect to hardware, just to itself), you might shave off a fraction of the computational time, but if you switch processors from a 386 to a Yorkfield cluster, the time is going to be reduced by magnitudes. That is what the coefficient represents. But you can't ignore coefficients in real life. Say your hardware performs a certain operation much faster than others and you're getting bottlenecked, it might be worthwhile to organize small chunks of your input even with an exponential time function because you're going to gain back that time in the end. In similar fashion, say you're bottle necked by memory and not processing power, it might make sense to write something that takes O(k^n) computing power and O(n log n) memory as opposed to something that takes O(n^2) of both.
As a minor point, my opponent argues that in an infinite set, polynomial time will always trump exponential time and for small sets efficiency doesn't matter anyways. But see, efficiency isn't relevant for small sets because the coefficient is 10 to the power of such a large magnitude (unless you're using a Celeron LOLOL) that it dwarfs everything else. If the coefficient makes that big of an impact, then it stands to say there may still be a large set less than infinity that computes faster with a routine in exponential time than one in polynomial time, depending on how it takes advantage of the hardware.
And realistically speaking, if your set is large enough to seriously look at Big O and your best case is O(n^3), you're probably in trouble anyways. Not to say you're not just as screwed with O(k^n), but now I'm back at the shot in the head vs shot in the chest analogy (see: last post).
For the record, the debate was ended by, "you see, I don't care about real life".
1. I know both Insertion sort and Quicksort are polynomial time operations. What I'm saying is, the latter averages O(n log n) while the former averages O(n^2), yet the former remains more efficient in some cases.
2. I also know Big O usually only refers to worst case, but lets not miss the forest for the trees shall we?
3. That is not to say computational analysis is useless. That's like saying what's the point of ideal gas law if gases aren't ideal? Well, if you're looking at nitrogen at 1 atm, 20°C you can guess that it's going to be a fairly accurate model. Ramp it up 400atm though, and it might be a good idea to break out the compressibility charts. ;)
4. I just wanted to put that chem analogy there. The fact is, the majority of the time polynomial time is preferable to exponential time in every way and Big O holds. But that's not what I'm arguing against.
Thursday, December 11, 2008
The road to all healing begins
...with just accepting that dy/dx is a fraction.
I know I've jeered my physics prof in the past for doing such a thing, but I'm seeing the benefits of his approach. For instance, now it doesn't take any special manipulations to find error, just multiply both sides by dx (or ∂x, depending)!
No more stupid math arguments with my roommate at 1 in morning! It's like I've fully declared my intention to ignore all proper conventions in favour of shortcuts and he gets the smug satisfaction that I'm not doing real math.
Instead I have stupid arguments about American automakers at 1 in the morning. Which ended with an analogy relating GM and Ford to a man getting shot in the head and a man getting shot in the chest, respectively.
Semantics.
They're both screwed.
As an addendum, my roommate is like a puritan when it comes to math. As in accepting nothing other than set theory to be "real" math. That's like saying Ruby isn't real programming because I'm not personally ferrying bits around like a deliveryman.
I know I've jeered my physics prof in the past for doing such a thing, but I'm seeing the benefits of his approach. For instance, now it doesn't take any special manipulations to find error, just multiply both sides by dx (or ∂x, depending)!
No more stupid math arguments with my roommate at 1 in morning! It's like I've fully declared my intention to ignore all proper conventions in favour of shortcuts and he gets the smug satisfaction that I'm not doing real math.
Instead I have stupid arguments about American automakers at 1 in the morning. Which ended with an analogy relating GM and Ford to a man getting shot in the head and a man getting shot in the chest, respectively.
Semantics.
They're both screwed.
As an addendum, my roommate is like a puritan when it comes to math. As in accepting nothing other than set theory to be "real" math. That's like saying Ruby isn't real programming because I'm not personally ferrying bits around like a deliveryman.
Subscribe to:
Posts (Atom)