Re: Learning Fundamentals: Data Structures and Algorithm Analysis in Perl

[ELISHEVA]

In your list of uses of big O I think you left out one of the most common uses: a thumb-in-the-air order of magnitude. The idea is to put problems in the right ballpark, not to "prove" a particular level of complexity.

In practical coding situations, sometimes all we need is a ball park. In fact, precision can sometimes even confuse the issue. Take, for example, the post you dislike so much. I don't know that it really matters to that discussion whether something is O(log N), O(N) or even O(N!). What does matter is that a preferred test for emptiness happen in constant time rather than scale with the size of the data structure. A brief statement like "O(1) vs. O(N)" gets that point across much more clearly than a precise statement loaded with if, ands, and buts.

For the most part, the monks I see using big O do in fact know what it means and are aware of all or most of the issues involved in it. However, figuring out how to apply the theory to a particular problem is the challenge.

For example, constant factors can make the f(N) component of an algorithm essentially irrelevant. Variance and competition over system resources can make singleton runs of benchmarks very misleading. Both of those turned out to be issues in the thread you did not want to mention, and I think we all learned something from that concrete example. In fact, I think we learned more that way than we would have from a theoretical discussion.

Often times, when faced with a complex problem, posters will immediately leap to the conclusion that the problem is NP complete. Often this has to do with the failure to understand the mathematical logic of the problem. A notable example is magic squares where many posters tried a brute force solution over all possible 3x3 squares. Using simple algebra developed during the course of the thread it soon became clear that the problem actually required examination of a much smaller problem space. The mathematics needed to come up with an efficient algorithm for that problem was particular to the problem.

Those are but two examples, but I could point to many more. In general, I think it is more constructive to discuss matters like complexity in the context of a specific threads and specific problems.

As for being afraid that people would take your criticisms personally? I think that is only going to happen if you jump to conclusions about their general level of knowledge based on the way they handle a specific problem. No one likes to have generalizations made from specific mistakes. It isn't fair. People make mistakes. They overlook things. They speak in generalizations (or too much detail) when they shouldn't.

On the other hand, Monks who get insulted by challenges to their problem solving approach usually get dinged - they either grow up or go away. The regulars have been challenged more times than they can count - they aren't going to go up in flames because of yet another one.

The monkly way is to criticize a particular approach to a problem, rather than the person or their general knowledge. If you think there are theoretical concepts that may be misapplied or misunderstood, then feel free to discuss the concepts as they apply to the problem or provide links to general purpose treatments.

If you do think there is an overall weakness, a mediation might be a good choice, but I think it is probably better to do your homework first rather than just point out a problem and say "let's discuss". In my company whenever someone does that we say: mind your QRS - Query, Research, Suggest.

• Query means that most problems have a context and a background - any solution one proposes will go over much better if it is stated in a way that takes that into account. Or if that is not possible says, "maybe I'm missing something as a new/infrequent observer. I wonder why X seems so."
• Research means don't ask others to do one's homework. Find out what has been done before (e.g. other tutorials and meditations). Find out what resources are out there to address the problem.
• Suggest means come up with a list of recommendations along with their pro's and con's. In the PM context that means a thoughtful, well researched meditation that adds new knowledge or synthesizes existing resources in a creative way.

Best, beth

[tilly]

Very mild disagreement here with For the most part, the monks I see using big O do in fact know what it means and are aware of all or most of the issues involved in it.

I would say that most of the monks I see using it are aware of how it is used informally by hackers, but a very large fraction are unaware of the formal definition, and/or are unaware of several subtleties that come up fairly often. (I rather strongly suspect that most who are aware that the formal definition probably couldn't come up with a reasonable version of it on demand...)

For instance if someone says, "That's O(1), not O(n)" they are really thinking of big-Omega, not big-O. Because by the formal definition, anything that is O(1) is also O(n). However that's not how hackers informally use the term. And lots of them don't know that their informal usage is technically incorrect.

Furthermore hackers usually have an implicit "amortized average time, if things work like they are supposed to" thrown in that they are not even conscious of. Worse yet, if they were asked to really explain what they meant, most probably couldn't. For instance most of us accept that, "hash lookup is O(1)." Well actually that's the average case if your hashing algorithm is working properly. The worst case with most hash implementations is O(n). If your hashing algorithm isn't a good fit, you'll hit that worst case fairly often. And what about that "amortized" bit? Well if you accept that pushing an element is O(1), you've implicitly accepted the amortized bit. If you're doing Perl programming that's OK. If you're doing real-time programming however...

Then of course there is the glaring issue that scalability is often not what matters. For instance which is faster? Scanning a sorted list for an element, or doing a binary search? Despite O(n) vs O(log(n)), in a low-level language on modern CPUs, scanning is probably faster. Very few of us have a good sense for this kind of detail.

As you see there are a lot of issues and complications that come up in a more formal discussion. My suspicion is that a large fraction (and possibility the majority) of Perl hackers who throw around the term aren't really aware of those. They could learn it pretty easily, but don't know it off of the top of their heads. However I'd absolutely agree that their understanding is more than sufficient for a practical analysis of the kinds of problems that we programmers are usually likely to encounter.

[BrowserUk]

but a very large fraction are unaware of the formal definition

I think far too much is made about "formal definitions". Back when I did my formal CS education, I chose a multi-part long questionon big-O as my optional question. I passed the exam with distinction. Of course they don't tell you anything more than the overall scores, but I think I would probably have had to have scored perfectly on the four compulsuries to achieve that if I'd totally flunked the optional. Back then I could have, and probably did, give a formal definition of big-O and big Omega.

But over a 25 year career, I never once needed to repeat it. And nor has it ever been useful to me. But the education means that I do have a way of informally discussing algortihmic complexity in terms that many other programmers recognise and understand. So in that sense the knowledge of it is useful.

But in the real-world, when, as you point out, an O(n^2) algorithm in one language can out perform an O(n log n) in another; when memory allocation/reallocation costs can render a formally faster algorithm slower than a formally slower algorithm, because the latter is more cache friendly (eg. Mergesort versus QuickSort); and given multi-tasking OSs and mutli-core hardware renders static formal analysis iffy at best and an outright lie at worst; the usefulness of big-O is pretty much limited to discussion purposes only. A benchmark run many times under real-world or realistic conditions renders it mostly redundant.

A starting point, and a means of informal discussion, but little more.

[tilly]

When I speak of a significant portion of hackers, I am not speaking of any particular one. I am not surprised that you'd have learned the formal definition.

Although I have to disagree on how extreme your dismissal is. Absolutely big-O is useful as a starting point and means of informal discussion. However it also provides a framework for how to think about performance, and that can go a lot farther. Being aware of big-O has helped me predict how well real systems will scale, understand bottlenecks, and multiple times has given me a sense as to whether a given implementation's performance is reasonable, or whether a performance mistake needs to be tracked down.

[spectre9]

I completely agree that O(1) vs. O(N) does get a point across about the Hash emptiness being finite time. Where I was led astray was why O(*) was even mentioned versus ending said post after the first sentence.

Quite usefule reply... and therefore, but none of them, nor the original post methinks, could be considered 'worst case.'

Cheers, Patrick