Keep It Simple, Stupid | |
PerlMonks |
Re: Mathematics eq CompSciby BrowserUk (Patriarch) |
on May 02, 2005 at 07:15 UTC ( [id://453154]=note: print w/replies, xml ) | Need Help?? |
I think that the mathematical symbolism used in the description, exploration and characterisation of algorithms from a formal CS perspective is frequently unhelpful. Besides that characterising one algorithm as O(log n) and another as O(n) often completely obscures that the former must be implemented at a higher, less efficient level than the latter, such characterisations often have unwritten (or legalpoint) riders like "in the general case", "given equal speed memory access", or "ignoring cache coherency". They also almost always assume unbounded, constant performance, memory; generalised (often properly random) datasets; and idealised, uniform, single-tasking operating environments. The real-world constraints often include bounded-RAM with much slower secondary storage sourcing and spillage; biased datasets with reducable, non-influencing commonalities; and pre-emptive, multi-tasking (and multiplicitous) operating environments with unquantifiable coexisting & competing demands. Whilst some of the more CS-favoured algorithms (sorts, shuffles, searches etc.) have been studied in depth for the influence of things like cache coherency, these studies again often make the preassumption that the hardware running the algorithm is entirely dedicated to the running of the algorithm. Once you place that algorithm onto hardware that can, at any given point in the algorithm, completely destroy the cache conherency by task switching to an entirely different process, most of the benefits extractable by tailoring the algorithm to maximise cache coherency go out of the window. Even when programming at a level where the effects of machine level "built-in" routines versus high-level user-coded algorithms does not mean a ratio of 10s or 100s to 1 performance advantage of the former over the latter (Perl), the percentage of code written that actually fits into that set of well-analysed algorithms is very small, maybe 10% to 20% at best. Most real-world code is dominated by interactions with external events. User inputs, shared devices and databases, chaotic networks and the omnipresent contention for cpu and other resources. Whilst we all benefit from highly tuned sorts and tree-traversal algorithms when we need them, the benefits derived from their tuning, in the reality of our tasks spending 50%, 70% or even 90% of their time task-swapped or waiting on IO, is usually much less than those ascribed to them via intensive studies performed under idealised conditions. And to answer your question. Yes, it is possible to describe algorithms without formal mathematic notation, though these tend to require much more careful, wordful construction. One of the benefits of such wordful, less specialist construction is that more minds are likely to see the flaws. The problem with formal symbolisms is that they tend to become more and more specialist as they evolve to deal with higher and higher levels of abstraction. Whilst many thousands, maybe 100s of 1000s have read much of Knuth's tomes, the percentage of those that really understood his notations is much less, and many of those that did are only writing code in academia. Just as there are only a handful of people in the world that will ever see the flaw in Wiles proof---if there is one. It falls to a pretty select group of people to find the limits, flaws and constraints on Knuth's work. Beyond the typos that he pays a peice rate for, I wouldn't mind betting that he personally has made more corrections to his own work than all the informal users of it combined. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco. -- Rule 1 has a caveat! -- Who broke the cabal?
"Science is about question the status quo. Questioning authority".
The "good enough" maybe good enough for the now, and perfection maybe unobtainable, but that should not preclude us from striving for perfection, when time, circumstance or desire allow.
In Section
Meditations
|
|