Roy Smith <r...@panix.com> wrote in news:roy- 92A049.08504216042...@reader1.panix.com:
> Imagine you've got a program which runs in O(N^2) > time. If you could find a way to reduce it to O(N), for an input set of > just 10 items, you would have speeded it up by a factor of 10! Compared > to upgrading your Python interpreter, you did 50-100 times better tuning > the algorithm. Now try to consider the implications of going from > O(N^2) to O(N) with 25,000 input items!
I believe you are making some unreasonable assumptions here. Remember that if I have an algorithm that is O(N^2) that is really just a shorthand for saying that it will have a running time a*N^2 + b*N * c where a, b, and c are constants but for sufficiently large N only the N^2 term matters.
Now imagine that you have a program that runs in O(N^2) time and you have 10 items. If a is 1 and b is 1000, the N^2 term doesn't start to dominate until you have at least 1000 items. If these are times in milliseconds, then your 10 item program would take ~10 seconds to run, but improving the algorithm from O(N^2) to O(N) (with the same value for b) would have no noticeable effect.
Yes, if you have 25,000 items then for my chosen values of a and b the O(N) algorithm is probably going to result in a significant speedup (unless it increases b by a factor of more than 26), but you can't just simplify this to say that O(N) is going to be better in all cases.
If you try to apply this to the real world you may find there are all manner of compromises to be made. The most obvious one is in sorting where a real implementation of an O(n log n) sort will adapt to using an O(n^2) sort on subsets of the data because it turns out that the dumb sorting techniques are faster until n gets quite large.
-- Duncan Booth dun...@rcp.co.uk int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3" "\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?
> In article <mailman.1050457621.2105.python-l...@python.org>, Mike C. > Fletcher wrote: > > Andrew Koenig wrote:
> > Okay, so now we have "The Practical Coder's Guide to big-O Notation" :) > > . We rock ;) , > > Mike
> You do, you know...c.l.p really does.
> I think I almost 'get it'. Except who or what decides what Big-O a > certain algorithm has. Is that by 'hunch' or by running benchmarks or > are there still other ways to recognize 'Big-O's (except for the > formal computations that I understand are not very common)?
It's been nearly forever since my compsci algorithms class so be gentle if I'm glaringly wrong :). Big O notation is a way to convey the magnitude of work that it takes for an algorithm to do it's job (ignoring any constant time). So, for a sufficiently large N, the work required for an algorithm is something like N or NlogN etc.. No one decides what order an algorithm is, it is an inherant property of the algorithm.
If you execute quicksort on a wide variety of sample sets of different sizes then measure and plot the processor time vs sample size, it will approximate the graph of NlogN. Therefore the algorithm has order NLogN. The same will apply to bubble sort (order N^2), etc.
On 05:06 AM 4/11/2003 -0400, python-list-requ...@python.org feed this fish to the sharks:
>- if you learn programming with Python and later have to use Java or >Visual Basic, it will be the most frustrating experience for the young >fellows.
Pardon my ignorance, but how could it be a frustating experience?
> On 05:06 AM 4/11/2003 -0400, python-list-requ...@python.org feed this fish > to the sharks: > >- if you learn programming with Python and later have to use Java or > >Visual Basic, it will be the most frustrating experience for the young > >fellows.
> Pardon my ignorance, but how could it be a frustating experience?
The frustration will arise from the non-availability of the various simple features that Python provides to make programming easier.
For a real example, consider the contortions I have to go through when writing VBScript ASP code for a client's project if I want a list (array) of strings. Where in Python I can write:
sarr = split("the quick brown fox jumps over the lazy dog")
Now imagine the further complexity when each element of sarr needs to have structure itself, remembering that VBScript has no data structure constructs except the array (well, I understand there's now a third-party module that lets you create collections or some similar object, but there's still no way to create an object with attributes).
In article <roy-92A049.08504216042...@reader1.panix.com>, Roy Smith wrote:
[snip excellent stuff]
Well, I'm amazed at, and grateful for, all the time and effort you guys put in. I also received an excellent reply by email. So a big thank you to all.
PterK
P.S. I agree that this would be a valuable resource on a webpage as Andrew suggested. It get's pointed out quite often that concatenating strings in loop is an expensive operation in python and I have always tried to keep that in mind but it is much nicer if you understand why...
-- Peter van Kampen pterk -- at -- datatailors.com
> For a real example, consider the contortions I have to go through when > writing VBScript ASP code for a client's project if I want a list (array) of > strings. Where in Python I can write:
>I believe you are making some unreasonable assumptions here. Remember that >if I have an algorithm that is O(N^2) that is really just a shorthand for >saying that it will have a running time a*N^2 + b*N * c where a, b, and c >are constants but for sufficiently large N only the N^2 term matters. >Now imagine that you have a program that runs in O(N^2) time and you have >10 items. If a is 1 and b is 1000, ...
Ah, the practical optimizer. We encounter so few of these in this day and age. :-)
> It also means that one doesn't bother distinction between logarithms > base 10, e, 2, etc.; O(ln n) ~ O(lg n) ~ O(lb n). Similarly, O(2^n) ~ > O(10^n) ~ O(e^n) too.
The second part of this isn't true. If a process f(n) has a running time T(N) for in input of size N, said process is O(N) if there exist constants "k" and "j" such that O(N)*k <= T(N) for all N>=j
While there does exist a constant (log(A)/log(B)) for which log_A(N)*k <= log_B(N) for all sufficiently large N, there is no constant for which (A**N)*k <= B**N for all sufficiently large N when B>A.
-- Christopher A. Craig <list-pyt...@ccraig.org> "Never let schooling get in the way of your education" Mark Twain
> On Wed, Apr 16, 2003 at 02:22:02PM +0000, Steve Holden wrote: > [...]
> > For a real example, consider the contortions I have to go through when > > writing VBScript ASP code for a client's project if I want a list (array) of > > strings. Where in Python I can write:
> > in VBScript I must resort to one of [nontested code follows]:
[...]
> Or, if my memory isn't failing me:
> sarr = Array("the", "quick", ... "dog")
Indeed, though that's new to me (never used VB, just the scripting version). Now let's create a dictionary-of-objects equivalent using the DictionaryOfObjects() function ;-)
> In article <mailman.1050457621.2105.python-l...@python.org>, Mike C. > Fletcher wrote: > I think I almost 'get it'. Except who or what decides what Big-O a > certain algorithm has. Is that by 'hunch' or by running benchmarks or > are there still other ways to recognize 'Big-O's (except for the > formal computations that I understand are not very common)?
Technically the only way to determine the O() for a particular algorithm is to do a complete mathematical analysis. One of the other posts has an excellent simple example. You can do comparative times for particular data sets, and fit a curve to the times, but that doesn't guarantee that the algorithm will behave the same way for some other set of data sets.
This mathematical analysis of an algorithm's behavior (and best-case, average, and worst-case performance) can be trivial. For example, x + 1 is O(1). Or it can be so complex that proving the exact behavior is a Ph.D. thesis, or even an unsolved problem.
> But these are not really 'algorithms'. Most algorithms are a lot more > complex even when reduced to it's essentials. I understand why > quicksort is better than bubblesort but I don't see an obvious way to > label quicksort O(??).
Everything's an algorithm :). Quicksort analysis isn't terribly complicated as these things go. There's got to be an analysis up on the web somewhere.
[...] > It's been nearly forever since my compsci algorithms class so be > gentle if I'm glaringly wrong :).
ditto.
[...]
> No one decides what order an algorithm is, it is an inherant property > of the algorithm.
... which implies that it must have been _proven_ (it's a theoretical system :-)
> If you execute quicksort on a wide variety of sample sets of different > sizes then measure and plot the processor time vs sample size, it will > approximate the graph of NlogN. Therefore the algorithm has order > NLogN. The same will apply to bubble sort (order N^2), etc.
[...]
A commonly held belief, but as I said, it has to be proven, not measured. Importantly, the statement entirely depends on the innocent phrase "wide variety of sample [data]" (which would be valid if you were trying to approximate the statistical mean of the algorithm). When measuring, most people (should be?) are interested in _expected_ performance however, which means you need a "representable sample" (of the domain), but even when well defined and acknowledged programmers/scientists/... have historically proven to be highly subjective when determining 'representable' <wink>. [Hint: you're assuming you're only sorting random data].
>I think I almost 'get it'. Except who or what decides what Big-O a >certain algorithm has. Is that by 'hunch' or by running benchmarks or >are there still other ways to recognize 'Big-O's (except for the >formal computations that I understand are not very common)?
I'll try to give a simple explanation. Big-O is the upper bound of the time it will take to complete the function.
There's usually a variable factor in determining how long an operation will take.
Inserting into a hash table: O(1) - constant time. This means that the amount of time it takes to insert into a hash table is not dependent on the size of the table. This is because the position to insert the item is calculated (the hash) and then inserted. This, of course, changes when there starts being collisions.
Inserting into the first free spot of an array: O(n) - linear time. n is the size of the array. This means when you cycle through the array you have to go through n items (at the most).
And it carries on. I forget exactly how to calculate them, but you can understand the simple ones.
Here's some really simple code to show different Big-O's
n = 24
# O(1) # constant time print n
# O(n) # linear time for x in range(0,n): print x
# O(n^2) # quadratic time for x in range(0,n): for y in range(0,n): print x, y
# O(x^n) # exponential time for y in range(0, x**n): print y
Keep in mind that Big-O is the *upper bound*. These all illustrate the maximum time. Any real code is most likely going to reach it's "destination" before it hits the end (though not always).
-- Hope this didn't make you more confused than ever, Ryan
> Peter van Kampen <n...@datatailors.xs4all.nl> wrote in message > <news:slrnb9q90a.mhg.news@datatailors.com>... > >I think I almost 'get it'. Except who or what decides what Big-O a > >certain algorithm has. Is that by 'hunch' or by running benchmarks or > >are there still other ways to recognize 'Big-O's (except for the > >formal computations that I understand are not very common)?
> I'll try to give a simple explanation. Big-O is the upper > bound of the time it will take to complete the function.
O() ::= The big-O notation gives an indication of the growth rate of a function. It identifies the dominant term of the function.
And, for the practically minded...
Rules of Thumb - A loop that processes each data item in turn is O(n). - A loop within a loop Do n Do m Is O(m*n) - If each data set is halved each time through a loop then there will be O(log2n) iterations. (log2n is the number of times you repeatedly half n to reach 1). - An algorithm that processes every subset of n data items has complexity O(2**n). - An algorithm that processes every permutation of n data items has complexity O(n!). - If the number of operations is the same whatever the number of data items then the complexity function does not depend on n. We say the operation has complexity O(1).
> This mathematical analysis of an algorithm's behavior (and best-case, > average, and worst-case performance) can be trivial. For example, x + > 1 is O(1). [...]
I would have thought it's O(log x), due to the possibility of carries.
-- Steven Taschuk stasc...@telusplanet.net "Study this book; read a word then ponder on it. If you interpret the meaning loosely you will mistake the Way." -- Musashi, _A Book of Five Rings_
> I believe you are making some unreasonable assumptions here. Remember that > if I have an algorithm that is O(N^2) that is really just a shorthand for > saying that it will have a running time a*N^2 + b*N * c where a, b, and c > are constants but for sufficiently large N only the N^2 term matters.
Not to dispute your general point, but a nit: O(n^2) doesn't imply a polynomial expansion such as you have above; the actual runtime could be, for example, 3n^2 + log n + 18/n. That is, the additional terms might be anything which (asymptotically) grows slower than n^2.
-- Steven Taschuk Aral: "Confusion to the enemy, boy." stasc...@telusplanet.net Mark: "Turn-about is fair play, sir." -- _Mirror Dance_, Lois McMaster Bujold
> I understand why the code is bad (copying the string each time in > memory as it grows). However, I've never understood the notation's > O(N) and O(N2)?
Others have given good explanations of the usual use of big-O notation, namely, to describe roughly how the running time of an algorithm relates to the size of its input. Imho this is actually a convenient but slightly sloppy way of speaking; strictly speaking one counts operations performed. Roy Smith's excellent post, for example, focusses on memory copy operations, essentially; that's a good choice for that problem, while counting string concatenations would not be, if we're interested in predicting runtime.
And you can use big-O notation for counting things other than operations. For example, it is correct usage to describe a trade-off as being between, say, an algorithm which runs in O(n) time but needs O(n^2) memory to do it, and an alternative which runs in O(n^2) time but only needs O(n) memory.
-- Steven Taschuk stasc...@telusplanet.net "Telekinesis would be worth patenting." -- James Gleick
> This mathematical analysis of an algorithm's behavior (and best-case, > average, and worst-case performance) can be trivial. For example, x + > 1 is O(1).
Or not so trivial. If x can be an arbitrary size integer, represented in memory as a chunk of bits, the value 'n' for the number of bits, and a sign flag, then addition could be O(n) == O(log(x)). Eg, suppose x = 1111111111111111111111111111111111111111 add 1 to get = 10000000000000000000000000000000000000000 so 49 bits were affected.
Peter van Kampen wrote: > I think I almost 'get it'. Except who or what decides what Big-O a > certain algorithm has. Is that by 'hunch' or by running benchmarks or > are there still other ways to recognize 'Big-O's (except for the > formal computations that I understand are not very common)?
It's just mathematics. You look at the behavior of the algorithm or data structure as the number of elements gets very large (in order to drown out fixed-cost or second-order effects).
> for example
> bigO_N(i): > for n in xrange(i): > print n
> Would be O(N) right?
That's right. It iterates over each element, and that takes O(n).
> bigO_N2(i,j): > for n in xrange(i): > for o in xrange(j): > print i,j
> This would be O(N**2)? Actually O(i*j) I suppose but if i==j N**2 > applies.
That's right also. You're looking at the case where the number of elements being processed -- even if there are multiple different sets -- grows large. In this case you're iterating over two lists, but for each list you're iterating over the other, so as i, j -> oo the behavior is O(n^2).
> But these are not really 'algorithms'. Most algorithms are a lot more > complex even when reduced to it's essentials. I understand why
quicksort is better than bubblesort but I don't see an obvious way to label quicksort O(??).
But there is always some set of behaviors that are core to the algorithm, and that's what you look at as the number of elements goes to infinity. Bubble sort is O(n^2), but quicksort is O(n ln n).
One also often speaks of worst case and average cases (this ties into what people mean by "amortized O(f(n))" behavior). For instance, take finding an element in a sorted binary tree. The average case is O(ln n), but the worst case (if the tree is maximally uneven) is O(n).
Adding an element to the end of a dynamically resizing vector is average case O(1), but worst case O(n), but since this worst case happens on average n times, we call it "amortized O(1)" behavior.
The big-O notation is one of those things that's really highly mathematical (particularly if you want to talk about things rigorously), but it's also something that's vitally important for even novice programmers to understand very well when they're using algorithms to solve complex problems that need to be scalable.
-- Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/ __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE / \ The only source of knowledge is experience. \__/ Albert Einstein Bosskey.net / http://www.bosskey.net/ A personal guide to online multiplayer first person shooters.
"Christopher A. Craig" wrote: > Erik Max Francis <m...@alcyone.com> writes:
> > Similarly, O(2^n) ~ O(10^n) ~ O(e^n) too.
> The second part of this isn't true. If a process f(n) has a running > time T(N) for in input of size N, said process is O(N) if there exist > constants "k" and "j" such that O(N)*k <= T(N) for all N>=j
> While there does exist a constant (log(A)/log(B)) for which > log_A(N)*k <= log_B(N) for all sufficiently large N, there is > no constant for which (A**N)*k <= B**N for all sufficiently large N > when B>A.
[scribbles on paper]
Right you are, thanks for that important correction. The ratio of two logarithmic functions with different bases is a constant, but the ratio of two exponential functions with different bases is a different exponential function, e^(k n), where k is the difference in the natural logarithms of the two original bases. So indeed, O(a^n) !~ O(b^n) for a != b.
Good catch!
-- Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/ __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE / \ The only source of knowledge is experience. \__/ Albert Einstein Bosskey.net / http://www.bosskey.net/ A personal guide to online multiplayer first person shooters.
Donnal Walter wrote: > I am a physican first and programmer second. I've never taken a course > in computer science, and I do not know the meaning of O(N). OTOH, just > from following comp.lang.python I think I have a pretty good idea why
> s += str(i)
> would be a bad idea. Nevertheless, I certainly would not be opposed to > deepening my understanding. (PythonIAN is great, BTW.)
I came in late. If we're talking about schools, I'm not sure whether we're talking about colleges and adult ed, or high school, or elementary school. Are we talking about teaching people who know nothing about programming?
If a 3rd grader wrote the s += str(i) or s = s+str(i) I would be pretty impressed. I don't expect them to understand O() notation. I wouldn't be to thrilled to see it in professional code. I don't expect that it would make it through the PEPs. But it would be expressing the basic idea, and then later it could be explained why it is so awfully slow on the big loops.
Maybe not too bad for 5th or 6th grade, since they're far from writing any professional code. You tolerate more with rank beginners, and you correct it in time.
Hi,all Does "execl", or whatever this family, support redirection of output? Say, I have a script: ( on my Linux7.2,C shell environment,with python2.2.1)
On Wed, 2003-04-16 at 21:24, Tim Ottinger wrote: > Donnal Walter wrote: > > I am a physican first and programmer second. I've never taken a course > > in computer science, and I do not know the meaning of O(N). OTOH, just > > from following comp.lang.python I think I have a pretty good idea why
> > s += str(i)
> > would be a bad idea. Nevertheless, I certainly would not be opposed to > > deepening my understanding. (PythonIAN is great, BTW.)
> I came in late. If we're talking about schools, I'm not sure whether > we're talking about colleges and adult ed, or high school, or elementary > school. Are we talking about teaching people who know nothing about > programming?
It's also a question of what you're trying to teach. Something that has always impressed me with Logo is that it's more of a teaching philosophy, and a language goes with it. The intention behind Logo isn't to teach programming... rather, programming is a medium in which to teach all sorts of other great stuff.
I personally believe that programming is *the* way pre-algebra and algebra should be taught. Logo shows it works very well for geometry as well. But you really have to get rid of the idea that you're teaching programming -- it does the children a disservice anyway, because programming is a rather niche skill in the larger picture. When you're teaching *with* programming, big-O notation and many other programming notions are just a distraction.
> Maybe not too bad for 5th or 6th grade, since they're far from writing > any professional code. You tolerate more with rank beginners, and you > correct it in time.
I'd go further -- if you're not trying to teach them to become programmers it's not a matter of tolerating, it's completely okay to be inefficient. It'd be like criticizing a student's handwriting on the caption they made for a picture in art class, or criticizing the aesthetic of a graph made for algebra.
Ian Bicking wrote: > It's also a question of what you're trying to teach. Something that > has > always impressed me with Logo is that it's more of a teaching > philosophy, and a language goes with it. The intention behind Logo > isn't to teach programming... rather, programming is a medium in which > to teach all sorts of other great stuff.
And, I might point out, Logo really gets a bad rap by the general populace as a "toy" language that just involves little turtles running around like silly things. In actuality, Logo was originally designed for abstract manipulation of symbols (_logo_ means "word" in Greek); the turtle graphics stuff came later. Logo is in fact a fun little cousin of the Lisp family.
-- Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/ __ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE / \ Can I walk with you / 'Till the day that my heart stops beating \__/ India Arie Polly Wanna Cracka? / http://www.pollywannacracka.com/ The Internet resource for interracial relationships.
Yu Wang wrote: > Hi,all > Does "execl", or whatever this family, support redirection of output? > Say, I have a script: ( on my Linux7.2,C shell environment,with > python2.2.1)
|
