Home > Archive > Software Engineering > May 2006 > Iteration vs. Recursion
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Iteration vs. Recursion
|
|
| Sathyaish 2006-05-08, 4:05 am |
| Can every problem that has an iterative solution also be expressed in
terms of a recursive solution?
I tried one example, and am in the process of trying out more examples,
increasing their complexity as I go. Here's a simple one I tried out:
#include<stdio.h>
/* To compare the the time and space cost of iteration against
recursion*/
const int SOME_CONST = 10;
void ifoo();
void rfoo(int, int, int);
int main(void)
{
ifoo();
rfoo(0, 0, 5);
printf("\n");
return 0;
}
void ifoo()
{
int i = 0, x = 0, y = 5;
for(; i < SOME_CONST; i++)
{
x += y;
printf("%d\t%d\t%d\t\n", i, x, y);
}
}
void rfoo(int i, int x, int y)
{
x += y;
printf("\n%d\t%d\t%d", i, x, y);
if (i < SOME_CONST - 1)
rfoo(++i, x, y);
}
I noted the following:
a. While iteration is linear in time and constant in space, recursion
is exponential in space.
b. Iteration preserves state, recursion does not.
| |
| Richard Heathfield 2006-05-08, 4:05 am |
| Sathyaish said:
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?
Yes. Iteration and recursion are just two different ways of saying "if we're
not finished yet, let's do it some more". Recursion is one way of
implementing iteration. Iteration is one way of implementing recursion.
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
Not necessarily. It depends what you're doing and how you're doing it.
> b. Iteration preserves state, recursion does not.
It certainly /can/, if that is what is required.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
|
| Sathyaish wrote:
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?
Matter of basic meaning of the two words.
>
> I tried one example, and am in the process of trying out more examples,
> increasing their complexity as I go. Here's a simple one I tried out:
You can not test a hypothesis merely by increasing the complexity.
>
> #include<stdio.h>
>
>
> /* To compare the the time and space cost of iteration against
> recursion*/
>
> const int SOME_CONST = 10;
> void ifoo();
> void rfoo(int, int, int);
>
>
> int main(void)
> {
> ifoo();
> rfoo(0, 0, 5);
> printf("\n");
> return 0;
> }
>
> void ifoo()
> {
> int i = 0, x = 0, y = 5;
> for(; i < SOME_CONST; i++)
> {
> x += y;
> printf("%d\t%d\t%d\t\n", i, x, y);
> }
> }
>
>
> void rfoo(int i, int x, int y)
> {
> x += y;
> printf("\n%d\t%d\t%d", i, x, y);
>
> if (i < SOME_CONST - 1)
> rfoo(++i, x, y);
> }
>
You have shown an example of an iteration and an example of recursion. Just
because the latter performs the same as the former does not mean that EVERY
iteration can be expressed as a recursion.
The following is an iteration that cannot be expressed as a recursion
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
printf("%d", rand());
....
>
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
>
In what way? What do you mean by space? Computer memory? This statement
would seem to be meaningless.
An iterated process would not necessarily be linear in time on a
multitasking computer - which most are these days.
I think you are getting lost over a simple matter.
> b. Iteration preserves state, recursion does not.
State of what? Recursion will preserve a return value. In the stack frame
of each iteration of a recursive function is preserved the "state" of the
function at that time. This would not be "exponential".
Try to simplify by going to the basic meaning of the two words -
"Iterate: repeat, state repeatedly (Latin: iterum - again)"
Iteration is a process that is repeated a number of times without
necessarily returning to anything.
Loops are iterative processes. But iteration is not necessarily confined
to loops - vide my example above.
"Recursion: the act or an instance of returning (Latin: recurrere - run
again)" Concise Oxford Dictionary.
Recursion is a process that calls itself, ie. returns to itself.
A "function" that calls itself is recursion.
The definition of the words show they are NOT synonymous - ie. things may be
repeated without necessarily involving any idea of "returning".
Simple!
Was it really necessary to cross post??
Alan
| |
| Torben Ægidius Mogensen 2006-05-08, 4:05 am |
| "Sathyaish" <sathyaish@gmail.com> writes:
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?
Yes. The converse is true only if you allow extra variables (of
unbounded size) to be introduced, essentially emulating a recursion
stack.
> I tried one example, and am in the process of trying out more examples,
> increasing their complexity as I go. Here's a simple one I tried out:
>
> #include<stdio.h>
>
>
> /* To compare the the time and space cost of iteration against
> recursion*/
>
> const int SOME_CONST = 10;
> void ifoo();
> void rfoo(int, int, int);
>
>
> int main(void)
> {
> ifoo();
> rfoo(0, 0, 5);
> printf("\n");
> return 0;
> }
>
> void ifoo()
> {
> int i = 0, x = 0, y = 5;
> for(; i < SOME_CONST; i++)
> {
> x += y;
> printf("%d\t%d\t%d\t\n", i, x, y);
> }
> }
>
>
> void rfoo(int i, int x, int y)
> {
> x += y;
> printf("\n%d\t%d\t%d", i, x, y);
>
> if (i < SOME_CONST - 1)
> rfoo(++i, x, y);
> }
>
>
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
How did you arive at that conclusion? Your rfoo function will in C
use space linear in the number of recursice calls, but even that is
only because your C compiler doesn't do tail-recursion optimisation
(which any sensible compiler will), which would make the above run in
constant space.
> b. Iteration preserves state, recursion does not.
On the contrary: Iteration works by transforming state while recursion
can work by creating new local values (while preserving the global
state). That is the essense of value-oriented (functional)
programming: You never destructively overwrite values, you just create
new ones and reuse the space for the old ones only when they are
guarateed not to be used anymore.
Torben
| |
| amaldev.manuel@gmail.com 2006-05-08, 4:05 am |
| > I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
>
> b. Iteration preserves state, recursion does not.
certainly not in the case of backtracking algorithms.
| |
| Julian V. Noble 2006-05-08, 8:02 am |
| Sathyaish wrote:
> Can every problem that has an iterative solution also be expressed in
> terms of a recursive solution?
>
[ snipped ]
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
Two remarks:
1. You can read all about recursion in my Computing Prescriptions
column in Computing in Science and Engineering (May/June 2003,
pp. 76-81 (a color version may be found at
http://galileo.phys.virginia.edu/cl...ll01/Cprogs.htm
2. Assuming recursion employs a stack, the growth of memory usage
with problem size is logarithmic, not exponential, unless you
are using recursion in a foolish context (to compute Fibonacci
numbers or the like).
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
| |
| Torben Ægidius Mogensen 2006-05-08, 8:02 am |
| "Julian V. Noble" <jvn@virginia.edu> writes:
> Two remarks:
>
> 1. You can read all about recursion in my Computing Prescriptions
> column in Computing in Science and Engineering (May/June 2003,
> pp. 76-81 (a color version may be found at
>
> http://galileo.phys.virginia.edu/cl...ll01/Cprogs.htm
Hardly _all_ about recursion. :-)
> 2. Assuming recursion employs a stack, the growth of memory usage
> with problem size is logarithmic, not exponential, unless you
> are using recursion in a foolish context (to compute Fibonacci
> numbers or the like).
That is a very imprecise statement. The largest number of stack
frames that are active at any one point can be anywhere between
constant to linear in the total number of recursive calls, but the
number of recursive calls does not need to be linear in the problem
size (as measured by the input size). For example, the recursive
solution to The Towers of Hanoi for N disks uses 2^N-1 calls but stack
depth only N. Additionally, the size of each stack frame may depend
on the input size, so the total space used can be larger than linear
in the number of calls.
Torben
| |
| SM Ryan 2006-05-08, 10:05 pm |
| # Sathyaish said:
#
# Can every problem that has an iterative solution also be expressed in
# terms of a recursive solution?
Iterative constructions can be easily transformed into recursive ones.
Some recursive constructs cannot be transformed into iterative without
additional variables to simulate the stack.
--
SM Ryan http://www.rawbw.com/~wyrmwif/
We found a loophole; they can't keep us out anymore.
| |
| raxitsheth@gmail.com 2006-05-09, 4:26 am |
|
>
> I noted the following:
>
> a. While iteration is linear in time and constant in space, recursion
> is exponential in space.
>
> b. Iteration preserves state, recursion does not.
Missing Basic Stuff,
Question why it would require more time (then linear)?
why required more space ? (coz to preserve the state on stake )
Simple ex. fibonacci
fib(1) = fib(2) = 1
fib(n) = fib(n-1)+fib(n-2), if n>2
for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
the basic thing is that fib(3) is calculated two times above.
Normally (not always) recursive one is slow(compare to linear) and/or
would require (more space) because
1. repeated computation done. (as in ex. fib(3) called twice,
2. and same result is stored more than once.
Before using recursive fun. Estimate how much space/time it would take
extra, ?
that is the best way to decide recursive is usable in particular case
or not ?
--
Raxit Sheth
| |
| Richard Heathfield 2006-05-09, 4:26 am |
| raxitsheth@gmail.com said:
> Simple ex. fibonacci
>
> fib(1) = fib(2) = 1
> fib(n) = fib(n-1)+fib(n-2), if n>2
>
> for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
>
>
> the basic thing is that fib(3) is calculated two times above.
> Normally (not always) recursive one is slow(compare to linear) and/or
> would require (more space) because
> 1. repeated computation done. (as in ex. fib(3) called twice,
> 2. and same result is stored more than once.
Exercise for the reader: write an iterative version of fib() that is even
less efficient than the recursive version explained above, and use it to
prove that iteration is slow (compared to recursion) and would require more
space.
Exercise for the undergraduate student (or bright 12-year-old): write a
version that calculates fib() without iterating or recursing, thus proving
that both iteration and recursion require unnecessary amounts of space and
time.
Exercise for the post-graduate student: make the non-iterative non-recursive
version less efficient than the least efficient of the versions so far
discussed, thus proving that both iteration and recursion are massively
superior to O(1) techniques.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| Alf P. Steinbach 2006-05-09, 4:26 am |
| * Richard Heathfield:
> raxitsheth@gmail.com said:
>
>
> Exercise for the reader: write an iterative version of fib() that is even
> less efficient than the recursive version explained above, and use it to
> prove that iteration is slow (compared to recursion) and would require more
> space.
>
> Exercise for the undergraduate student (or bright 12-year-old): write a
> version that calculates fib() without iterating or recursing, thus proving
> that both iteration and recursion require unnecessary amounts of space and
> time.
>
> Exercise for the post-graduate student: make the non-iterative non-recursive
> version less efficient than the least efficient of the versions so far
> discussed, thus proving that both iteration and recursion are massively
> superior to O(1) techniques.
The last one stumps me.
--
A: Because it messes up the order in which people normally read text.
Q: Why is it such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
| |
| Torben Ægidius Mogensen 2006-05-09, 8:06 am |
| raxitsheth@gmail.com writes:
>
> Missing Basic Stuff,
> Question why it would require more time (then linear)?
> why required more space ? (coz to preserve the state on stake )
>
> Simple ex. fibonacci
>
> fib(1) = fib(2) = 1
> fib(n) = fib(n-1)+fib(n-2), if n>2
>
> for fib(6)=fib(5)+fib(4)=[fib(4)+fib(3)] + [fib(3)+fib(2)] =-........
>
>
> the basic thing is that fib(3) is calculated two times above.
> Normally (not always) recursive one is slow(compare to linear) and/or
> would require (more space) because
> 1. repeated computation done. (as in ex. fib(3) called twice,
> 2. and same result is stored more than once.
>
> Before using recursive fun. Estimate how much space/time it would take
> extra, ?
> that is the best way to decide recursive is usable in particular case
> or not ?
As Richard Heathfield said, this is not a question of recursion versus
iteration, but a question of using different algorithms. You are not
the only one making this mistake, though. I remember a special issue
of BYTE magazine from 1988 on benchmarks, where the author of an
article on Pascal benchmarks used the naive fibonacci function above
as a benchmark for function calls. The author then thought it would
be neat to compare the running time to a non-recursive implementation
and was flabbergasted by the large difference, concluding that
function calls must be very expensive indeed.
If your iterative fibonacci is
a := 0;
b := 1;
for i:=0 to n do begin
t := a;
a := b;
b := t+b
end;
writeln(b)
then the recursive version you should compare with is:
fib n = fib1 (n,0,1)
fib1 (0,a,b) = b
fib1 (n,a,b) = fib1 (n-1,b,a+b)
which is simpler than the above (it doesn't need the temporary
variable t) and equally fast (assuming a sensible compiler).
Both of the above use O(n) steps to calculate fibonacci of n. The
recursive function below uses O(log(n)) steps. Try writing this
without recursion.
fibo n = fst (h n)
h 0 = (1,0)
h n | even n = (a^2+b^2,b*(2*a-b)) where (a,b) = h (n`div`2)
h n | odd n = (a*(2*b+a),a^2+b^2) where (a,b) = h (n`div`2)
Note: It will be slower than the simple fib for small n.
Richard also hinted at an O(1) fibonacci function. He probably meant
(phi^n - (1-phi)^n)/sqrt(5), where phi = (sqrt(5)+1)/2. This is,
however, a bit misleading, as this is only O(1) if you can do
arbitrary precision arithmetic in constant time, which is a bit
doubtful. This is also to a lesser extent true for the simpler
versions, as the linear time is assuming that arithmetic operations on
arbitrary-size integers can be done in constant time.
Torben
| |
|
|
| Julian V. Noble 2006-05-09, 7:04 pm |
| Jonathan Bartlett wrote:
> You might be interested in an article I wrote for IBM DeveloperWorks on
> recursive programming:
>
> http://www-128.ibm.com/developerwor...y/l-recurs.html
>
> Jon
> ----
> Learn to program using Linux assembly language
> http://www.cafeshops.com/bartlettpublish.8640017
Nice article. I sent feedback. I don't agree that you should
keep variables constant throughout a program. That's what a
CONSTANT is for.
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
| |
| James Dow Allen 2006-05-11, 4:03 am |
|
Richard Heathfield wrote:
> Exercise for the post-graduate student: make the non-iterative non-recursive
> version less efficient than the least efficient of the versions so far
> discussed, ...
Not overly impressed with Comp Sci doctorates, eh?
James
| |
| Richard Heathfield 2006-05-11, 4:03 am |
| James Dow Allen said:
>
> Richard Heathfield wrote:
>
> Not overly impressed with Comp Sci doctorates, eh?
When you've had to teach 'em to program, you don't tend to be too impressed
by the bits of paper that said they already could.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| blmblm@myrealbox.com 2006-05-11, 8:01 am |
| In article <n4ednUcxsZjmRf_ZnZ2dnUVZ8s6dnZ2d@bt.com>,
Richard Heathfield <invalid@invalid.invalid> wrote:
>James Dow Allen said:
>
>
>When you've had to teach 'em to program, you don't tend to be too impressed
>by the bits of paper that said they already could.
Point taken, but ....
Do PhD programs in CS even claim to be producing good programmers?
I mean, I can easily imagine legitimate dissertation research that
involves no programming at all, and while you could argue that the
degree program should include a breadth requirement that includes
programming skills, hm .... No, I don't think I would (argue that,
beyond a minimal level that I suspect would still leave the person
in a state in which you would have to "teach 'em to program").
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| Richard Heathfield 2006-05-11, 7:02 pm |
| blmblm@myrealbox.com said:
> In article <n4ednUcxsZjmRf_ZnZ2dnUVZ8s6dnZ2d@bt.com>,
> Richard Heathfield <invalid@invalid.invalid> wrote:
>
> Point taken, but ....
>
> Do PhD programs in CS even claim to be producing good programmers?
If CS grads at least knew a bit of CS, that would be a start. :-)
(I accept that my sample set is probably statistically insignificant, but
they were *all* useless, and 100% is 100% in anybody's language!)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| Ben Pfaff 2006-05-11, 7:02 pm |
| blmblm@myrealbox.com writes:
> Do PhD programs in CS even claim to be producing good programmers?
That's not a claim here at Stanford, as far as I know.
--
Ben Pfaff
email: blp@cs.stanford.edu
web: http://benpfaff.org
| |
| blmblm@myrealbox.com 2006-05-11, 7:02 pm |
| In article <IvqdnVrtxcAF2f7ZnZ2dnUVZ8qudnZ2d@bt.com>,
Richard Heathfield <invalid@invalid.invalid> wrote:
>blmblm@myrealbox.com said:
>
>
>If CS grads at least knew a bit of CS, that would be a start. :-)
>
>(I accept that my sample set is probably statistically insignificant, but
>they were *all* useless, and 100% is 100% in anybody's language!)
>
They're useless for your purposes, and they don't know any CS either?
That would *really* be a  commentary on those bits of paper.
War stories of their uselessness appreciated, too, especially
if your comment extends to people with undergrad CS degrees.
I teach undergrad CS, and while I don't think every last one of our
graduates should be a good fit in a programming job, still, *some*
of them should be.
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| Richard Heathfield 2006-05-11, 7:02 pm |
| blmblm@myrealbox.com said:
>
> War stories of their uselessness appreciated, too, especially
> if your comment extends to people with undergrad CS degrees.
> I teach undergrad CS, and while I don't think every last one of our
> graduates should be a good fit in a programming job, still, *some*
> of them should be.
I'm sure your crop is better than average, as they have you to teach them.
And of course I know there are plenty of bright CS bunnies out there
generally. It's just that I hardly ever seem to run into them myself -
except here on Usenet, of course.
Maybe the bright ones are bright enough to know to avoid me. :-)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| blmblm@myrealbox.com 2006-05-11, 7:02 pm |
| In article <4pidneLYbck0wP7ZnZ2dnUVZ8s-dnZ2d@bt.com>,
Richard Heathfield <invalid@invalid.invalid> wrote:
>blmblm@myrealbox.com said:
>
>I'm sure your crop is better than average, as they have you to teach them.
Actually I think they are a bit better than average, though I doubt
I can claim much if any of the credit for that -- we get some pretty
bright ones coming in. Some of them, by the time they graduate,
are pretty competent programmers, by the standards of an academic
anyway. Others -- well, we sometimes wonder how they managed to
forget so much of what they presumably learned in order to pass the
introductory programming classes. And don't get me started on the
range of mathematical backgrounds/skills ....
Possibly, though, I wasn't clear -- I wasn't so much claiming that
we *do* turn out a few who might be useful (though I hope that's
true) as saying that we *should* turn out a few such, and asking
for stories that would make it clearer what to avoid.
>And of course I know there are plenty of bright CS bunnies out there
>generally. It's just that I hardly ever seem to run into them myself -
>except here on Usenet, of course.
>
>Maybe the bright ones are bright enough to know to avoid me. :-)
Anything's possible, but I'd claim that the bright ones are smart
enough to recognize the value of hanging around someone knowledgeable
if irascible.
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| Richard Heathfield 2006-05-11, 7:02 pm |
| blmblm@myrealbox.com said:
> Possibly, though, I wasn't clear -- I wasn't so much claiming that
> we *do* turn out a few who might be useful (though I hope that's
> true) as saying that we *should* turn out a few such, and asking
> for stories that would make it clearer what to avoid.
Well, for starters, either teach them how to program or tell them not to
apply for programming jobs. :-)
Seriously, it's not my place to teach you how to teach. But IF IT WERE, then
I'd suggest the following:
Make sure they have a thorough understanding of an abstract machine, to the
extent that they can write non-trivial machine code programs in it. An
8-bit machine will be fine - 256 bytes of RAM ought to be enough for
anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
a weird character collating sequence. I mean /really/ weird. (But keep '0'
through '9' contiguous and ascending.) If you're feeling really pleasant,
make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
the word "architecture" (or "agriculture", as we read in clc recently!).
Set one of the really bright ones to write the machine code interpreter in
something like C or C++; then make sure it works, fix it if need be, and
use it forever afterwards for students to test their machine code programs
on. Then get someone else bright to write an assembler and debugger for it.
You're now in a position to teach programming at the dirty end - so make
sure they all understand about stacks and heaps and how memory works and
procedure calls, and so on ad nauseam. (Make sure they write enough machine
code programs to get the idea, before you let them graduate to assembly
language.)
This doesn't have to be hugely in-depth, but I am sick and tired of teaching
people what a pointer is, when they ought to KNOW what a pointer is. "Look,
you want this function to update the pointer, right? So you ought to be
passing a pointer-to-the-pointer into the function" + blank look = recipe
for a police caution.
Then, once they know all that, teach them programming from the clean end.
:-) High level, in other words. You should find that they pick it up rather
easily, because they understand what's going on underneath.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| Charles Richmond 2006-05-11, 7:02 pm |
| blmblm@myrealbox.com wrote:
>
> In article <n4ednUcxsZjmRf_ZnZ2dnUVZ8s6dnZ2d@bt.com>,
> Richard Heathfield <invalid@invalid.invalid> wrote:
>
> Point taken, but ....
>
> Do PhD programs in CS even claim to be producing good programmers?
> I mean, I can easily imagine legitimate dissertation research that
> involves no programming at all, and while you could argue that the
> degree program should include a breadth requirement that includes
> programming skills, hm .... No, I don't think I would (argue that,
> beyond a minimal level that I suspect would still leave the person
> in a state in which you would have to "teach 'em to program").
>
This reminds me of this math professor that a friend and I took
numerical analysis from in college. This istic prof did *not*
provide the students with computer accounts. Instead, you had to
"play" the computer and do all the iterative calculations by hand.
This required a *lot* of writing and created quite a pile of notebook
paper.
ISTM that using the computer is part of the point of such a course.
Fortunately, I had the good sense to drop the class...
--
+----------------------------------------------------------------+
| Charles and Francis Richmond richmond at plano dot net |
+----------------------------------------------------------------+
| |
| Jonathan Bartlett 2006-05-11, 7:02 pm |
| > Nice article. I sent feedback. I don't agree that you should
> keep variables constant throughout a program. That's what a
> CONSTANT is for.
Constants don't work for such a thing. Constants must be (1) global and
(2) known at compile-time.
The point is not "constancy" as much as "single assignment only". There
is a subtle difference. A variable can get a new value, but only if it
is a new instance of that variable (i.e. from a new activation record).
Single assignment allows you to keep better control over your loops.
That way, at all times the derivation of any variable is easily
determinable.
Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017
| |
| Jonathan Bartlett 2006-05-11, 7:02 pm |
| > You're now in a position to teach programming at the dirty end - so make
> sure they all understand about stacks and heaps and how memory works and
> procedure calls, and so on ad nauseam. (Make sure they write enough machine
> code programs to get the idea, before you let them graduate to assembly
> language.)
>
> This doesn't have to be hugely in-depth, but I am sick and tired of teaching
> people what a pointer is, when they ought to KNOW what a pointer is. "Look,
> you want this function to update the pointer, right? So you ought to be
> passing a pointer-to-the-pointer into the function" + blank look = recipe
> for a police caution.
Wow. This sounds exactly like what my book was intended to teach. This
is a shameless plug, but since you essentially stated the purpose and
outline of my book I thought it might be appropriate:
Programming from the Ground Up
http://www.cafeshops.com/bartlettpublish.8640017
It doesn't do machine code, but it covers a lot. However, when I teach
intro to programming at the local junior college, I have a "Machine
Language Game" to teach people how the computer works. I have a 16x16
board representing RAM, a whiteboard segmented into registers, a
one-line card for the display, and a stack of papers which tell how to
execute different command codes. I have one student be the data bus,
one student be the ALU, and one student be the instruction handler, and
one student be the graphics card. The instruction handler tells the
data bus to grab the next instruction. The data bus reads it from RAM
and comes back with the instruction and the next two bytes. The
instruction handler then looks up the first number in the instruction
code manual, and does what the manual says. The ALU does what the
instruction handler says, and the graphics card just watches some memory
and updates his output whenever it changes, based on the ASCII codes.
It really helps students figure out how the computer really works
underneath.
Jon
| |
| Bradley K. Sherman 2006-05-11, 7:02 pm |
| In article <44638567$1@news.tulsaconnect.com>,
Jonathan Bartlett <johnnyb@eskimo.com> wrote:
>code manual, and does what the manual says. The ALU does what the
>instruction handler says, and the graphics card just watches some memory
>and updates his output whenever it changes, based on the ASCII codes.
>
>It really helps students figure out how the computer really works
>underneath.
>
Which is why students should be learning C not Java in High School
AP courses.
--bks
| |
| Andrew Poelstra 2006-05-11, 7:02 pm |
| On 2006-05-11, Richard Heathfield <invalid@invalid.invalid> wrote:
> Make sure they have a thorough understanding of an abstract machine, to the
> extent that they can write non-trivial machine code programs in it. An
> 8-bit machine will be fine - 256 bytes of RAM ought to be enough for
> anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
> a weird character collating sequence. I mean /really/ weird. (But keep '0'
> through '9' contiguous and ascending.) If you're feeling really pleasant,
> make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
> the word "architecture" (or "agriculture", as we read in clc recently!).
>
One w s in clc is enough to figure that out. I personally think that no
computer programming class should have machines built in the past 15 years.
No, make that 20. Learning to code on a 8086 will teach people the meaning
of portability.
> You're now in a position to teach programming at the dirty end - so make
> sure they all understand about stacks and heaps and how memory works and
> procedure calls, and so on ad nauseam. (Make sure they write enough machine
> code programs to get the idea, before you let them graduate to assembly
> language.)
I agree entirely. Any decent programmer should have some idea of how to
write machine code, or at least understand how it works in principle.
> This doesn't have to be hugely in-depth, but I am sick and tired of teaching
> people what a pointer is, when they ought to KNOW what a pointer is. "Look,
> you want this function to update the pointer, right? So you ought to be
> passing a pointer-to-the-pointer into the function" + blank look = recipe
> for a police caution.
I spent a year working entirely in x86 assembler. I have never, ever, had
a problem figuring pointers out since. Machine language probably isn't
necessary.
Of course, if you are going to teach them Java, you might as well explain
that fairies memorize the contents of your variables so that you don't need
memory.
| |
| CBFalconer 2006-05-11, 7:02 pm |
| Richard Heathfield wrote:
> blmblm@myrealbox.com said:
>
>
> Well, for starters, either teach them how to program or tell them
> not to apply for programming jobs. :-)
>
> Seriously, it's not my place to teach you how to teach. But IF IT
> WERE, then I'd suggest the following:
>
> Make sure they have a thorough understanding of an abstract machine, to the
> extent that they can write non-trivial machine code programs in it. An
> 8-bit machine will be fine - 256 bytes of RAM ought to be enough for
> anybody. 16 bits if you're feeling astoundingly generous. Make sure it has
> a weird character collating sequence. I mean /really/ weird. (But keep '0'
> through '9' contiguous and ascending.) If you're feeling really pleasant,
> make it a two-byte machine with 11-bit bytes! Let them learn the meaning of
> the word "architecture" (or "agriculture", as we read in clc recently!).
>
> Set one of the really bright ones to write the machine code interpreter in
> something like C or C++; then make sure it works, fix it if need be, and
> use it forever afterwards for students to test their machine code programs
> on. Then get someone else bright to write an assembler and debugger for it.
>
> You're now in a position to teach programming at the dirty end - so make
> sure they all understand about stacks and heaps and how memory works and
> procedure calls, and so on ad nauseam. (Make sure they write enough machine
> code programs to get the idea, before you let them graduate to assembly
> language.)
>
> This doesn't have to be hugely in-depth, but I am sick and tired of teaching
> people what a pointer is, when they ought to KNOW what a pointer is. "Look,
> you want this function to update the pointer, right? So you ought to be
> passing a pointer-to-the-pointer into the function" + blank look = recipe
> for a police caution.
>
> Then, once they know all that, teach them programming from the clean end.
> :-) High level, in other words. You should find that they pick it up rather
> easily, because they understand what's going on underneath.
But you would clutter their pristine young minds with all this
detail, when all they need to know is the abstract properties of an
operation! Something like teaching the basic definitions of a
limit (difference arbitrarily small as things approach arbitrarily
near, or we can find an epsilon such that, etc.) to budding
mathematicians. Or even that hot gases expand and urge pistons or
other things to move to budding automotive engineers.
In all seriousness though, the fundamental teaching problem is when
and where to draw the line between detail and abstraction, and
persuade the student to choose the appropriate view. The lack
today of simple but complete systems, such as were built around the
8080, is a drawback. A stack is a detail, automatic storage is an
abstraction.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
| |
| Ben Pfaff 2006-05-11, 10:00 pm |
| Richard Heathfield <invalid@invalid.invalid> writes:
> blmblm@myrealbox.com said:
>
>
> If CS grads at least knew a bit of CS, that would be a start. :-)
I know some excellent computer scientists who are not
programmers. It is not what they do. Their papers read like
math papers. I could never do what they do, and I wouldn't try
to claim that I could.
For their part, I suspect that they wouldn't claim they are good
programmers either, at least not in languages like C. Perhaps
that's the real problem: people who claim to be what they are
not. But I wouldn't criticize computer scientists for not being
programmers, as long as they don't claim to be.
--
Bite me! said C.
| |
| Richard Heathfield 2006-05-11, 10:00 pm |
| Ben Pfaff said:
> I know some excellent computer scientists who are not
> programmers. It is not what they do. Their papers read like
> math papers. I could never do what they do, and I wouldn't try
> to claim that I could.
I take your point, but those people aren't applying for programming jobs,
so, for the purposes of the current discussion, they don't count. :-)
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| Keith Thompson 2006-05-12, 8:02 am |
| Ben Pfaff <blp@cs.stanford.edu> writes:
[...]
> I know some excellent computer scientists who are not
> programmers. It is not what they do. Their papers read like
> math papers. I could never do what they do, and I wouldn't try
> to claim that I could.
>
> For their part, I suspect that they wouldn't claim they are good
> programmers either, at least not in languages like C. Perhaps
> that's the real problem: people who claim to be what they are
> not. But I wouldn't criticize computer scientists for not being
> programmers, as long as they don't claim to be.
It reminds me of an Edsger Dijkstra quotation: "Computer science is no
more about computers than astronomy is about telescopes."
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
|
|
| Richard Heathfield 2006-05-12, 8:02 am |
| birarai said:
> Take a look at www.monsterSDLC.com
....and you'll see a cartoon of an owl with a beach-ball stuck on his nose.
How is this relevant to our discussion of iteration vs recursion?
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| David Lightstone 2006-05-12, 8:02 am |
|
"CBFalconer" <cbfalconer@yahoo.com> wrote in message
news:4463C372.DA1A0537@yahoo.com...
> Richard Heathfield wrote:
>
> But you would clutter their pristine young minds with all this
> detail, when all they need to know is the abstract properties of an
> operation! Something like teaching the basic definitions of a
> limit (difference arbitrarily small as things approach arbitrarily
> near, or we can find an epsilon such that, etc.) to budding
> mathematicians. Or even that hot gases expand and urge pistons or
> other things to move to budding automotive engineers.
>
> In all seriousness though, the fundamental teaching problem is when
> and where to draw the line between detail and abstraction, and
> persuade the student to choose the appropriate view.
I thought Parnas resolved that circa the development innovation
modularization / incapsulation / data hiding.
Is a whole new bunch of programmers (and I know you are not one of them)
rediscovering the square wheel?
>The lack
> today of simple but complete systems, such as were built around the
> 8080, is a drawback. A stack is a detail, automatic storage is an
> abstraction.
I do not consider that necessary to learn about systems. Laszlos's book
System View of the World will be adequate
>
> --
> "If you want to post a followup via groups.google.com, don't use
> the broken "Reply" link at the bottom of the article. Click on
> "show options" at the top of the article, then click on the
> "Reply" at the bottom of the article headers." - Keith Thompson
> More details at: <http://cfaj.freeshell.org/google/>
> Also see <http://www.safalra.com/special/googlegroupsreply/>
>
>
| |
| blmblm@myrealbox.com 2006-05-14, 7:03 pm |
| In article <rKCdnaiWgf5W9P7ZRVnygg@bt.com>,
Richard Heathfield <invalid@invalid.invalid> wrote:
>blmblm@myrealbox.com said:
>
>
>Well, for starters, either teach them how to program or tell them not to
>apply for programming jobs. :-)
>
You know, my initial reaction to this was "excellent advice!" --
but one of the advantages (?) of putting off a reply is that there's
time for second thoughts ....
We do get some students who just plain don't like programming
(difficult though that may be for some of us to imagine :-) ).
These students are apt to get discouraged and drop out of CS early
on, because the introductory courses are almost 100% programming.
The ones that stick around, though .... They almost certainly
should be encouraged to find some career path that doesn't involve
programming, even as an entry-level job.
But for the ones who do enjoy programming enough to do it for a
living, at least for a few years, I don't know. I'm not sure we
*can* teach them to program -- we can teach them some rudimentary
skills, but the only way they can become good programmers is to
actually program, and our ability to make them do that is limited
given that we also want to teach them "basic principles" (i.e.,
given them a framework of basic knowledge on which they can hang the
technical details they'll learn in later years). I don't think we
should skimp on the "basic principles" stuff, because that's what
I think we do well, better than the workplace. But the result is
that only the ones who enjoy programming enough to do side projects
really graduate with more than rudimentary programming skills. I'm
not sure we can fix that.
>Seriously, it's not my place to teach you how to teach. But IF IT WERE, then
>I'd suggest the following:
Oh, no need to be so diplomatic -- I asked, right? though if you
want to say it's not your *responsibility* to teach me/us how to
teach, well, yeah ....
However. You may or may not know that how to teach beginning
programming is a topic of perennial debate among people who do it for
a living. In the most recent ACM report on undergraduate curricula
(2001, linked from http://www.acm.org/education/curricula.html),
six, count 'em six, approaches are listed. Something rather like
what you describe is one of them ("hardware first").
>Make sure they have a thorough understanding of an abstract machine, to the
>extent that they can write non-trivial machine code programs in it.
[ snip ]
I like your thinking here. I'm a little biased, maybe -- the first
CS course I took was introductory programming using Fortran, and
though I did well I didn't feel like I understood much, and it wasn't
until I took another course in assembly-language programming (IBM
360 ALC -- that probably dates me, right?) that I started to think
"oh, I get it now ...."
>Then, once they know all that, teach them programming from the clean end.
>:-) High level, in other words. You should find that they pick it up rather
>easily, because they understand what's going on underneath.
Yeah .... And if you don't teach this kind of thing at some point,
I'm inclined to think that on some level the students will never
really understand what they're doing. Then again, one of my
colleagues, a fairly bright guy, claims that by doing this you're
locking them into how things are done now and making it less likely
that they can come up with fresh perspectives, and the right way
to start is with something much more abstract. (He likes J, which
is more or less a descendant of APL.) I don't know. More in responses
to other posts in this thread.
Anyway, a "thank you!" to you and everyone who replied to my question.
It's all being filed for reference next time we argue about curriculum
revisions. :-)
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| blmblm@myrealbox.com 2006-05-14, 7:03 pm |
| In article <44638567$1@news.tulsaconnect.com>,
Jonathan Bartlett <johnnyb@eskimo.com> wrote:
[ snip ]
>However, when I teach
>intro to programming at the local junior college, I have a "Machine
>Language Game" to teach people how the computer works. I have a 16x16
>board representing RAM, a whiteboard segmented into registers, a
>one-line card for the display, and a stack of papers which tell how to
>execute different command codes. I have one student be the data bus,
>one student be the ALU, and one student be the instruction handler, and
>one student be the graphics card. The instruction handler tells the
>data bus to grab the next instruction. The data bus reads it from RAM
>and comes back with the instruction and the next two bytes. The
>instruction handler then looks up the first number in the instruction
>code manual, and does what the manual says. The ALU does what the
>instruction handler says, and the graphics card just watches some memory
>and updates his output whenever it changes, based on the ASCII codes.
>
>It really helps students figure out how the computer really works
>underneath.
Cool idea. And you say this works well in practice? Hm ....
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| blmblm@myrealbox.com 2006-05-14, 7:03 pm |
| In article <4463C372.DA1A0537@yahoo.com>,
CBFalconer <cbfalconer@maineline.net> wrote:
[ snip ]
>In all seriousness though, the fundamental teaching problem is when
>and where to draw the line between detail and abstraction, and
>persuade the student to choose the appropriate view. The lack
>today of simple but complete systems, such as were built around the
>8080, is a drawback. A stack is a detail, automatic storage is an
>abstraction.
Exactly.
Too much focus on details, too early, carries the risk of creating
the impression that whatever detailed system you teach is the only
possible one. I'm not thinking of a really great example of what I
have in mind here -- something along the lines of "if all you know
is Windows, the idea of a powerful command line is unimaginable",
or equivalently, "if all you know is CLIs, the idea of a system with
menus and icons is unimaginable". Starting out with a more abstract
view supposedly avoids this "lock the students into a too-limited
mental model". Can MIT really be totally wrong to start 'em out
in Scheme? (If they're still doing that.)
Then again, too much focus on abstractions carries the risk that they
never really understand .... I think this is especially a risk for
the less-bright students, who aren't very good at abstractions and
when forced to deal with them are apt to just get  and ....
I wonder if this is the origin of that (bad) approach to writing
code that seems to consist of trying things at random until something
seems to work.
--
| B. L. Massingill
| ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| David Lightstone 2006-05-14, 7:03 pm |
|
<blmblm@myrealbox.com> wrote in message
news:4cp81vF173r54U2@individual.net...
> In article <44638567$1@news.tulsaconnect.com>,
> Jonathan Bartlett <johnnyb@eskimo.com> wrote:
>
> [ snip ]
>
>
> Cool idea. And you say this works well in practice? Hm ...
I would say that it will work quite well.
When I learned programming (cerca 1967), the technique was called "desk
checking". The difference being that we did it at the level of the FORTRAN
instruction, rather than the machine instruction.
For those not familiar with the era, batch processing was the norm.
Turnaround time was measured in days, not seconds. It has to compile
correctly the first time. It has to execute correctly the first time.
otherwise you loose several days
..
>
> --
> | B. L. Massingill
> | ObDisclaimer: I don't speak for my employers; they return the favor.
| |
| Torben Ægidius Mogensen 2006-05-15, 4:13 am |
| Ben Pfaff <blp@cs.stanford.edu> writes:
> Richard Heathfield <invalid@invalid.invalid> writes:
>
>
> I know some excellent computer scientists who are not
> programmers. It is not what they do. Their papers read like
> math papers. I could never do what they do, and I wouldn't try
> to claim that I could.
Mathematicians are nearly always good programmers -- if you can
structure a proof of a complex mathematical statement, you can program
also. They might find C++ obstruse and complicated (who doesn't?),
but give them a good functional programming language, and they will
out-program most so-called "programmers".
> For their part, I suspect that they wouldn't claim they are good
> programmers either, at least not in languages like C. Perhaps
> that's the real problem: people who claim to be what they are
> not. But I wouldn't criticize computer scientists for not being
> programmers, as long as they don't claim to be.
Indeed. I would rather criticise someone who calls himself a
programmer and who isn't able to program a sub-quadratic sorting
algorithm without having to consult a textbook (or use a library
routine).
Torben
| |
| S Perryman 2006-05-15, 4:13 am |
| "David Lightstone" <david._NoSpamlightstone@prodigy.net> wrote in message
news:XSL9g.76686$H71.70443@newssvr13.news.prodigy.com...
> <blmblm@myrealbox.com> wrote in message
> news:4cp81vF173r54U2@individual.net...
[color=darkred]
[color=darkred]
[color=darkred]
[color=darkred]
> I would say that it will work quite well.
It worked for me too, but in a different area.
As an undergrad, the CS101 OS course had a similar game for a tutorial.
One person played the dispatcher role , another an I/O device etc.
You really get to see the big picture IMHO.
Regards,
Steven Perryman
| |
| Jonathan Bartlett 2006-05-15, 10:00 pm |
|
>
>
> Cool idea. And you say this works well in practice? Hm ....
I had an adult Walmart stocking clerk who had attended my class by
mistake (she was supposed to be in the "how to use MS Word class" decide
to stay and learn to program... and did every bit as good a job as the
kid who played around with Linux in the offtime.
Because of the game/simulation, she felt she could actually understand
how it all worked together.
Jon
| |
| Andrew Poelstra 2006-05-15, 10:00 pm |
| On 2006-05-15, Jonathan Bartlett <johnnyb@eskimo.com> wrote:
>
>
> I had an adult Walmart stocking clerk who had attended my class by
> mistake (she was supposed to be in the "how to use MS Word class" decide
> to stay and learn to program... and did every bit as good a job as the
> kid who played around with Linux in the offtime.
>
In general, if she herself decided to stay and learn how to code, she'd
be motivated enough to do a good job. Just a thought.
> Because of the game/simulation, she felt she could actually understand
> how it all worked together.
>
That would likely be the main reason that she was motivated. I think I
will steal your idea and use it to teach my class. Thanks!
| |
| Keith Thompson 2006-05-15, 10:00 pm |
| torbenm@app-4.diku.dk (Torben Ægidius Mogensen) writes:
[...]
> Indeed. I would rather criticise someone who calls himself a
> programmer and who isn't able to program a sub-quadratic sorting
> algorithm without having to consult a textbook (or use a library
> routine).
I would criticize any programmer who *bothers* to implement a
sub-quadratic sorting algorithm without consulting a textbook or using
a library routine.
I can write a Quicksort function if I have to -- but I don't have to.
And if I tried it without consulting any references, it's likely the
resulting function would have some (probably subtle) bugs.
I don't remember where I read this, but I seem to recall that there
was a gap of a decade or so between the first implementation of a
binary search algorithm, and the first *correct* implementation of a
binary search algorithm.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Phil Cairns 2006-05-15, 10:00 pm |
| Keith Thompson wrote:
> torbenm@app-4.diku.dk (Torben Ægidius Mogensen) writes:
> [...]
>
> I would criticize any programmer who *bothers* to implement a
> sub-quadratic sorting algorithm without consulting a textbook or using
> a library routine.
Couldn't agree more. And now with work in the real^H^H^H^Hcommercial
world requiring more and more in terms of knowledge of libraries and
SDKs, I'd be completely lost without a second monitor containing a
browser and the online help for my IDE open at all times.
There are some things with which I need to clutter my brain, but stuff
that I wouldn't use more than a couple of times a decade aren't
included. Especially if said stuff was available in one of the
peer-reviewed libraries I can download.
Phil.
| |
| Richard Heathfield 2006-05-16, 7:08 pm |
| Keith Thompson said:
> I can write a Quicksort function if I have to -- but I don't have to.
> And if I tried it without consulting any references, it's likely the
> resulting function would have some (probably subtle) bugs.
I think that's unlikely - in the sense that I am quite confident your
function would sort correctly (after a few muffled curses and a bit more
typing, obviously).
I think it's far /more/ likely that it would in fact be a SlowSort, and that
you could easily write a Shell sort to out-perform it.
Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
fair bit harder.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| David Lightstone 2006-05-16, 7:08 pm |
|
"Richard Heathfield" <invalid@invalid.invalid> wrote in message
news:94idnR7tl79Q4_TZRVnyrA@bt.com...
> Keith Thompson said:
>
>
> I think that's unlikely - in the sense that I am quite confident your
> function would sort correctly (after a few muffled curses and a bit more
> typing, obviously).
>
> I think it's far /more/ likely that it would in fact be a SlowSort, and
> that
> you could easily write a Shell sort to out-perform it.
>
> Implementing Quicksort is pretty easy. Implementing it *efficiently* is a
> fair bit harder.
>
I guess you basic argument is something like - Efficiently is why academics
study such things. Programmers often only need concern themselves with
evaluating whether the algorithm is or is not in conflict with NP
completeness
When you define success that way, I doubt if anyone could possible disagree.
When I first started out (auto industry) success was often being able to
reduce the cost of a part by 1 cent (US). Efficency counted
> --
> Richard Heathfield
> "Usenet is a strange place" - dmr 29/7/1999
> http://www.cpax.org.uk
> email: rjh at above domain (but drop the www, obviously)
| |
| Richard Heathfield 2006-05-16, 7:08 pm |
| David Lightstone said:
>
> I guess you basic argument is something like - Efficiently is why
> academics study such things. Programmers often only need concern
> themselves with evaluating whether the algorithm is or is not in conflict
> with NP completeness
No, that's not what I'm saying at all. In fact, I was agreeing with the idea
that it's far better to write a call to qsort (possibly two minutes to bash
out a comparison function, and another twenty seconds to check the order of
the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
know that Quicksort is faster than Shell sort, so it isn't a question of
choosing which algorithm to use. But having coded up a Shell sort just for
the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
astounded to discover that my Shell sort consistently outperformed my Quick
sort over a large range of data set sizes - tiny, through mid, and right
the way up to huge. Obviously I got my Quick sort wrong. It sorted just
fine, but it took way too long to do it.
> When you define success that way, I doubt if anyone could possible
> disagree.
>
> When I first started out (auto industry) success was often being able to
> reduce the cost of a part by 1 cent (US). Efficency counted
Yeah, but if saving a cent is success, then saving a dollar is a triumph.
The best way to make your sort Quick is to use the standard library's
sorting routine. That cuts down on writing time, debugging time, and run
time.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| Flash Gordon 2006-05-16, 7:08 pm |
| Richard Heathfield wrote:
> David Lightstone said:
>
>
> No, that's not what I'm saying at all. In fact, I was agreeing with the idea
> that it's far better to write a call to qsort (possibly two minutes to bash
> out a comparison function, and another twenty seconds to check the order of
> the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
<snip>
>
> Yeah, but if saving a cent is success, then saving a dollar is a triumph.
> The best way to make your sort Quick is to use the standard library's
> sorting routine. That cuts down on writing time, debugging time, and run
> time.
I agree completely. In addition, if after doing it you find your
libraries quicksort implementation isn't fast enough the best thing to
do is see if you can find a better one that someone else has implemented
and use that.
I'll never write code myself if I can find and legally use some written
by an expert in the field.
--
Flash Gordon, living in interesting times.
Web site - http://home.flash-gordon.me.uk/
comp.lang.c posting guidelines and intro:
http://clc-wiki.net/wiki/Intro_to_clc
Inviato da X-Privat.Org - Registrazione gratuita http://www.x-privat.org/join.php
| |
|
| Richard Heathfield wrote:
> The best way to make your sort Quick is to use the standard library's
> sorting routine.
The truth of that is entirely implementation dependant.
qsort on my implementation,
goes quadratic on worst cases,
and it has more than one kind of worst case,
and it is easy to beat hand coded, for all cases.
Using
http://www.mindspring.com/~pfilandr/C/e_driver/
/* BEGIN e_driver.c program output */
Timing 4 different sorting functions.
Sorting arrays of N number of elements,
in 2 different distributions.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.
Distribution #1: Shuffled
N qisort qrsort m_sort qsort
199998 0.110000 0.109000 0.140000 0.156000
199999 0.110000 0.125000 0.140000 0.157000
Total times:
qisort: 0.220000 qsort interface, center pivot introspective
qrsort: 0.234000 qsort interface, random pivot introspective
m_sort: 0.280000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 0.313000 standard library qsort
Distribution #2: Ramp, Drives center pivot qsorts, quadratic
N qisort qrsort m_sort qsort
199998 0.250000 0.094000 0.078000 0.922000
199999 0.266000 0.094000 0.078000 1.250000
Total times:
qisort: 0.516000 qsort interface, center pivot introspective
qrsort: 0.188000 qsort interface, random pivot introspective
m_sort: 0.156000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 2.172000 standard library qsort
/* END e_driver.c program output */
/* BEGIN e_driver.c program output */
Timing 4 different sorting functions.
Sorting arrays of N number of elements.
The elements are of type long unsigned.
sizeof (long unsigned) is 4.
The times shown are in seconds.
Distribution #1: Two values, Badly written qsorts choke on this
N qisort qrsort m_sort qsort
19998 0.000000 0.000000 0.000000 1.594000
19999 0.000000 0.000000 0.000000 1.593000
Total times:
qisort: 0.000000 qsort interface, center pivot introspective
qrsort: 0.000000 qsort interface, random pivot introspective
m_sort: 0.000000 qsort interface, stable merge, TOO_SMALL is 10
qsort: 3.187000 standard library qsort
/* END e_driver.c program output */
--
pete
| |
| Richard Heathfield 2006-05-16, 7:08 pm |
| pete said:
> Richard Heathfield wrote:
>
>
> The truth of that is entirely implementation dependant.
Naturally, but:
(a) mostly it's true anyway;
(b) in cases where the implementation gives you a lousy qsort, get a better
implementation!
(a) takes care of maybe 90% of the cases. (b) takes care of maybe 90% of
what remains. And even if you're in the unlucky 1%, nevertheless you can
probably still find something on Usenet, written by some guy who calls
himself Lower Case Pete, which does the job for you. So there's no real
need to write it yourself.
--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
| |
| CBFalconer 2006-05-16, 7:08 pm |
| pete wrote:
> Richard Heathfield wrote:
>
>
> The truth of that is entirely implementation dependant.
It is always possible to make quicksort go quadratic solely by the
appropriate input data. See:
SOFTWARE—PRACTICE AND EXPERIENCE, VOL. 29(0), 1–4 (0 1999)
A Killer Adversary for Quicksort
M. D. MCILROY
Dartmouth College, Hanover, NH 03755, USA
I have this as a file mdmspe.pdf on my system. Not sure where I
found it.
You can use sorts with guaranteed worst case performance, such as
heapsort and mergesort. There is no guarantee that the C system
qsort is actually quicksort.
--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson
More details at: <http://cfaj.freeshell.org/google/>
Also see <http://www.safalra.com/special/googlegroupsreply/>
| |
| Googmeister 2006-05-16, 7:08 pm |
|
CBFalconer wrote:
> pete wrote:
[color=darkred]
> It is always possible to make quicksort go quadratic solely by the
> appropriate input data. See:
No, that's not true. If you partition on the median element,
you can guarantee O(n log n) - admittedly finding the median
in linear time is not so practical. Alternatively, if you
partition on a random element (using a good source of
randomness), no fixed input will make it go quadratic.
> SOFTWARE-PRACTICE AND EXPERIENCE, VOL. 29(0), 1-4 (0 1999)
> A Killer Adversary for Quicksort
> M. D. MCILROY
> Dartmouth College, Hanover, NH 03755, USA
This is a great paper, but the technique only apply to a
certain (but broad) class of partitioning schemes.
| |
| Keith Thompson 2006-05-17, 7:03 pm |
| Richard Heathfield <invalid@invalid.invalid> writes:
> David Lightstone said:
>
>
> No, that's not what I'm saying at all. In fact, I was agreeing with the idea
> that it's far better to write a call to qsort (possibly two minutes to bash
> out a comparison function, and another twenty seconds to check the order of
> the args in K&R) than to spend two hours getting Quicksort /wrong/. We all
> know that Quicksort is faster than Shell sort, so it isn't a question of
> choosing which algorithm to use. But having coded up a Shell sort just for
> the hell of it, and then a Quick sort because I'm-so-smart-I-can, I was
> astounded to discover that my Shell sort consistently outperformed my Quick
> sort over a large range of data set sizes - tiny, through mid, and right
> the way up to huge. Obviously I got my Quick sort wrong. It sorted just
> fine, but it took way too long to do it.
Some things to keep in mind:
The basic Quicksort algorithm is quadratic (O(N**2)) for some inputs.
There are various ways to tweak it to avoid this problem, such as
being smarter about picking a pivot value.
The best possible performance for a sorting algorithm (using only a
certain set of operations) is O(n log n). Quicksort isn't the only
O(n log n) sorting algorithm.
Despite the name, there is no requirement for C's qsort() function to
be implemented using the Quicksort algorithm. No sane implementer
would use a quadratic algorithm for qsort(), but it would be legal.
(Perhaps the DS9K does this.)
The qsort() function does impose a significant performance overhead
compared to a hand-written sorting routine. It has to perform an
indirect function call for each comparison. If you re-implement the
exact same algorithm used by your implementation, but using inline
comparisons, you'll probably get a constant factor speedup. There are
undoubtedly cases where this would be worth doing -- *if* you've
measured the actual performance and determined that it's significant.
For sufficiently small arrays, the complexity of Quicksort and other
O(n log n) algorithms can make them slower than quadratic algorithms
like insertion sort. One common approach is to use Quicksort, but
fall back to something like insertion sort for small subarrays.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Keith Thompson 2006-05-17, 7:03 pm |
| "Googmeister" <googmeister@gmail.com> writes:
> CBFalconer wrote:
>
>
> No, that's not true. If you partition on the median element,
> you can guarantee O(n log n) - admittedly finding the median
> in linear time is not so practical. Alternatively, if you
> partition on a random element (using a good source of
> randomness), no fixed input will make it go quadratic.
One approach I've seen is to take the median of the first, middle, and
last elements, and use that as the pivot.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.
| |
| Ben Pfaff 2006-05-17, 7:03 pm |
| "Googmeister" <googmeister@gmail.com> writes:
> No, that's not true. If you partition on the median element,
> you can guarantee O(n log n) - admittedly finding the median
> in linear time is not so practical.
It's possible, though:
http://en.wikipedia.org/wiki/ Selec...
tion_algorithm
--
int main(void){char p[]=" ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmn
opqrstuvwxyz.\
\n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
);while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p[i]\
);}return 0;}
| |
|
| Keith Thompson wrote:
>
> "Googmeister" <googmeister@gmail.com> writes:
I've read about that, but never seen real C code for it.
[color=darkred]
>
> One approach I've seen is to take the median of the first, middle, and
> last elements, and use that as the pivot.
That goes quadratic with the "ramp" pattern,
which has ascending element values until the middle
and then descending until the end.
void ramp(long *a, size_t n)
{
const size_t N = n;
const size_t mid = N / 2;
while (n != mid) {
*a++ = N - n--;
}
while (n != 0) {
*a++ = n--;
}
}
--
pete
| |
|
| Keith Thompson wrote:
> The qsort() function does impose a significant performance overhead
> compared to a hand-written sorting routine. It has to perform an
> indirect function call for each comparison. If you re-implement the
> exact same algorithm used by your implementation, but using inline
> comparisons, you'll probably get a constant factor speedup.
A constant factor speedup of the comparisons
won't give you a constant speedup factor of the algorithm
unless the algorithm spends 100% of it's time doing comparisons.
If you hand code for sorting arrays of a specific element type,
then you can use an assignment operation to move the data,
(unless the element types are arrays,)
which is probably going to be faster than what qsort does,
when the type is larger than int.
I recall seeing on this newsgroup, a URL to a paper which
described a highly, if not totally,
portable way for qsort to tell if the element types
are aligned for type int.
--
pete
| |
| David Wagner 2006-05-17, 7:03 pm |
| pete wrote:
>Keith Thompson wrote:
>
>A constant factor speedup of the comparisons
>won't give you a constant speedup factor of the algorithm
>unless the algorithm spends 100% of it's time doing comparisons.
Huh? If the sorting algorithm spends a constant fraction of its time
doing comparisons (which it does), then speeding up the time to do
a comparison by a constant factor will speed up the algorithm by a
constant factor.
Example: If 50% of the time is spent on comparisons, then speeding up
comparisons by a factor of 10x will speed up the overall computation
time by a factor of 1.82x. To put it another way, if the original
implementation spends 0.5 N cycles on comparisons and 0.5 N cycles on
other operations, and you find some way to reduce the total cost of the
comparisons to 0.05 N cycles, then you'll have reduced the total cost
to 0.55 N cycles. Reducing the runtime from N to 0.55 N is a speedup
by a constant factor.
| |
|
| David Wagner wrote:
>
> pete wrote:
>
> Huh? If the sorting algorithm spends a constant fraction of its time
> doing comparisons (which it does),
It doesn't.
The tendency is for the ratio of comparisons to data movements
to increase as the number of elements increases.
> then speeding up the time to do
> a comparison by a constant factor will speed up the algorithm by a
> constant factor.
--
pete
| |
|
| pete wrote:[color=darkred]
>
> David Wagner wrote:
>
> It doesn't.
> The tendency is for the ratio of comparisons to data movements
> to increase as the number of elements increases.
>
I just made some measurments
on a quicksort with Sedgewick style loops.
The average comparisons/swap ratio with 1999 elements was 5.23
The average comparisons/swap ratio with 19999 elements was 5.53
.... which is small enough of an increase
for me to say that you guys are right,
and I was wrong.
--
pete
| |
| Torben Ægidius Mogensen 2006-05-18, 4:01 am |
| Ben Pfaff <blp@cs.stanford.edu> writes:
> "Googmeister" <googmeister@gmail.com> writes:
>
>
> It's possible, though:
> http://en.wikipedia.org/wiki/ Selec...
tion_algorithm
Yes, but the deterministic O(n) algorithms for median finding are so
slow that it isn't worth the effort. It is faster to first randomize
the array and then use the first element of each subarray as the
pivot. While the worst case is still quadratic, the probability of
that is very low and no fixed pattern (ascending, descending, ramp,
etc.) can defeat it.
When I want to find the median of a long sequence, I usually use a
modified quicksort algorithm:
median xs
= let (len,xs1) = randomize xs -- shuffle and find length
in
nth (len `div` 2) xs1
nth 1 (x:xs) = x
nth n (x:xs)
= let (m,ys,zs) = splitAt x xs 0 [] [x]
in
if n<=m then nth n ys
else nth (n-m) n zs
splitAt x [] m ys zs = (m,ys,zs)
splitAt x (v:vs) m ys zs
= if v<x then splitAt x vs (m+1) (v:ys) zs
else splitAt x vs m ys (v:zs)
Torben
| |
| Googmeister 2006-05-18, 8:02 am |
|
pete wrote:
> pete wrote:
>
> I just made some measurments
> on a quicksort with Sedgewick style loops.
>
> The average comparisons/swap ratio with 1999 elements was 5.23
> The average comparisons/swap ratio with 19999 elements was 5.53
These seems consistent with a more rigorous analysis of
(randomized) quicksort.
Avg # comparisons ~ 2n ln n
Avg # swaps ~ 1/3 n ln n
The ratio converges to 6 as n gets large.
|
|
|
|
|