Quote:
In my experience as a programmer, professionally, academically and otherwise, many considerable speed improvements are gained precisely by realizing that big-O performance is poor and using a better algorithm. In fact, this can make the difference between being able to run a program and not being able to run it at all!
I don't know why you say that picking a better big-O algorithm will "in many cases" result in worse running time -- do you have more examples of this? Of course there are special cases, like when you have particular constraints on the problem domain, but in general your statement seems quite wrong.
Quote: A common example is quicksort vs mergesort. Most beginning CS students know that quicksort is better. Why would anyone ever use merge sort? Although it has a worse average case, merge sort has a better worst case, making it ideal for presorted data. Further quicksort is great for in-memory data, but terrible for large data sets which cannot be stored on disk, which is why most database programs use variants on mergesort.
Sure -- and in this case, the algorithm choice is made because the problem domain is very particular. In general, it is still usually better to recommend quicksort over straight mergesort.
I'm not sure why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth. :-) It's all just part of the algorithm selection process once you start thinking about it.
I think I should differentiate; when it comes to picking an algorithm, I'm all for knowing its complexity and understanding why that is so. When it comes to optimization, I think you should still know the relevant big-O factors, but I contend that it's largely useless for optimization.
Why? Because perf optimization is about profiling, testing, understanding the bottlenecks, and knowing your hardware. Big-O tells you nothing about any of that. You ask why it's sinful premature optimization to look at big-O performance, but fine to look at things like where a data set is stored (RAM vs. disk), and so forth; I answer because looking at the big-O complexity tells you nothing about what the algorithm actually does or how it operates, where as looking at things such as where a data set is stored assumes a detailed knowledge of exactly what is happening and how hardware is affecting it.
This is why I object to statements which for instance, dismiss Fruchterman/Reingold because it has a base O(N^3) complexity. It's complexity alone tells us -nothing- about how useful it may be. It may take a million second or a millisecond for one node, it may be disk bound or cpu bound, we don't know.
The fact is, our problem domain is dealing with <100 nodes visible, and <10000 node maps (usually). This is a strongly CPU bound application, and depends heavily on the current CPU/FPU and very little on hardware bandwidth or seek times. Now that we know this, we can profile the algorithm, check which loops take longest, apply our knowledge of big-O, and modify the data structures to allow O(n log(n)). We can cut down on unneccesary power and trigonometric usage, etc...
Quote:
If you're looking at an algorithm whose average case is O(N^3), for example, and you know that your input size is large, then you really should consider if you have no choice but to use an O(N^3) algorithm because there necessarily will come a point where no amount of optimization trickery will help you speed up the algorithm.
I think this is exactly what I'm talking about. Before you look at the complexity, first you need to profile. Maybe the best case is O(1), maybe the average data size is <10, maybe there is a O(log(n)) algorithm elsewhere in your code with an average data size of 1000000. Maybe this is an algorithm that applies itself to caching extremely well, or maybe your algorithm is O(N^3) with a large data set, but its disk bound, and decreasing its time complexity won't help.
Assuming automatically that big-O is anything other than a vague guide to an algorithm's performance in a specific real-world case is a mistake to me. I don't want to sound like I don't care about categorizing algorithms' complexity, because I think this is an irreplacable and extremely important tool in a very broad and wide range of areas. Frankly, I'm usually a lot happier working in those areas than caring about perf :P But it's not a good metric when it comes down to the nuts and bolts in the specific area of perf optimization. |