Promoting Python
Kevin Altis
sessions at PyCon that were relevant:
http://www.python.org/cgi-bin/moinmoin/MarketingPythonOpenSpace
http://www.python.org/cgi-bin/moinmoin/PythonOrgWebsiteRedesignOpenSpace
I would like to invite you to join the marketing-python list if you're
interested in contributing ideas or would like to help implement plans to
increase the user-base of Python and make sure that you never have to answer
the question "What is Python?" ever again. If you have marketing, PR, or
business experience that you can share that is a big plus!
http://pythonology.org/mailman/listinfo/marketing-python
One of the top priorities is to improve the python.org website. A mailing
list has been created to coordinate activities. We will need volunteers to
help make python.org a better site. If you have experience building large
web sites, are an experienced web designer, or can help with the nuts and
bolts of the web site maintenance your contributions to making a better
python.org will be quite welcome.
http://mail.python.org/mailman/listinfo/pydotorg-redesign
I recommend that you take time to read the marketing-python and
pydotorg-redesign archives, at least the posts from the last few weeks to
catch-up with the discussions.
Welcome to the revolution!
ka
---
Kevin Altis
al...@semi-retired.com
http://radio.weblogs.com/0102677/
Thomas Guettler
> One of the hot topics at PyCon was Promoting Python.
> I would like to invite you to join the marketing-python list if you're
> interested in contributing ideas
> ...
[cut]
I think python is a very good language for education. You could get in
contact with local schools.
thomas
--
Thomas Guettler <gue...@thomas-guettler.de>
http://www.thomas-guettler.de
Harald Massa
> I think python is a very good language for education. You could get in
> contact with local schools.
Thomas, I am not so sure about this.
Yes, I love Python, and it is the most elegant programming language I
ever met.
Python gives you objectoriented, functionorientet and imperative
programming paradigm in one fitting package.
Python does not bother beginners with a million typecasts. Very great.
For education there are small drawbacks:
- 50% of all exercises "to teach programming" are already solved in the
standard-library or are a method of a buildin object / are allready build
in the core language
- 45% of these exercises are solved within "the python cookbook",
available also online
- 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.
Anyway, I regret not having met Python earlier in my programming career.
Jason Smith
> For education there are small drawbacks:
>
> - 50% of all exercises "to teach programming" are already solved in the
> standard-library or are a method of a buildin object / are allready build
> in the core language
>
> - 45% of these exercises are solved within "the python cookbook",
> available also online
Holey moley! And all this time, I had it in my Safari queue!
> - 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.
I don't think so. Particularly with computer science courses, I think it's
often the case that students are required to re-implement features that
come with a library. For example, consider a course where students
implement their own data structures in C++, and then they implement
iterators to mimic the STL. (I actually took this course, so there's your
existence proof.) If a student uses code from a book, or say some GNU
code, then that's simply academic dishonesty; and any good teacher would or
should catch these things as part of their general grading techniques.
Where I think python would be great is at the lower educational levels. I
think we all agree (heh) that programming as part of a general computer
literacy course should be necessary for any high-school diploma today, just
like Chemistry or such. And in that arena, as a student's first exposure
to programming, Python shines.
I mean, if we're all studying sorting, and I turn in
a = [ 'this', 'is', 'a', 'list' ]
a.sort()
well then clearly I just got an F. But it's not Python's fault.
----== Posted via Newsfeed.Com - Unlimited-Uncensored-Secure Usenet News==----
http://www.newsfeed.com The #1 Newsgroup Service in the World! >100,000 Newsgroups
---= 19 East/West-Coast Specialized Servers - Total Privacy via Encryption =---
Nick Vargish
Nick
--
#include<stdio.h> /* SigMask 0.3 (sig.c) 19990429 PUBLIC DOMAIN "Compile Me" */
int main(c,v)char *v;{return !c?putchar(*v-1)&&main(0,v+ /* Tweaks welcomed. */
1):main(0,"Ojdl!Wbshjti!=obwAqbusjpu/ofu?\v\1");} /* build: cc -o sig sig.c */
Mads Orbesen Troest
> Yes, I love Python, and it is the most elegant programming language I
> ever met.
I agree it's mostly elegant, but the OO features are clumsy in my oppinion
(coming as a professional developer from other languages). Not as bad as
Perl's bless-a-dictionary-into-being-a-class retro-fitting hack, of course,
but really; all the self me here and self me there is - to me at last -
exceedingly clumsy and a constant source of frustration.
Regards,
/\/\\ads Orbesen Troest
Lee Harr
>
> I mean, if we're all studying sorting, and I turn in
>
> a = [ 'this', 'is', 'a', 'list' ]
> a.sort()
>
> well then clearly I just got an F. But it's not Python's fault.
>
Why? This looks good to me.
Well... ok. I see your point. But if you are studying sorting algorithms,
a.sort() should definitely be on the list :o) And then I think almost
any student will see the advantage of a.sort() over a page of intricate code.
What I mean is that students should first learn how to use the tools before
they are required to know how to make them.
I think going the other way around just encourages the poor practice of
everyone creating their own incompatible and (very often) buggy private
libraries.
Peter Hansen
>>> import this
-Peter
Bryan L. Fordham
> What I mean is that students should first learn how to use the tools before
> they are required to know how to make them.
Absolutely. This is how my calculus teach in HS taught us: he'd show us
the really complicated way, then show us the shortcut.
It would make perfect sense for a teacher to require you to use
something more than list.sort() if you're studying sorting... but after
that, why make you write your own sorting routines if what's provided
works just fine?
--B
Kevin Altis
"Thomas Guettler" <pan-new...@thomas-guettler.de> wrote in message
news:pan.2003.04.11.09...@thomas-guettler.de...
> On Fri, 11 Apr 2003 05:34:35 +0200, Kevin Altis wrote:
>
> > One of the hot topics at PyCon was Promoting Python.
> > I would like to invite you to join the marketing-python list if you're
> > interested in contributing ideas
> > ...
>
> [cut]
>
> I think python is a very good language for education. You could get in
> contact with local schools.
Thanks for the suggestion Thomas. Kirby Urner, who is quite active on
edu-sig has already agreed to lead the charge in promoting Python in
education. Suggestions can be passed onto Kirby via the edu-sig mailing list
and as progress is made it will get posted to edu-sig and the
marketing-python lists.
http://mail.python.org/mailman/listinfo/edu-sig
The first step is collecting information on what is already being done with
Python. We have a pretty big list of links to schools, educators, and
education-related projects using Python. Additional info is always welcome.
http://mail.python.org/pipermail/edu-sig/2003-April/002765.html
Kirby and I will be organizing that into categories to make it easier to
use. Kirby is also editing the edu-sig page on python.org.
http://www.python.org/sigs/edu-sig/
ka
yaipa h.
> >>> import this
>
OT: Sure glade the reader to your reply knows what you are talking about.
Otherwise he might be a little taken aback. ;^))
Peter Hansen <pe...@engcorp.com> wrote in message news:<3E96D270...@engcorp.com>...
Andrew Dalke
> > but really; all the self me here and self me there is - to me at last -
> > exceedingly clumsy and a constant source of frustration.
Peter Hansen
> >>> import this
... from the interpreter and you'll see a list of 'Pythonic' guidelines.
More specifically, "explicit is better than implicit". See the 'self'
and you know where the variable comes from. Compare to C++
where you don't know (without some looking) if the variable is
an attribute or a variable in the compilation unit.
Andrew
da...@dalkescientific.com
yaipa h.
> standard-library or are a method of a buildin object / are allready build
> in the core language
Funny when my US Army .45 cal pistol class champion uncle taught me to
shoot he told me it was better to learn the right way first so not to
develop the bad habits in the first place. I find that today's "program
in a box" college courses bread more bad habits then they actually teach
good programming practices. Learning from the Python modules is a fine
way of learning the right way first.
Also, programming at the entry level is a bit like your basic hand tools. Life
becomes greatly more interesting/easier if you know how to use them CORRECTLY.
All be it most of us have no desire to become carpenters, auto mechanics, &c.
Python is an excellent language to teach early on to find those that love
the discipline and educate the rest on how to use today's version of a hand
tool CORRECTLY.
> - 45% of these exercises are solved within "the python cookbook",
> available also online
>
Ditto
> - 50% of all exercises "to teach programming" are already solved in the
> standard-library or are a method of a buildin object / are allready build
> in the core language
Harald Massa <cpl.1...@spamgourmet.com> wrote in message news:<Xns935A6D886AC5cp...@62.153.159.134>...
Paul Watson
were taught how to drive a car?
Surely you must have studied the basic physics of fluid mechanics before you
could be successful in the WC.
We need to teach students correct design priciples to build something
greater than what already exists. We will never get very far if we require
everyone to start with a quark or atom. Yes, of course we need some people
who design silicon and create microcode. They will learn the low-level
details what they need to know as they need it. Knowing great design and
organization principles will enable them to make the most of it.
"Harald Massa" <cpl.1...@spamgourmet.com> wrote in message
news:Xns935A6D886AC5cp...@62.153.159.134...
Jp Calderone
> Were you required to learn how to refine crude oil into petrol before you
> were taught how to drive a car?
>
> Surely you must have studied the basic physics of fluid mechanics before you
> could be successful in the WC.
>
> We need to teach students correct design priciples to build something
> greater than what already exists. We will never get very far if we require
> everyone to start with a quark or atom. Yes, of course we need some people
> who design silicon and create microcode. They will learn the low-level
> details what they need to know as they need it. Knowing great design and
> organization principles will enable them to make the most of it.
>
+1.
Programming and computer science are related, but not the same. Teaching
someone computer science and expecting this to make them a good programmer
is a mistake.
Jp
--
Lowery's Law:
If it jams -- force it. If it breaks, it needed replacing anyway.
--
up 22 days, 15:01, 3 users, load average: 1.05, 1.11, 1.16
Kyler Laird
>- 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.
After reading this thread, I am not sure that we're all making
what I consider a vital distinction. When we talk about
"teaching Python" are we talking about "teaching students how
to program with Python as the primary language" or are we
"teaching students how to solve problems with Python as the
primary tool"?
If we're just teaching the use of Python as a way to solve
problems (my particular interest), it doesn't matter that the
student will be frustrated when going to another language -
heck, it's a mark of how appropriate Python is that it's more
difficult to achieve the same results with another language.
OTOH, if we're teaching programming (I have a Scheme course
going now.) it's a whole different ballgame. There I feel it
is vital to understand the basics and be able to build them
from scratch.
(I recently used Python matrix operations to solve some GIS
problems. I know terrifyingly little about either but I was
able to stumble through and get the job done with surprising
ease. Do I really understand what I did? No. Could I code
it in C? Probably not. Was it adequate to solve my needs?
Yes! What a great tool!)
I recall sub teaching "Computer Science" at a middle school a
few years ago. The task for the day was to follow step-by-
step instructions on running MS Word to edit and print a file
on a floppy disk. We don't all define "Computer Science" the
same.
So...I think you probably all understand the difference
between Python as a tool and Python as a base language for
teaching programming. I'd just like to see a more deliberate
distinction so that we don't confuse the goal of "Python and
Schools".
Thank you.
--kyler
Lee Harr
> OTOH, if we're teaching programming (I have a Scheme course
> going now.) it's a whole different ballgame. There I feel it
> is vital to understand the basics and be able to build them
> from scratch.
>
> So...I think you probably all understand the difference
> between Python as a tool and Python as a base language for
> teaching programming. I'd just like to see a more deliberate
> distinction so that we don't confuse the goal of "Python and
> Schools".
>
I have a feeling that going beyond using Python as a great tool
for getting work done with computers is probably out of scope
for most schools, but I can certainly imagine a small percentage
of students signing up for an essentially college-level comp-sci
course in their last year or two of school.
Ideally, the students would already be quite proficient at using
the tools provided by Python to get things done, and could use
those tools to prototype the lower-level details of the tools
themselves as a learning exercise.
Then they might go in to the "comparative anatomy" of learning to
do the same things with C or C++ or Java. And, of course the best
part is that they have all of the CPython and Jython source code
so they can see how experienced programmers have solved these
problems. They might even study how the implementations have
changed historically. (Open source software... wow.)
Harald Massa
>Harald Massa wrote:
>> Yes, I love Python, and it is the most elegant programming language I
>> ever met.
> Mad wrote:
> all the self me here and self me there is - to me at last - exceedingly
> clumsy and a constant source of frustration.
Mad, I wrote that I love Python. Not: Python is perfect.
Especially if you look at OO: OO with Python is great. Adding/Removing
Attributes on the fly, inspecting objects in the living system, getting
documentation while running....
And then there is the self. It is not bad. It does not hurt your OO
programming. It's like the nipples of a beautifull girl turning into a
different color during intercourse. You think it's wired for the first
time. You wonder, why is this necessary.
But sex with her is perfect. She is beautifull. She knows to dress and to
behave with your geeky friends and with your business friends, handles
situation in gym as well as in the opera.
There is only that strange colour her nipples are turning when she's
nearing orgasm.
And this strange colour of her nipples is like Pythons "self": it takes
time to love it.
It's not that great astonishing for var in iterator: do something. It's
not the perfect ass of the girl, with that you fall in love immediately.
It's the strange colour the nipples turn during sex. But after some time
you learn to love this colour ... you see this colour and know: she is
hot.
Same happened to Python, self and me: Someday I recognized, that for
nested classes self is a godsend: you can access the outerclass self with
total ease, just name it differently:
class miriam:
def __init__(self, numberofshoes):
self.shoes=numberofshoes
def goshopping(self):
class necessaryitems:
def __init__(innerself):
if self.shoes > 10:
innerself.ni=["wine","grapes","cheese"]
else:
innerself.ni=["shoes","wine","strawberrys"]
def shoppinglist(innerself):
for a in innerself.ni:
print a
myneci=necessaryitems()
myneci.shoppinglist()
a=miriam(8)
a.goshopping()
Doing similiar accesses without "SELF" is a real pain in the ass. It's
like finding out what tearns a girl on without the colourchanging
nipples. Once you learned to love it, you never will stop your loving.
best self-wishes
Harald
Jason Smith
> It would make perfect sense for a teacher to require you to use
> something more than list.sort() if you're studying sorting... but after
> that, why make you write your own sorting routines if what's provided
> works just fine?
I agree.
Still, what's wrong with this?
a.the_sort_that_i_learned_last_week()
Anyway, this decision is all up to the teacher of course. So then we see
that Python gives a teacher flexibility depending on the focus of study.
And that sounds like another big plus to me.
Alex Martelli
> On Fri, 11 Apr 2003 10:48:49 +0200, Harald Massa wrote:
>
>> Yes, I love Python, and it is the most elegant programming language I
>> ever met.
>
> I agree it's mostly elegant, but the OO features are clumsy in my oppinion
> (coming as a professional developer from other languages). Not as bad as
Interesting, because I also came to Python as a professional developer
from other languages (C++ above all) and the utter *ELEGANCE* of Python's
OO features was one of the things that hooked me to it irretrievably.
> Perl's bless-a-dictionary-into-being-a-class retro-fitting hack, of
> course, but really; all the self me here and self me there is - to me at
> last - exceedingly clumsy and a constant source of frustration.
Let's put it this way: in C++ you have to use this->foo SOME of the
time (to avoid running afoul of extremely subtle and deuced bugs
in some templates) but it's quite hard to predict exactly when you'll
need to do it. With Python, you ALWAYS use self.foo (one character
less than C++'s this->foo!-) and thus your code is more regular and
uniform, there is no risk of ugly conventions such as naming member
variables m_this and m_that (popular in several C++ shops), no bugs
due to accidental local "hiding" of a member variable by a local one
(I've taught and consulted on C++ long enough to have seen THAT
happen many, MANY times -- and not to idiots, either... rather, to
very good professional programmers!) -- a HUGE amount of conceptual
AND pragmatical simplification of your life.
If that's the worst aspect of Python, then how must the rest be?-)
You can gain most (not quite all) of these advantages in C++ by
using the this->foo way of accessing instance variables -- this
also makes your C++ and Python code more similar, and helps you get
into the good habit. And if any C++ bigot ever challenges you,
explain that this ensures optimal behavior of your code should it
ever be turned a template under ANY circumstances (it's true...!-).
Alex
Alex Martelli
>> [cut]
>> I think python is a very good language for education. You could get in
>> contact with local schools.
>
> Thomas, I am not so sure about this.
>
> Yes, I love Python, and it is the most elegant programming language I
> ever met.
>
> Python gives you objectoriented, functionorientet and imperative
> programming paradigm in one fitting package.
>
> Python does not bother beginners with a million typecasts. Very great.
>
> For education there are small drawbacks:
>
> - 50% of all exercises "to teach programming" are already solved in the
> standard-library or are a method of a buildin object / are allready build
> in the core language
>
> - 45% of these exercises are solved within "the python cookbook",
> available also online
Why are these "drawbacks"? I see them as opportunities to:
-- have users develop/learn simple solutions to see how some things
could be done then compare them with "professionally developed"
approaches
-- then use the professional stuff as building-blocks for higher level
problems (closer to applications of interest to the student)
When I taught programming I did show, for example, how to build an
integer multiplication function with a loop on top of addition and
shift-left -- even though the programming language in use DID have a
built-in multiplication operator, I thought that was instructive
(for my target audience -- engineering students in their 3rd year
of university). Then, of course, we moved on to using multiplication
as a "built-in". Similarly, later in the course, I showed how to
implement saxpy in bare Fortran -- then matrix multiplication on
top of saxpy -- etc, etc -- and as the course progressed we then
used excellent library implementations of those BLAS tools, not the
one we had put together "naively" (the subtext: I thought, and still
think, that engineers should have a feel for how things work inside,
BUT also resist the temptation to reinvent the wheel when good tools
are available in libraries).
Isn't the situation here quite similar?
> - 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.
If you learn arithmetic with arabic notation and later have to use
roman numerals (try long division with them one of these days... but
even multiplication is cumbersome enough!-), it will be at least as
frustrating. So, should we teach arithmetic using roman numerals
rather than arabic ones?-)
Any time you learn a good tool and later are forced to use inferior
tools it can be frustrating. If the prospect of such forced use of
inferior tools is realistic, then the course that teaches the better
tool might choose to spend some time explaining how one can manage
to get things done anyway even with the inferior ones; it's not a
sound motivation to avoid teaching the better tool, anyway!
> Anyway, I regret not having met Python earlier in my programming career.
Sure -- me too. Though "from pain we learn" (Pindarus), and maybe I
wouldn't have learned quite as much without the pain of dealing with
lower-level languages throughout my career, still I'd probably have
gotten more done in my life;-).
Alex
Courageous
>And then there is the self. It is not bad. It does not hurt your OO
>programming. It's like the nipples of a beautifull girl turning into a
>different color during intercourse. You think it's wired for the first
>time. You wonder, why is this necessary.
Possibly it is necessary for the same reason that many coding standards
(such as in C++, using Microsoft's approach), one must put m_ before all
class member attributes. What that coding standard amounts to is an
example of the standards writer actually _fighting_ the existence of
implicit this in C++. In other words, they are using attribute-naming
to disambiguate between class attributes and local variables of the same
name. In Python, this problem does not exist, because "m_" is spelled
"self".
C//
Courageous
>Let's put it this way: in C++ you have to use this->foo SOME of the
>time (to avoid running afoul of extremely subtle and deuced bugs
>in some templates) but it's quite hard to predict exactly when you'll
>need to do it. With Python, you ALWAYS use self.foo (one character
>less than C++'s this->foo!-) and thus your code is more regular and
>uniform, there is no risk of ugly conventions such as naming member
>variables m_this and m_that (popular in several C++ shops), no bugs
>due to accidental local "hiding" of a member variable by a local one
>(I've taught and consulted on C++ long enough to have seen THAT
>happen many, MANY times -- and not to idiots, either... rather, to
>very good professional programmers!) -- a HUGE amount of conceptual
>AND pragmatical simplification of your life.
Alex Martelli demonstrates once again a fine talent at burying the
hatchet. I rather doubt there can *be* much of a reply to this fine
retort.
C//
Michael Robin
This would all be icing on the cake of consistency, except when
seemingly innocent constructs like:
class C:
x = 42
def foo(): self.x += 1
exist that can lookup & bind a name in a two different scopes
(probably not intended) - from a class to an instance.
If you really want this behavior, you should have to say "self.x = C.x
+ 1" if x is not bound (the first time that foo() is executed) and the
current version thereafter. (Or even better, put set self.x = C.X in
__init__)
This violates
In the face of ambiguity, refuse the temptation to guess
Explicit is better than implicit
and perhaps:
...that way may not be obvious at first unless you're Dutch.
There are really two explict vs. implict issues here - the
class-scoped
variable and the binding to self.x without explicit knowlege that "x"
should in fact be a member of C, given that there are no decl's and
the slot is currently unbound -- but the latter is an important and
useful part of Python parlance, __slots__ and varible-name typos
notwithstanding.
Rule#1 is of course in the eye of the beholder, and there must be a
balance between explicit uglyness and implicit beauty (or is it the
other way around?) - but in this case I think we'd vote for the extra
typing for the class accessor, just as we don't mind "self.".
thanks, mike
"Andrew Dalke" <ada...@mindspring.com> wrote in message news:<b76ult$plu$1...@slb5.atl.mindspring.net>...
Alex Martelli
...
> class C:
> x = 42
> def foo(): self.x += 1
No doubt you intend foo to have a self argument, right?
> other way around?) - but in this case I think we'd vote for the extra
> typing for the class accessor, just as we don't mind "self.".
It's not a matter of extra typing, but of changing semantics!!!
>>> class C:
... x = 42
... def foo(self): self.x = self.x + 1
...
>>> class D:
... x = 42
... def foo(self): self.x = D.x + 1
...
>>> class subC(C): x = 23
...
>>> class subD(D): x = 23
...
>>> aa = subC(); aa.foo(); print aa.x
24
>>> aa = subD(); aa.foo(); print aa.x
43
>>>
See the difference? By switching to D.x instead of self.x, you
inhibit the data override in class subD from working as intended --
you cannot any more make a subclass have a different default /
starting value for the x attribute of its instances that is
different from that in the base class.
You need to know which semantics you desire, but in most cases
allowing data overriding adds flexibility at no cost -- thus it's
what you should be doing by default. Use self.attribute, NOT
someclass.attribute, even in methods written inside someclass,
in order to allow data overriding to work.
Furthermore, would you be happy calling aa.__class__.foo(), if
aa.foo didn't automatically go get the attribute from the class
when it doesn't find it in the instance? I doubt so. Automatic
delegation of attribute access from instance to class is THE
prime mechanism of Python's O-O, after all. So what horrid kludges
would you suggest, to ensure that accessing self.x delegates to
the class (when instance self has no specific attribute x) just
in some cases but not in others...?
MUCH better as we have it today -- simpler, more practical,
more flexible, more regular and general -- ALWAYS delegate
the lookup when the attribute isn't found right in the instance.
How could piling exceptions on top of this simple rule make
things any better?!
Alex
sik0fewl
> Bryan L. Fordham wrote:
>>It would make perfect sense for a teacher to require you to use
>>something more than list.sort() if you're studying sorting... but after
>>that, why make you write your own sorting routines if what's provided
>>works just fine?
>
> I agree.
>
> Still, what's wrong with this?
>
> a.the_sort_that_i_learned_last_week()
>
> Anyway, this decision is all up to the teacher of course. So then we see
> that Python gives a teacher flexibility depending on the focus of study.
> And that sounds like another big plus to me.
Yeah. That's very interesting. For example, one week you could teach
your students something that involves/requires sorting (can't think of
any decent examples off the top of my head) and not actually teach them
sorting until the next week.
--
Ryan
Aahz
Paul Watson <pwa...@redlinec.com> wrote:
>
>We need to teach students correct design priciples to build something
>greater than what already exists. We will never get very far if we
>require everyone to start with a quark or atom. Yes, of course we need
>some people who design silicon and create microcode. They will learn
>the low-level details what they need to know as they need it. Knowing
>great design and organization principles will enable them to make the
>most of it.
While there's some truth to that, try explaining why the following code
is a Bad Idea to someone who has no basic understanding of CS:
s = ''
for i in range(1000000):
s += str(i)
Knowing the difference between O(N) and O(N^2) is critical to writing
even the simplest programs. OTOH, I do agree with you that focusing on
programming as a craft is more important to being a programmer than
learning CS.
--
Aahz (aa...@pythoncraft.com) <*> http://www.pythoncraft.com/
This is Python. We don't care much about theory, except where it intersects
with useful practice. --Aahz, c.l.py, 2/4/2002
Alex Martelli
> In article <v9e21m...@corp.supernews.com>,
> Paul Watson <pwa...@redlinec.com> wrote:
>>
>>We need to teach students correct design priciples to build something
>>greater than what already exists. We will never get very far if we
>>require everyone to start with a quark or atom. Yes, of course we need
>>some people who design silicon and create microcode. They will learn
>>the low-level details what they need to know as they need it. Knowing
>>great design and organization principles will enable them to make the
>>most of it.
>
> While there's some truth to that, try explaining why the following code
> is a Bad Idea to someone who has no basic understanding of CS:
>
> s = ''
> for i in range(1000000):
> s += str(i)
I will gladly accept the challenge, if we can agree on the details to
determine whether I've won or lost the bet. What I require is somebody
with real, earnest *interest* in *understanding* this stuff -- I'll
gladly undertake to supply all necessary *background*, but I have no
idea on how to awake real interest in somebody whose motivation for
learning is just "serving time" or some vague hope of getting a good
paying job (and that would be just as much of a problem, whether the
subject was "CS", "programming", or "artichoke farming techniques").
If the interest is there, and enough Python background to understand
exactly what this program snippet DOES, then in about one or two
hours of face to face instruction I can give a model that will allow
the student to predict this snippet's disastrous performance and
compare it to the expected performance for, e.g.,
s = ''.join([str(i) for in in range(1000000)])
It's not rocket science (that's _another_ thread...;-) -- at this
level, it's really simple arithmetic, a decent mental model of "an
abstract underlying machine", AND an interest in understanding this.
> Knowing the difference between O(N) and O(N^2) is critical to writing
> even the simplest programs. OTOH, I do agree with you that focusing on
> programming as a craft is more important to being a programmer than
> learning CS.
I'm not dissing CS (though I could well have some fun dissing it on
some other thread...!-), I'm claiming that one can become a rather
effective programmer in Python with only those modest, approximate CS
concepts that it's feasible to explain within a first programming
course (to _interested_ students...). For example, while we keep
mentioning big-O ("worst-case"...), what we're really USING most of
the time is really big-Theta ("_typical_ case", _expected_ performance).
Except in hard real-time programming, hardly anybody ever does more
sophisticated analysis than "_expected_ performance" during the design
of actual programs...
Alex
Peter van Kampen
> Aahz wrote:
>
>> In article <v9e21m...@corp.supernews.com>,
>> Paul Watson <pwa...@redlinec.com> wrote:
>>>
>>>We need to teach students correct design priciples to build something
>>>greater than what already exists. We will never get very far if we
>>>require everyone to start with a quark or atom. Yes, of course we need
>>>some people who design silicon and create microcode. They will learn
>>>the low-level details what they need to know as they need it. Knowing
>>>great design and organization principles will enable them to make the
>>>most of it.
>>
>> While there's some truth to that, try explaining why the following code
>> is a Bad Idea to someone who has no basic understanding of CS:
>>
>> s = ''
>> for i in range(1000000):
>> s += str(i)
>
> I will gladly accept the challenge, if we can agree on the details to
> determine whether I've won or lost the bet. What I require is somebody
> with real, earnest *interest* in *understanding* this stuff -- I'll
> gladly undertake to supply all necessary *background*, but I have no
> idea on how to awake real interest in somebody whose motivation for
> learning is just "serving time" or some vague hope of getting a good
> paying job (and that would be just as much of a problem, whether the
> subject was "CS", "programming", or "artichoke farming techniques").
I would gladly volunteer to be that somebody, although I realize it
won't happen (Practicallity beats geograpy ;-)) But I think you'll be
surprised about the number of people who *would* want to understand
the basics without necessarily (re-)entering university for a
CS-course. Let me tell you my background, perhaps it can serve as an
example.
I am a programmer by accident. I love the pleasure of 'creating' when
writing programs/scripts/whatever. I studied English literature but I
have toyed with computers over the years, mostly as a means to
store/retrieve stuff my brain (sadly) keeps forgetting (that's why I
have always been interested in databases).
Thanks to BASIC I learned on a Commodore 64 and dBase I learned on my
parents computer, back in the 1980's I found myself faced with the
opportunity/neccesity (as I said, totally by accident) to develop an
MS-Access-application in 1999 (a long story I won't bother you with).
After that was finished I was rather hooked (again after almost 10
years of hardly touching a computer, couldn't afford on either). Once
I learned to connect databases to the internet I could make a living
out of it (my re-discovery of the computer coincided with the
.com-hype), but I could not afford to keep up with Microsofts
relentless 'upgrading' so I have gradually moved to linux over the
past 2 years. Now I do mostly php/mysql-stuff and try to learn python.
I do not understand discussions about O(N) en O(N^2) and would be very
interested to learn such things. I have bought 'Python in a Nutshell'
and I love it how you explain about tokens, identifiers, keywords and
so on. Very few (if at all) 'general purpose' textbooks take the
trouble to explain stuff like that.
> If the interest is there, and enough Python background to understand
> exactly what this program snippet DOES, then in about one or two
> hours of face to face instruction I can give a model that will allow
> the student to predict this snippet's disastrous performance and
> compare it to the expected performance for, e.g.,
>
> s = ''.join([str(i) for in in range(1000000)])
>
> It's not rocket science (that's _another_ thread...;-) -- at this
> level, it's really simple arithmetic, a decent mental model of "an
> abstract underlying machine", AND an interest in understanding this.
So +1 for an article/book. I think you could write another best-seller
explaining this and similar basic things most CS-students take for
granted while there are many more users of python (and many other
high-level languages) who use it just to get their jobs done...
PterK
--
Peter van Kampen
pterk -- at -- datatailors.com
Donnal Walter
Me, too, Peter. +1 on the article/book as well.
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.)
Donnal Walter
Arkansas Children's Hospital
mindwrapper.org
Greg Brondo
> In article <v9e21m...@corp.supernews.com>,
> Paul Watson <pwa...@redlinec.com> wrote:
>
>>We need to teach students correct design priciples to build something
>>greater than what already exists. We will never get very far if we
>>require everyone to start with a quark or atom. Yes, of course we need
>>some people who design silicon and create microcode. They will learn
>>the low-level details what they need to know as they need it. Knowing
>>great design and organization principles will enable them to make the
>>most of it.
>
>
> While there's some truth to that, try explaining why the following code
> is a Bad Idea to someone who has no basic understanding of CS:
>
> s = ''
> for i in range(1000000):
> s += str(i)
>
> Knowing the difference between O(N) and O(N^2) is critical to writing
> even the simplest programs. OTOH, I do agree with you that focusing on
> programming as a craft is more important to being a programmer than
> learning CS.
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)?
Thanks,
Greg Brondo
Jordan McCoy
representing the execution time of programs, and in particular,
algorithms that operate over a set of data. The more complete definition
is thus:
The order of an algorithm is O(f n), if a function f and a constant k
exists such that k * f(n) is not more then the execution time of the
algorithm, assuming n is a suitable problem set.
The goal of algorithm development is to achieve O(f n) [or O(n)
abbreviated] as this represents constant execution time; each addition
to the problem set adds a constant amount of time to the execution time.
So, an algorithm that takes, for example, 1 second for n=1 would take
100 seconds for n=100, and so forth.
However, most algorithms can't achieve this: larger problem sets
increase algorithmic complexity and therefore increase execution time at
a greater then constant rate. Two examples:
1. The common but inefficient bubble sort has an order of O(n^2). Since
the bubble sort ends up comparing each set element multiple times to
multiple elements, a sort where n=1000 will require nearly 500,000
comparsions. While the math is somewhat more complex and boring, this
means that each addition to the problem set will result in an
exponential time increase.
2. The more efficient quick sort has an order of O(n * log2 n). Worse
then constant time, but much better then exponential time. Generic
sorting algorithms (those that don't rely on knowing pattern information
inherent in the data) rarely improve upon logarithmic time.
You can find more by searching on 'Order Notation.'
Jordan McCoy
> --
> http://mail.python.org/mailman/listinfo/python-list
>
Mike C. Fletcher
...
>
> 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)?
...
Here's a crack at explaining it:
Characterisation of an algorithm's (as distinct from an
implementation's) performance in relation to the size of the input
set. Normally of interest in determining the
scalability/suitability of a particular algorithm. The static (e.g.
setup) and proportional (e.g. implementation) factors in the
algorithm are factored out under the assumption that they are
swamped by the relative effects of the size of the input set as that
goes to infinity.
Common examples of big-O performance types:
* O(1) -- time is linear, that is, it takes the same amount of time
to do something regardless of how large the input set is.
* O(log N) -- time grows as the log of N, (for those who don't
remember high-school math, this means that it grows very slowly
compared to N).
* O(N) -- time grows linearly as the size of the set grows (e.g.
process every item in the set in turn)
* O(N log N) -- see O(N) and O(log N), basically, you do an amount
of work tied to the size of the whole set for every stage in an O(
log N ) operation (this is comparatively rarely discussed in my
experience).
* O(N**2) O(N**3) etceteras -- time grows as an exponent (e.g.
2,3,3.4,10) of the size of the set, so you get geometric explosion
of running time as set size increases. These algorithms tend to
fail on even small N values.
You can have all sorts of fun learning how to combine and re-factor the
equations to get a final big-O notation, but for the most part,
practical coders can get away with recognising and avoiding O(N**X)
where X > 1 situations. Recognising the underlying patterns in O(log N)
(binary searches and the like), and O(1)-ish situations is useful as
well, as they provide very good general scalability. The calculus of
big-O notations is just a convenient shorthand for people doing rigorous
analysis AFAICS.
Keep in mind that the setup and constant factors of the algorithm are
factored out of the equations. Something which is O(1) may be slower
than O(N**3) for all practical values of N if the setup time for the
O(1) algorithm approaches the age of the universe. Similarly, two
algorithms which are O(N), but with vastly different constant factors
(implementations) may have dramatically different running times.
HTH,
Mike
_______________________________________
Mike C. Fletcher
Designer, VR Plumber, Coder
http://members.rogers.com/mcfletch/
Jp Calderone
Big-O is just a way to formally describe the complexity of an algorithm.
It tends to only be applied to the most complex (and therefore most
expensive) portion, and all the lesser parts are ignored. It is almost
always in terms of some variable, usually (but not always) one with an
obvious meaning. N above refers to the number of times the concatenation is
performed. So O(N) simply means the algorithm has linear complexity - that
is, the runtime cost of running this algorithm grows directly with the
number of concatenations performed. O(N**2) would indicate quadratic
complexity - the runtime costs grow with the square of the number of
concatenations performed.
It also occassionally makes sense to talk about the best case, the average
case, and the worst case complexity. For example, quick-sorting an almost
sorted list can take much longer than quick-sorting one ordered such that
the partitions are always exactly at the center of each segment being
examined. The former of these cases is the worst case and the latter is the
best case. In practical programming, as I believe someone else has
mentioned in this thread, often only the average case is generally
considered.
Also note that hidden things can affect the complexity of algorithms.
With a malloc-dependant algorithm, such as string concatenation, while your
algorithm may be O(N) or O(N**2), the algorithms you depend on may increase
the overall complexity. While you would still talk about your algorithm
having some complexity, the actual runtime performance might vary
significantly from this, and vary significantly from environment to
environment, where the hidden complexity changes due to different library
implementations. For this reason, the practical use of Big-O notation is
fairly limited (IMHO).
Hope this helps,
Jp
--
http://catandgirl.com/view.cgi?90
--
up 26 days, 15:02, 4 users, load average: 0.29, 0.10, 0.02
Chad Netzer
> Greg Brondo wrote:
> Here's a crack at explaining it:
Good job. I have a few corrections and minor additions.
> * O(1) -- time is linear
You meant "time is constant". The algorithm requires the same number of
operations regardless of input size.
> * O(N log N) -- see O(N) and O(log N), basically, you do an amount
> of work tied to the size of the whole set for every stage in an O(
> log N ) operation (this is comparatively rarely discussed in my
> experience).
Really? Some of the most important classes of algorithms are O( N log N
), specifically, many common sort algorithms. Also, there are many of
these algorithms that have degenerate cases that become O( N**2 )
algorithms, with naive implementations or just by the nature of the data
set, and it is important to be wary of this phenomenon.
Also, one further class that is import to know is O( 2**N ), such as the
brute-force solution to the "travelling salesman problem". These are
much, MUCH worse than O( N**2 ) algorithms, and even today can rarely be
computed for problems sets much larger than 100 (whereas O( N**2 )
problem sets can grow to thousands or perhaps even millions and still be
practically solved). Rather than computing "solutions" with these types
of algorithms, it is required to instead come up with "close-enough" or
"best guess" type algorithms that CAN be computed practically on large
data sets.
--
Chad Netzer
(any opinion expressed is my own and not NASA's or my employer's)
Andrew Koenig
Mike> implementation's) performance in relation to the size of the input
Mike> set. Normally of interest in determining the
Mike> scalability/suitability of a particular algorithm. The static (e.g.
Mike> setup) and proportional (e.g. implementation) factors in the
Mike> algorithm are factored out under the assumption that they are
Mike> swamped by the relative effects of the size of the input set as that
Mike> goes to infinity.
Also, big-O notation always refers to an upper bound, not an estimate
that might be high or low. So, for example, every quantity that is
O(N) is also O(N log N), but the reverse is not true.
Mike> Common examples of big-O performance types:
Mike> * O(1) -- time is linear, that is, it takes the same amount of time
Mike> to do something regardless of how large the input set is.
O(1) doesn't mean linear, it means bounded by a constant. That is,
if the running time of an algorithm is O(1), it means that there exists
a time interval t such that the algorithm always finishes in time < t.
Mike> * O(log N) -- time grows as the log of N, (for those who don't
Mike> remember high-school math, this means that it grows very slowly
Mike> compared to N).
You can also think of O(log N) as being no worse than proportional to
the number of digits in N.
Mike> * O(N) -- time grows linearly as the size of the set grows (e.g.
Mike> process every item in the set in turn)
Mike> * O(N log N) -- see O(N) and O(log N), basically, you do an amount
Mike> of work tied to the size of the whole set for every stage in an O(
Mike> log N ) operation (this is comparatively rarely discussed in my
Mike> experience).
Many sorting algorithms are O(N log N).
Mike> * O(N**2) O(N**3) etceteras -- time grows as an exponent (e.g.
Mike> 2,3,3.4,10) of the size of the set, so you get geometric explosion
Mike> of running time as set size increases. These algorithms tend to
Mike> fail on even small N values.
Mike> You can have all sorts of fun learning how to combine and
Mike> re-factor the equations to get a final big-O notation, but for
Mike> the most part, practical coders can get away with recognising
Mike> and avoiding O(N**X) where X > 1 situations. Recognising the
Mike> underlying patterns in O(log N) (binary searches and the like),
Mike> and O(1)-ish situations is useful as well, as they provide very
Mike> good general scalability. The calculus of big-O notations is
Mike> just a convenient shorthand for people doing rigorous analysis
Mike> AFAICS.
O(N**1.5) is often bearable.
Mike> Keep in mind that the setup and constant factors of the
Mike> algorithm are factored out of the equations. Something which is
Mike> O(1) may be slower than O(N**3) for all practical values of N if
Mike> the setup time for the O(1) algorithm approaches the age of the
Mike> universe. Similarly, two algorithms which are O(N), but with
Mike> vastly different constant factors (implementations) may have
Mike> dramatically different running times.
Right.
--
Andrew Koenig, a...@research.att.com, http://www.research.att.com/info/ark
Roy Smith
> You can have all sorts of fun learning how to combine and re-factor the
> equations to get a final big-O notation, but for the most part,
> practical coders can get away with recognising and avoiding O(N**X)
> where X > 1 situations.
Indeed. Lest people think this is of academic interest only, let me
describe a situation we had at my company recently.
We've got something which scans a directory (an O(N) process). It's
supposed to happen once every time the program is run. Somebody goofed
in coding, and moved it into the loop that happens once every input
file, not once per run. Now it's an O(N^2) process.
Nobody noticed it in testing because we only tested it with maybe 100
files. Then one of our customers ran it with 25,000 files (a perfectly
reasonable thing to do). Whoops :-)
Steve Holden
> Aahz wrote:
[...]
> > Knowing the difference between O(N) and O(N^2) is critical to writing
> > even the simplest programs. OTOH, I do agree with you that focusing on
> > programming as a craft is more important to being a programmer than
> > learning CS.
>
> 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)?
>
an algorithm. If an algorithm is O(N) and your code runs in 10 seconds on a
list of 100 elements then you might expect it to run in 30 seconds on a list
of 300 elements - in other words, the run time is proportional to N, the
input size.
If the algorithm were O(N^2) then the run time could be expected to increase
with the SQUARE of the input size, meaning that an input of 200 elements
would take 40 seconds and an input of 300 elements would take 90 seconds.
The O() notation is a way of describing algorithmic performance without
getting stuck in the real world: it's assumed that for large enough N the
order effects will dominate, leaving any "trivial" variations in timing lost
in the noise. Thus it's a useful way to predict *roughly* how a given
algorithm will scale.
regards
--
Steve Holden http://www.holdenweb.com/
How lucky am I? http://www.google.com/search?q=Steve+Holden&btnI=1
Python Web Programming http://pydish.holdenweb.com/pwp/
Greg Ewing (using news.cis.dfn.de)
> The order of an algorithm is O(f n), if a function f and a constant k
> exists such that k * f(n) is not more then the execution time of the
> algorithm
Just a few corrections:
I think you mean "the execution time of the algorithm is not
more than k * f(n)".
> The goal of algorithm development is to achieve ... O(n)
> ... as this represents constant execution time;
No, constant time is O(1) -- i.e. completely independent
of n. You're talking about linear time.
> 1. The common but inefficient bubble sort has an order of O(n^2). ...
> each addition to the problem set will result in an exponential time
> increase.
That's called polynomial time, not exponential. Exponential time
is O(a^n) for some a, which is even worse.
> 2. The more efficient quick sort has an order of O(n * log2 n). Worse
> then constant time, but much better then exponential time.
Again, I think you mean polynomial. Although it's better than
exponential time, too!
By the way, you can just write that as O(n * log n). The base
of the log is irrelevant, since it only changes things by a
constant factor.
--
Greg Ewing, Computer Science Dept,
University of Canterbury,
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg
Chad Netzer
> We've got something which scans a directory (an O(N) process). It's
> supposed to happen once every time the program is run. Somebody goofed
> in coding, and moved it into the loop that happens once every input
> file, not once per run. Now it's an O(N^2) process.
>
> Nobody noticed it in testing because we only tested it with maybe 100
> files. Then one of our customers ran it with 25,000 files (a perfectly
> reasonable thing to do). Whoops :-)
I have unit tests that actually try to detect these things using
regressions and t-tests. For example, I have an implementation of a
numerical algorithm that I know is supposed to be O(N). In my tests, I
time the result of the algorithm with varying input sizes (ie. different
N), and do a quadratic regression (like a linear regression, but with a
term for x**2).
My assumption is that the x**2 term should have a coefficient near zero
(ie. zero "curve" to the regression). I then use a t-test to verify
this assumption, using a few runs on random data. Set the confidence
level fairly low, and it seems to do a good job of detecting if I
accidentally make a O(N**2) algorithm, rather than the expected O(N)
(with very few false positives).
Fairly quick and easy to implement (given existing t-test and regression
toolks available in stats.py and Numeric)
Anton Vredegoor
>Also, one further class that is import to know is O( 2**N ), such as the
>brute-force solution to the "travelling salesman problem". These are
Although it's important to not set too severe limitations I have the
impression this salesman is underestimating the problem.
>>> def fac(n):
... return reduce(operator.mul,range(2,n+1),1)
...
>>> fac(10)
3628800
>>> 2**10
1024
Anton
Mike C. Fletcher
>Mike> Characterisation of an algorithm's (as distinct from an
>Mike> implementation's) performance in relation to the size of the input
>Mike> set. Normally of interest in determining the
>Mike> scalability/suitability of a particular algorithm. The static (e.g.
>Mike> setup) and proportional (e.g. implementation) factors in the
>Mike> algorithm are factored out under the assumption that they are
>Mike> swamped by the relative effects of the size of the input set as that
>Mike> goes to infinity.
>
>Also, big-O notation always refers to an upper bound, not an estimate
>that might be high or low. So, for example, every quantity that is
>O(N) is also O(N log N), but the reverse is not true.
>
I seldom seem to see people invoking that part of the definition, though
it's definitely it.
Mostly people seem to talk about the best, average and worst-case
performance as if the O notation was relevant in each case, though IIUC
the worst-case would be the "real" O description. That is, the O
notations seem to be commonly used as shorthand notation for "constant
running time", "linear running time", "quadratic running time"
etceteras. Bad people, bad :) .
>Mike> Common examples of big-O performance types:
>
>Mike> * O(1) -- time is linear, that is, it takes the same amount of time
>Mike> to do something regardless of how large the input set is.
>
>O(1) doesn't mean linear, it means bounded by a constant. That is,
>if the running time of an algorithm is O(1), it means that there exists
>a time interval t such that the algorithm always finishes in time < t.
>
>
Yup, I'd meant to write constant and brain-fog occluded the shore
...
>You can also think of O(log N) as being no worse than proportional to
>the number of digits in N.
>
Good way of describing it.
...
>Mike> re-factor the equations to get a final big-O notation, but for
>Mike> the most part, practical coders can get away with recognising
>Mike> and avoiding O(N**X) where X > 1 situations. Recognising the
>
>
...
>O(N**1.5) is often bearable.
>
Good point.
...
Okay, so now we have "The Practical Coder's Guide to big-O Notation" :)
. We rock ;) ,
Mike C. Fletcher
>On Tue, 2003-04-15 at 13:32, Mike C. Fletcher wrote:
>
>
>>Greg Brondo wrote:
>>
>>
...
>> * O(1) -- time is linear
>>
>>
>
>You meant "time is constant". The algorithm requires the same number of
>operations regardless of input size.
>
>
Yup, absolutely correct, though in my defense, a horizontal line is
linear too ;) .
Don't post when tired (I just took a nap :) )!
>> * O(N log N) -- see O(N) and O(log N), basically, you do an amount
>> of work tied to the size of the whole set for every stage in an O(
>> log N ) operation (this is comparatively rarely discussed in my
>> experience).
>>
>>
>
>Really? Some of the most important classes of algorithms are O( N log N
>), specifically, many common sort algorithms.
>
Ah, but I never took comp-sci, so I never got into those cool "what's
the best sort algorithm" debates ;) . Most of the debates I've gotten
into this way have been around choices such as binary trees vs. hash
tables, so that's probably skewed my experience.
...
>Also, one further class that is import to know is O( 2**N ), such as the
>brute-force solution to the "travelling salesman problem". These are
>much, MUCH worse than O( N**2 ) algorithms, and even today can rarely be
>computed for problems sets much larger than 100 (whereas O( N**2 )
>problem sets can grow to thousands or perhaps even millions and still be
>practically solved). Rather than computing "solutions" with these types
>of algorithms, it is required to instead come up with "close-enough" or
>"best guess" type algorithms that CAN be computed practically on large
>data sets.
>
>
Cool. Haven't come across an algorithm described as such, though I'd
guess there've been a few that matched it over the years.
Thanks for all the clarifications and corrections,
Erik Max Francis
> Also, one further class that is import to know is O( 2**N ), such as
> the
> brute-force solution to the "travelling salesman problem". These are
> much, MUCH worse than O( N**2 ) algorithms, and even today can rarely
> be
> computed for problems sets much larger than 100 (whereas O( N**2 )
> problem sets can grow to thousands or perhaps even millions and still
> be
> practically solved). Rather than computing "solutions" with these
> types
> of algorithms, it is required to instead come up with "close-enough"
> or
> "best guess" type algorithms that CAN be computed practically on large
> data sets.
Note also (I'm sure you know this, Chad, I'm just elaborating for the
general benefit of everyone reading), since big-O notation represents
the behavior of algorithm complexity as the number of elements tends
toward infinity, it means that only the "biggest" function counts.
e.g., something that might scale as n (n + 1) = n^2 + n -- for instance,
having a collection of n elements and selecting all pairs i, j where i
!= j -- only is written as O(n^2), since as n -> oo, n^2 grows much
faster than n.
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.
There's also amortized notation, where on average you'd expect a certain
type of behavior but occasionally it will be another. For instance,
adding an element to the end of a dynamically resizing vector (like a
list in Python) is amortized O(1), since typically the operation will
take constant time, but occasionally (like when you're at the end of the
vector's capacity and it needs to be resized) it will take O(n).
Amortized is when you expected it to take O(f(n)), but only about every
n operationss, so one calls it "amortized O(f(n)/n)"; in this case, the
worst case is O(n), which should only happen every n operations, so you
speak of "amortized O(n)" (n/n = 1).
As Roy Smith mentioned, this is not merely of academic interest,
although formally defining it takes knowledge of calculus. It is
vitally important that you know the complexity of the algorithms you're
using and how they'll interrelate to avoid scalability problems.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ I want a martini that could be declared a disaster area.
\__/ Capt. Benjamin "Hawkeye" Pierce
Crank Dot Net / http://www.crank.net/
Cranks, crackpots, kooks, & loons on the Net.
David Eppstein
an...@vredegoor.doge.nl (Anton Vredegoor) wrote:
Actually, it's possible to solve the traveling salesman problem in time
O(n 2^n), much better than factorial. But the solution involves dynamic
programming and is probably not what Chad N. meant by "brute-force".
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Chad Netzer
> Although it's important to not set too severe limitations I have the
> impression this salesman is underestimating the problem.
Oops. I never was cut out for sales. :) Thanks for correcting me.
Peter van Kampen
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)?
for example
bigO_N(i):
for n in xrange(i):
print n
Would be O(N) right?
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.
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(??).
Roy Smith
> 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
You do it by analysis. Basicly, you find the "inner loop", i.e. the bit
of core code that gets run over and over while the algorithm does its
work. Then, you figure out (by looking at the code) how many times that
inner loop will run given that the input is a given size.
Sometimes, in a high level language like Python, there are implied loops
in what look like atomic operations. This can obscure the real
algorithmic complexity of a program, unless you know enough to look
deeper. Take the classic Python example:
s1 = ""
for s2 in stringList:
s1 += s2
On the surface, it looks like this should be an O(N) program, where N is
the number of strings in stringList. Certainly, for N strings, the loop
gets executed N times. But, the string addition has an couple of
inherent loops of its own. The most obvious is that each character in
s2 has to be copied someplace, so it really looks like this:
s1 = ""
for s2 in stringList:
for c in s2:
s1 += c
Now it looks like it takes O(k*N) steps, where N is again the number of
strings in stringList, and k is the average number of characters in a
string.
Here's the first tricky part -- for the purpose of big-O notation, the k
is meaningless. It's essentially a constant factor. For a given
universe of strings (say, words in a dictionary), k is not going to
change as you add more strings. Sure, it's going to have minor
variations as the average bops around, but once you've got a statisticly
valid sample of input strings, it'll pretty much stay put. k may be a
function of the kinds of strings you're giving it (k might be bigger for
German compared to English), but it's not a function of the number of
strings you're feeding the program. For big-O purposes, O(k*N) where k
is a constant is the same as O(N). What we're trying to describe is the
shape of the growth curve, not the scaling factors.
And, here's the second tricky part -- since strings in Python are
immutable, the way you do s1 += s2 is to figure out how long each of the
two components are, allocate a new string big enough to hold the sum of
those, and copy the two original strings into the new one. So, let's
tear that apart a bit and see what it looks like, complexity wise.
We need to figure out how long each component string is. On the
surface, that's O(N), where N is the length of the string. In C, it
looks something like:
length = 0;
while (*string != NULL) {
length++;
string++;
}
This takes 2*N steps (it does two additions on each of N trips through
the loop), but big-O says that O(2*N) is the same as O(N).
Fortunately for us, Python doesn't need to do that. Python stores
strings in a way where the length is pre-computed and stored. All it
really needs to do to get the length is something like "return
string.length", which is a constant-time operation (i.e. it takes the
same amount of time regardless of the length of the string). That's
called O(1).
So, we could rewrite the whole thing as something like:
s1 = ""
for s2 in stringList:
len1 = len(s1)
len2 = len(s2)
newLen = len1 + len2
temp = allocate buffer for newLen characters
for c in s1:
temp += c
for c in s2:
temp += c
s1 = temp
Now, we analyse the complexity of each bit of that. It does the outer
loop N times, but how much work is involved in each iteration of the
outer loop? Each of the len()'s we already figured out is constant
time, so they don't add anything complexity-wise. Adding the two
lengths is also constant time.
For the sake of argument, I'm going to assume that memory allocation is
constant time, although I don't really know that for sure. To really do
the analysis right, I'd have to know the details of how Python memory
management works, and I don't, but I'm reasonably confident that it's
not going to be a determining factor here.
Now we come to the first interesting part. The "for c in s1" loop takes
as many iterations as s1 is long. Well, how long is s1? It varies as
the program progresses, but after we've processed M strings, it's
approximately k*M characters long (where k is again the average string
length). We again toss out the constant k, and come up with the
complexity of this particular loop being O(M). But, what's M? It
varies from 1 to N, and on average, it's N/2. But, the constant factor
of 1/2 doesn't mean anything to big-O, so O(M) = O(N/2) = O(N).
The "for c in s2" loop we've already discussed and decided it was O(k),
which is the same as O(1), i.e. constant time.
And finally, the rebinding of s1 to the new temporary string is constant
time. One minor hitch is that this causes the old s1 to fall out of
scope and become a candidate for garbage collection. Again, without
knowing the details of Python's memory management, I can't say for sure
what the algorithmic complexity of freeing a string is, but for now I'm
going to assume it's O(1).
So, overall, we do an O(N) inner loop (plus a lot of constant-time stuff
that we're ignoring), O(N) times, giving us an overall algorithmic
complexity of O(N^2). This is often called quadratic behavior, and is
generally considered evil and something to be avoided if at all possible.
How evil? Well, I read recently that the new Python 2.3 release is
supposed to be 10% to 20% faster than 2.2. That sounds impressive (and,
don't get me wrong, it is impressive), but it's bupkis compared to
algorithm tuning. 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!
BTW, this is perhaps one of the few arguments against teaching Python
(or any high-level language) as a first programming language. So much
algorithmicly complex stuff gets pushed down into atomic language
constructs that there's no longer much of a correlation between code
complexity and algorithmic complexity. This, of course, is what makes
high level languages so useful in the first place, but I fear we may be
training a new generation of programmers for whom algorithmic complexity
is not as familiar a concept as it used to be.
I'm not saying we should still be teaching C (or assembler) as a first
language. On the other hand, I suspect analysis of algorithms probably
needs to be emphasized more (and earlier) in the curriculum. When I
first learned this stuff, it was mostly just a codification and rigorous
analysis of concepts I'd already explored experimentally in the normal
course of writing C programs. I suspect now it's rather completely new
ground, and may seem rather esoteric and theoretical and not
particularly relevant to real-world problems like designing java
animiations for web pages :-)
A.M. Kuchling
Roy Smith <r...@panix.com> wrote:
<excellent discussion deleted...>
> algorithm tuning. 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
... except for one nit; the above inference isn't valid. O() notation
usually ignores differing multipliers because they don't matter much as N
grows larger, but they still have an effect on the running time.
Consider two algorithms: A is O(N) where each loop takes one second, and B
is O(N**2) where each loop takes .001 second. For 10 items, A takes 10
seconds and B takes .1 sec to run, so switching from A to B would actually
run slower. The situation changes for N=1000, where A takes 1000 seconds
and so does B. For N=2000, A takes 2000sec and B takes 4000sec, twice as
long.
Algorithms often achieve better O() performance at the cost of making the
loop more complicated or requiring some precomputing step, so for small
problem sizes the straightforward algorithm might be faster. Better O()
performance buys you something at larger problem sizes, of course.
(BTW, you should turn your post into a web page and put it somewhere; it
might be useful for educators.)
> complexity and algorithmic complexity. This, of course, is what makes
> high level languages so useful in the first place, but I fear we may be
> training a new generation of programmers for whom algorithmic complexity
> is not as familiar a concept as it used to be.
I don't see that as being a problem; students can first learn the ideas of
big-O notation by counting the number of Python operations, ignoring the
wall-time performance of those operations.
--amk (www.amk.ca)
Now I'll never know if I was right.
-- Adric's last words, in "Earthshock"
Mel Wilson
>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)?
>
>for example
>
>bigO_N(i):
> for n in xrange(i):
> print n
>
>Would be O(N) right?
Yes. A slightly more concrete example:
def bigO_N (a_list):
for a in a_list:
print a
where run-time depends pretty much on the len (a_list).
>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.
Again:
def bigO_N2 (a_list):
for n in a_list:
for m in a_list:
print n, m
I guess two different lists might be used, just as different
i and j values were used above. The run-time depends on the
product of two sizes, so it's called order N-squared. The
O-notation is intentionally sloppy .. scarcely better that a
hand-wave, but it's a useful hand-wave.
>But these are not really 'algorithms'.
Yes they are.
> Most algorithms are a lot more
>complex even when reduced to it's essentials.
Most algorigthms have a lot of processing details that
can distract you from regarding the bare-bones structure.
The O notation is only about that structure:
- hit one element of the data, ignoring the rest
- a pass over the data
- a pass over the data for each data element
- a pass over the data for each permutation of elements
- something else
> I understand why
>quicksort is better than bubblesort but I don't see an obvious way to
>label quicksort O(??).
Divide-and-Conquer algorithms tend to be O(n log n).
Quicksort works by dividing the data set up into a high set
and a low set, and then quicksorting each subset separately.
Making a pass over the set to divide it into high and low is
O(n) .. just like the O(n) examples above in this post. The
number of times you will divide the set in two is roughly
log2(n). So performing log(n) copies of a process that's
O(n) makes for a process that itself is O(n log n).
Regards. Mel.
Duncan Booth
92A049.085...@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?
Ken R.
> In article <mailman.105045762...@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)?
>
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.
I haven't seen the referenced Big-O posting but there is a decent
explanation of Big-O and sorting algorithms here
http://www.autoobjects.com/Home/Teaching/CmpE_126/CmpE_126_Lectures/Sortings/sortings.html#Algorithm
Ken
Andres Rosado
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?
--
Andres Rosado
Email: and...@despammed.com
ICQ: 66750646
Homepage: http://andres980.tripod.com/
Get my PGP key at http://andres980.tripod.com/pgp-key.asc
"Cat's tough. He went out fighting."
-- Depth Charge, on Cheetor's apparent demise,
"Feral Scream" Part 1
Steve Holden
news:mailman.1050499405...@python.org...
> On 05:06 AM 4/11/2003 -0400, python-li...@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 = ['the', 'quick', 'brown', 'fox', 'jumps' 'over', 'the', 'lazy',
'dog]
in VBScript I must resort to one of [nontested code follows]:
dim sarr(9)
sarr(1) = 'the'
sarr(2) = 'quick'
...
sarr(8) = 'dog'
or possibly
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).
Hope this makes it clearer.
Peter van Kampen
[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...
Andrew Bennetts
[...]
>
> 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 = ['the', 'quick', 'brown', 'fox', 'jumps' 'over', 'the', 'lazy',
> 'dog]
>
> in VBScript I must resort to one of [nontested code follows]:
>
> dim sarr(9)
> sarr(1) = 'the'
> sarr(2) = 'quick'
> ...
> sarr(8) = 'dog'
>
> or possibly
>
> sarr = split("the quick brown fox jumps over the lazy dog")
Or, if my memory isn't failing me:
sarr = Array("the", "quick", ... "dog")
-Andrew.
Courageous
>I think I almost 'get it'. Except who or what decides what Big-O a
>certain algorithm has.
It's mathematics. There's neither opinion nor "benchmarks".
C//
Courageous
>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
Ah, the practical optimizer. We encounter so few of these in this day
and age. :-)
C//
Christopher A. Craig
> 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-...@ccraig.org>
"Never let schooling get in the way of your education" Mark Twain
Steve Holden
> 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:
> >
> > sarr = ['the', 'quick', 'brown', 'fox', 'jumps' 'over', 'the',
'lazy',
> > 'dog]
> >
> > 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 ;-)
A. Lloyd Flanagan
> 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.
Bjorn Pettersen
>
[...]
> 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].
-- bjorn
sik0fewl
news:<slrnb9q90...@datatailors.com>...
>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
Bjorn Pettersen
> Peter van Kampen <ne...@datatailors.xs4all.nl> wrote in message
> news:<slrnb9q90...@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.
google(algorithm complexity) == lecture notes
(http://www.geog.buffalo.edu/classes/geo554/week4.pdf)
[also "time complexity", "space complexity"].
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).
-- bjorn
Steven Taschuk
[...]
> This mathematical analysis of an algorithm's behavior (and best-case,
> average, and worst-case performance) can be trivial. For example, x +
I would have thought it's O(log x), due to the possibility of
carries.
--
Steven Taschuk stas...@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_
Steven Taschuk
[...]
> 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."
stas...@telusplanet.net Mark: "Turn-about is fair play, sir."
-- _Mirror Dance_, Lois McMaster Bujold
Steven Taschuk
[...]
> 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 stas...@telusplanet.net
"Telekinesis would be worth patenting." -- James Gleick
Andrew Dalke
> 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.
But for fixed size integers, the above is true.
Andrew
da...@dalkescientific.com
Erik Max Francis
> 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.
Erik Max Francis
> 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!
Tim Ottinger
> 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.
tim
Yu Wang
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)
command="somecommand"
arg="-i somefile > output file"
execl(command,arg)
what's wrong with this?
And,
how could I get child pid from "popen3(somecommand)".
Thanks to you.
Regards.
Ian Bicking
> 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
Erik Max Francis
> 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
use sys.stderr, and dup2() function both work for it.
Alex Martelli
> Hi,all
> Does "execl", or whatever this family, support redirection of output?
exec...* are the system calls on top of which redirection of output
is implemented by the shell (there's also a fork in between of course).
> Say, I have a script: ( on my Linux7.2,C shell environment,with
> python2.2.1)
>
> command="somecommand"
> arg="-i somefile > output file"
> execl(command,arg)
>
> what's wrong with this?
You have not involved the shell, so the "> whatever" syntax ain't
gonna fly (who would be parsing it?). You can explicitly invoke
/bin/sh -c "whatever >theoutputfile" if you wish; or else, do it
at a lower level (with os.dup2 and friends, fork maybe, then exec).
> And,
> how could I get child pid from "popen3(somecommand)".
http://www.python.org/doc/current/lib/popen3-objects.html
Alex
Alex Martelli
...
> 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
I don't think there can be any such algorithm -- in O(n) time,
the algoritm cannot USE more than O(n) memory, so how could it
NEED it...? The reverse, sure, but not this way, I think.
Alex
David Eppstein
Alex Martelli <al...@aleax.it> wrote:
A simple example would be an algorithm that takes as input a sequence of
values that are all (for whatever reason) guaranteed to be integers in
range(n**2), and tests whether any two of them are the same:
def anysame(seq):
allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
(is this possible in pure python?)
for i,x in enumerate(seq):
if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
return True
A[x] = i
return False
Initializing A would require too much time, but the algorithm is capable
of working with an uninitialized array. The usual trick for reducing
the memory requirements of such an algorithm is to replace the array by
a hash table, and of course in Python the hash table (dictionary) based
duplicate detection algorithm is much more preferable, but this makes
theoreticians unhappy by turning worst-case time bounds into randomized
expected time bounds.
--
David Eppstein http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science
Alex Martelli
> In article <_Fzna.27993$LB6.6...@news1.tin.it>,
> Alex Martelli <al...@aleax.it> wrote:
>
>> Steven Taschuk wrote:
>> ...
>> > 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
>>
>> I don't think there can be any such algorithm -- in O(n) time,
>> the algoritm cannot USE more than O(n) memory, so how could it
>> NEED it...? The reverse, sure, but not this way, I think.
>
> A simple example would be an algorithm that takes as input a sequence of
> values that are all (for whatever reason) guaranteed to be integers in
> range(n**2), and tests whether any two of them are the same:
>
> def anysame(seq):
> allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
> (is this possible in pure python?)
I don't think it is, but probably you could write a C-coded
extension that does this. It would have to be a C-coded type
in order to be able to ensure returning the x-th item as a
valid Python object without having undergone any initialization,
though. Perhaps on some architectures mmap applied to some
appropriate /dev/??? would let you do this (but I'm not sure).
> for i,x in enumerate(seq):
> if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
> return True
> A[x] = i
> return False
Neat! Takes a while to convince oneself of this, but, yes,
if "allocating N cells of uninitialized memory" exists as a
O(1) primitive, this will work. I had not considered this
possibility when I expressed my doubts on Steven's words!
> Initializing A would require too much time, but the algorithm is capable
> of working with an uninitialized array. The usual trick for reducing
> the memory requirements of such an algorithm is to replace the array by
> a hash table, and of course in Python the hash table (dictionary) based
> duplicate detection algorithm is much more preferable, but this makes
> theoreticians unhappy by turning worst-case time bounds into randomized
> expected time bounds.
Oh yes, absolutely.
Alex
Tim Peters
> ...
> A simple example would be an algorithm that takes as input a sequence of
> values that are all (for whatever reason) guaranteed to be integers in
> range(n**2), and tests whether any two of them are the same:
>
> def anysame(seq):
> allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
> (is this possible in pure python?)
It shouldn't be possible: if you find a way to do it, it would be
considered a security bug. No memory is really uninitialized -- if Python
gave you read access to n**2 bytes in constant time, it would be revealing
to you the state left behind by some other function (or user, or process).
If you created a file with at least n**2 bytes beforehand, then you could
mmap the file in constant time, and that acts like an array object
initialized to whatever bytes happen to be sitting in the file. But the O()
behavior of access to an mmap'ed region depends on the platform
implementation of mmap'ed regions.
> for i,x in enumerate(seq):
> if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
> return True
> A[x] = i
> return False
Something must be missing here, right? For example, suppose A just happens
to be uninitialized to all zeroes, and we pass in seq=[8, 8]. Then A[8] is
set to 0 in the first loop trip, and in the second
A[8] is 0 so 0 <= A[x] < i is true
A[A[x]] == A[A[8]] == A[0] == 0 != 8 so the if guard is false
A[8] is set to 1
Then the loop ends and the function returns False.
David Eppstein
Tim Peters <tim...@comcast.net> wrote:
> > for i,x in enumerate(seq):
> > if A[x] is an integer and 0 <= A[x] < i and A[A[x]] == x:
> > return True
> > A[x] = i
> > return False
>
> Something must be missing here, right? For example, suppose A just happens
> to be uninitialized to all zeroes, and we pass in seq=[8, 8]. Then A[8] is
> set to 0 in the first loop trip, and in the second
>
> A[8] is 0 so 0 <= A[x] < i is true
> A[A[x]] == A[A[8]] == A[0] == 0 != 8 so the if guard is false
> A[8] is set to 1
>
> Then the loop ends and the function returns False.
Sorry, bug in untested code. Instead of A[A[x]]==x the test should be
seq[A[x]]==x.
Anyway, this is not code you would want to actually use, just an
illustration of how random access can sometimes make it useful to have
much more memory than you actually touch during an algorithm.
Steven Taschuk
Eppstein's given a nice example here, assuming O(1) memory
allocation. What I had in mind was something much less clever --
just not counting the time to set up ancillary data structures.
A silly example: comparing two strings for lexicographic order.
The obvious character-by-character algorithm is O(len(s)) (where s
is one of the strings -- doesn't matter which). If, however, the
set of strings which might enter into comparisons during the
execution of the program is fixed and computable beforehand (in
particular, finite), you might precompute the results of all the
n^2 comparisons. Then comparing two strings is just a lookup in
the table, which might be just O(1).
Of course, it does take O(n^2) time to set up such a table, and
from that point of view you are of course correct. In practice
that might not matter.
Steven Taschuk
> [David Eppstein]
[...]
> > allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
> > (is this possible in pure python?)
>
> considered a security bug. No memory is really uninitialized -- if Python
> gave you read access to n**2 bytes in constant time, it would be revealing
> to you the state left behind by some other function (or user, or process).
Hm... it doesn't have to let us *read* from the uninitialized
memory. Just as long as it lets us write to it, and later read
from the spots we've written to.
This is of dubious usefulness, of course.
--
Steven Taschuk stas...@telusplanet.net
"I'm always serious, never more so than when I'm being flippant."
-- _Look to Windward_, Iain M. Banks
Andy Robinson
>>
>> 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 ;-)
I think VB actually started to borrow Python ideas and
features a few years back. The Collection classes
got a lot friendlier, foreach loops over collections..
Years ago someone here said that Python won't take over
the world but its good ideas would end up in other languages...
- Andy Robinson
Paul Moore
>> 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).
Just to clarify this point a bit, the measure usually used in sorting
is the number of swaps of two elements (or the number of comparisons -
these are usually equivalent in terms of O() calculations).
So, you look at bubblesort. Basically, each element gets compared
against each other - that's n * n comparisons, hence O(n**2).
But for quicksort you partition, and compare each element against the
partitioning element. That's n comparisons against log(n) partitioning
elements (each partitioning step halves the size of the chunks, so you
do this log2(n) times). So the complexity is O(n*log(n)).
Disclaimer: This is all *very* rough, and from memory as well. But I
hope it's enough that you get the idea.
Paul.
--
This signature intentionally left blank
Erik Max Francis
> Just to clarify this point a bit, the measure usually used in sorting
> is the number of swaps of two elements (or the number of comparisons -
> these are usually equivalent in terms of O() calculations).
That touches on a point I meant to address but forgot, which is that the
big-O notation can really refer to anything at all. Usually it refers
to algorithm complexity (how much "stuff" needs to get done -- as you
rightly point out in the case of a sorting algorithm it would be the
number of compares), but it could apply to anything like numeric
multiplications, or even amount of memory used either by a static data
structure or an algorithm.
It's really just a method for expressing how complex "something" gets
for very large n (mathematically, as n -> oo). What that something is
can vary from usage to usage.
--
Erik Max Francis / m...@alcyone.com / http://www.alcyone.com/max/
__ San Jose, CA, USA / 37 20 N 121 53 W / &tSftDotIotE
/ \ Covenants without the sword are but words.
\__/ Camden
Bosskey.net: Aliens vs. Predator 2 / http://www.bosskey.net/avp2/
A personal guide to Aliens vs. Predator 2.
Tim Peters
> Sorry, bug in untested code. Instead of A[A[x]]==x the test should be
> seq[A[x]]==x.
So the algorithm is
def anysame(seq):
allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
for i, x in enumerate(seq):
if A[x] is an integer and 0 <= A[x] < i and seq[A[x]] == x:
return True
A[x] = i
return False
Cute! I like it.
> Anyway, this is not code you would want to actually use, just an
> illustration of how random access can sometimes make it useful to have
> much more memory than you actually touch during an algorithm.
Yup, understood. I still like it <wink>.
David Eppstein
Paul Moore <gus...@morpheus.demon.co.uk> wrote:
> But for quicksort you partition, and compare each element against the
> partitioning element. That's n comparisons against log(n) partitioning
> elements (each partitioning step halves the size of the chunks, so you
> do this log2(n) times). So the complexity is O(n*log(n)).
>
> Disclaimer: This is all *very* rough, and from memory as well. But I
> hope it's enough that you get the idea.
This is not completely accurate, since each partition is not usually
exactly in half. My favorite version of the quicksort analysis is in
the new Cormen-Leiserson-Rivest-Stein version of Intro to Algorithms:
number the items according to their eventual sorted positions, then item
i is compared to item j exactly when the first pivot in the range i..j
is either i or j, which occurs with probability 2/|i-j+1|. Sum up these
probabilities for all i<j to get the expected number of comparisons and
you get roughly 2 n H_n (harmonic numbers) = O(n log n).
Beni Cherniavsky
>[David Eppstein]
>> ...
>> A simple example would be an algorithm that takes as input a sequence of
>> values that are all (for whatever reason) guaranteed to be integers in
>> range(n**2), and tests whether any two of them are the same:
>>
>> def anysame(seq):
>> allocate array A, of dimension n**2, WITHOUT INITIALIZING IT
>> (is this possible in pure python?)
>
>It shouldn't be possible: if you find a way to do it, it would be
>considered a security bug. No memory is really uninitialized -- if Python
>gave you read access to n**2 bytes in constant time, it would be revealing
>to you the state left behind by some other function (or user, or process).
>If you created a file with at least n**2 bytes beforehand, then you could
>mmap the file in constant time, and that acts like an array object
>initialized to whatever bytes happen to be sitting in the file. But the O()
>behavior of access to an mmap'ed region depends on the platform
>implementation of mmap'ed regions.
>
memory mapping hardware. It's possible to mark the required range of memory
pages to cause an exception and be initialized [to zeros] only when they are
accessed. Since the algorithm only accesses a few pages, this should work
fine. This reveals a little clarification to the original claim: the
algorithm doesn't use O(N**2) memory, it eats O(N**2) of your *address space*.
In fact, that's what mmaping /dev/zero probably does on most platforms...
There is a catch: for large enough N, you need to mark O(N**2) pages in this
way, so it's O(N**2) time to allocate again :-(. This can be overcome by
hierarchical page tables. To be precise, you would need an arbitrarily deep
hierarchy rather than one of fixed depth that real computers tend to have
<wink>. Note that such a hierarchy is actually a way of implementing a
dictionary from digital trees :-).
You would actually need infinite memory to have an unbounded hierarchy. Which
exposes a small catch with application of asymptotic analysis once you
approach limits of address space, integer size, etc. No algorithm takes
O(f(N)) when N approaches infinity - instead it just runs out of resources
:-)! So many algorithms can be pervertly claimed to be O(1) on a given
architecture. For example one can sort any array of 16 bit integers in O(1)
by just allocating a O(2**16) array counting how many times each number
appeared and then scanning the array. Of course this is worse than any
sensible algorithm one would write - because of the huge factor. In truth
this is not O(1) - it's O(M) where M is your address space or "integer space"
size. But omitting such considerations can lead to funny "paradoxes"...
P.S. Cute algorithm indeed!
Beni Cherniavsky <cb...@tx.technion.ac.il>
A. Lloyd Flanagan
I stand corrected. See, this algorithm-analysis stuff can tricky!