I promised I would post the iterative version of some
code that was posted before in this Newsgroup. I'm a man of
my word, so here it is.
There are some interesting issues that are being raised
up on this subject thread, and I wish I had the time to respond
to them. There's way too many things that I need to get done.
BTW, anyone looking for a job? Lisp programmers need not apply
(Take it easy, I'm just kidding :) )
Well, anyway I'd like to say goodbye to all the people
that responded to this thread. Take a look at the program below,
and enjoy messing around with it, and improving it. See ya. If
you need to contact me, please feel free to send E-Mail.
Peaceman
--------------------------------------------------------------------
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#define tree_size 20
typedef struct _tree_node
{
int key;
struct _tree_node *left;
struct _tree_node *right;
} tree_node;
typedef tree_node * ptree_node; /* ptree_node is a pointer to a
tree node. */
/* It's always a good idea to declare your functions in advance.
* They are usually put in a .h file. You should know better than
* that Marco :) ,
* since it is neccesary to declare functions in advance for
* two or more mutually recursive functions. Otherwise, you
* will either be unable to compile, or get implicit declarations
* for your functions.
*/
void insert (tree_node *tree, int value);
void preorder_traversal (tree_node *tree);
void nonrecursive_preorder_traversal (ptree_node tree);
void np_preorder_traversal (tree_node *tree); /* your function with
the printing
disabled */
void np_nonrecursive_preorder_traversal (ptree_node tree);
/* The nonrecursive
function with
printing disabled */
/* global vars for the stack */
ptree_node thestack[tree_size]; /* the actual stack */
ptree_node * sp=thestack; /* the stack pointer
initialized to point to the
beginning of the stack */
/* Macro definitions for push and pop */
#define pop() (*sp--)
#define push(pt) (*++sp=(pt));
void insert (tree_node *tree, int value)
{
assert (tree);
if (value == tree->key)
return;
else if (value < tree->key)
{
if (tree->left == 0)
{
tree->left = (tree_node*) calloc (1, sizeof (tree_node));
tree->left->key = value; /* Sorry. No check on malloc return. */
}
else
insert (tree->left, value);
}
else
{
if (tree->right == 0)
{
tree->right = (tree_node*) calloc (1, sizeof (tree_node));
tree->right->key = value; /* Sorry. No check on malloc return. */
}
else
insert (tree->right, value);
}
}
void preorder_traversal (tree_node *tree)
{
if (tree == 0)
return;
else
{
printf ("%d ", tree->key);
preorder_traversal (tree->left);
preorder_traversal (tree->right);
}
}
void np_preorder_traversal (tree_node *tree)
{
if (tree == 0)
return;
else
{
/* printf ("%d ", tree->key); */
np_preorder_traversal (tree->left);
np_preorder_traversal (tree->right);
}
}
/* This function does a preorder traversal of the tree with the root
* head. It is implemented iteratively. No recursive calls.
*/
void nonrecursive_preorder_traversal (ptree_node tree) {
static ptree_node temp; /* Temporary pointer to a tree node
structure */
push(NULL); /* Push NULL on the stack, to indicate the stopping
point */
/* for the pop statement in the while loop. */
push(tree); /* Set the starting point for the tree traversal */
while(temp = pop()) {/* Keep popping off the stack until theres
nothing */
printf ("%d ", temp->key); /* Print the current value on node
temp */
if ( (temp->right) != NULL) push (temp->right);
if ( (temp->left) != NULL) push(temp->left);
/* Push the right and left branches of the tree to */
/* the stack, if the exist. */
}
return; /* done */
}
/* This function does a preorder traversal of the tree with the root
* head. It is implemented iteratively. No recursive calls.
*/
void np_nonrecursive_preorder_traversal (ptree_node tree) {
static ptree_node temp; /* Temporary pointer to a tree node
structure */
push(NULL); /* Push NULL on the stack, to indicate the stopping
point */
/* for the pop statement in the while loop. */
push(tree); /* Set the starting point for the tree traversal */
while(temp = pop()) {/* Keep popping off the stack until theres
nothing */
if ( (temp->right) != NULL) push (temp->right);
if ( (temp->left) != NULL) push(temp->left);
/* Push the right and left branches of the tree to */
/* the stack, if the exist. */
}
return; /* done */
}
void main()
{
tree_node *root = (tree_node*) calloc (1, sizeof (tree_node));
/* __const__ int tree_size = 20; */
int count;
int x,y,z; /* Loop vars */
time_t startime, finishtime; /* The starting and finishing times */
/* Sorry. No system error checking.. */
srand((unsigned)time(NULL)); /* Fixed this to run on uniproccesor
machines */
root->key = rand() % 100;
for (count = 0; count < tree_size; count++)
insert(root, rand() % 100);
puts("recursive Preorder traversal\n");
preorder_traversal(root);
putchar('\n');
puts("\nnonrecursive Preorder traversal\n");
nonrecursive_preorder_traversal(root);
putchar('\n');
/* Heres the benchmark code */
printf("\nRunning nonrecursive preorder traversal 8,000,000
times.\n");
printf("Each dot represents 100,000 calls.\n");
startime = time(NULL);
for(x=1;x<=80;x++) {
for(z=1;z<=100;z++)
for(y=1;y<=1000;y++)
np_nonrecursive_preorder_traversal(root);
putchar('.');
}
finishtime = time(NULL);
printf("\n Total elapsed time in seconds: %d \n",
(int) finishtime - startime);
printf("\nRunning recursive preorder traversal 8,000,000 times.\n");
printf("Each dot represents 100,000 calls.\n");
startime = time(NULL);
for(x=1;x<=80;x++) {
for(z=1;z<=100;z++)
for(y=1;y<=1000;y++)
np_preorder_traversal(root);
putchar('.');
}
finishtime = time(NULL);
printf(" Total elapsed time in seconds: %d \n",
(int) finishtime - startime);
return;
}
In article <·············@capital.net> Sajid Ahmed the Peaceman <········@capital.net> writes:
From: Sajid Ahmed the Peaceman <········@capital.net>
Newsgroups: comp.lang.lisp
CC: ·······@infiniti.Berkeley.edu
Date: Mon, 18 Aug 1997 21:35:26 -0400
Organization: Logical Net
Reply-To: ········@capital.net
Lines: 236
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
X-Mailer: Mozilla 3.01 (WinNT; I)
I promised I would post the iterative version of some
code that was posted before in this Newsgroup. I'm a man of
my word, so here it is.
There are some interesting issues that are being raised
up on this subject thread, and I wish I had the time to respond
to them. There's way too many things that I need to get done.
BTW, anyone looking for a job? Lisp programmers need not apply
(Take it easy, I'm just kidding :) )
Well, anyway I'd like to say goodbye to all the people
that responded to this thread. Take a look at the program below,
and enjoy messing around with it, and improving it. See ya. If
you need to contact me, please feel free to send E-Mail.
Peaceman
Excellent! Yet another unreadable iterative version USING AN EXPLICIT
STACK of an inherently recursive algorithm. (And no! Saying that some
recursion needs a stack is not enough. You need to admit that you
were wrong.)
Have we learned something here? From the response of the Peaceman, I
doubt it. :)
Cheers
--
Marco Antoniotti
==============================================================================
California Path Program - UC Berkeley
Richmond Field Station
tel. +1 - 510 - 231 9472
On Mon, 18 Aug 1997 21:35:26 -0400, Sajid Ahmed the Peaceman
<········@capital.net> posted:
>I promised I would post the iterative version of some
>code that was posted before in this Newsgroup. I'm a man of
>my word, so here it is.
Certainly looks like it's code that does the task in question...
It's rather unfortunate that the iterative version, not unlike the
recursive version, consumes stack space rather in profusion...
All that being said, it's rather unfortunate that the iterative
version proves to be less readable by nature than the recursive
version...
The fact that the recursive version is somewhat slower than the
iterative version is readily explained by the fact that C doesn't
handle stack frame creation with optimal efficiency...
--
Christopher B. Browne, ········@hex.net, ············@sdt.com
PGP Fingerprint: 10 5A 20 3C 39 5A D3 12 D9 54 26 22 FF 1F E9 16
URL: <http://www.hex.net/~cbbrowne/>
Bill Gates to his broker: "You idiot, I said $150 million on **SNAPPLE**!!!"
Sajid Ahmed the Peaceman wheezed these wise words:
> I promised I would post the iterative version of some
> code that was posted before in this Newsgroup. I'm a man of
> my word, so here it is.
> There are some interesting issues that are being raised
> up on this subject thread, and I wish I had the time to respond
> to them. There's way too many things that I need to get done.
> BTW, anyone looking for a job? Lisp programmers need not apply
> (Take it easy, I'm just kidding :) )
> Well, anyway I'd like to say goodbye to all the people
> that responded to this thread. Take a look at the program below,
> and enjoy messing around with it, and improving it. See ya. If
> you need to contact me, please feel free to send E-Mail.
You left without telling us what happens when you compile the
following code with VC++ 4.0 (or later), using "/O2".
#include <stdio.h>
int *p = NULL;
void r(int i)
{
if (p == NULL)
p = &i;
printf("%d %p\n", i, &i);
if (p != &i)
exit(0);
r(i + 1);
}
void main(void)
{
r(1);
}
Anyway, farewell.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
"There are no limits." -- ad copy for Hellraiser
Please note: my email address is gubbish
This thread started with what's-his-name's claim that
recursion was inherently less efficient than iteration. I
once believed that myself, but long ago learned the better.
However, this leads me to ask: where and how did this notion
arise?
What's-his-name may have heard it from one of his (older)
teachers. Because there was a day when this was pretty much
the case, or at least gave a strong impression of being the
case.
Some recursive algorithms can run in fixed space, e.g., those
which are tail-recursive. I'm not interested in those.
Others are inherently recursive, which to me signifies there
is no a priori upper bound on the space required, independent
of the specific case of application. By "space" I include the
call stack necessary to manage the bookkeeping. All recursive
algorithms can be recast in an iterative form through the use
of an explicit stack; however (except in the cases I've
excluded), there can't be an a priori upper bound on the size
of this stack. At the machine-code level the differences
between the two approaches are trivial: on the one hand, the
operating system manages the bookkeeping through its call
stack mechanism, and on the other the program manages it
through its explicit stack. In either case, stack frames are
created and deleted, jump instructions executed.
Most modern operating systems use a call stack, and the
processors they run on have instructions and features to
facilitate the use of a call stack. But it was not always
thus. Let's go back to the early 60's, when the IBM 7094 was
state-of-the-art. There was no call stack, and no features in
the hardware to support one. Memory was hugely expensive and
scarce by today's standards: multi-million dollar mainframes
had no more RAM than some of today's hand-helds, and often a
lot less. It was out of the question for the operating system
to reserve a significant amount of memory for something like a
call stack, which might or might not be used by any specific
program. A compiler might arrange a call stack in it's run
time code, or it might create some other memory management
mechanism supporting recursion, but it would pay a heavy price
in terms of memory: some large block of memory would have to
be dedicated to the possibility, not the certainty, of being
needed.
In the IBM 360 series (mid 60's), the OS had a feature
allowing a program to request additional pages from the
operating system. A recursive program might contain code for
such calls. The bottom line here is that the program
(including the run-time code generated by the compiler) had to
have its own memory management system, which might involve
time-consuming calls to the operating system. A PL/I program
already had a large prelude; just adding the word "recursive"
somewhere added a couple of pages to the assembly language
listing. Recursion looked expensive, and basically, it was.
So it's no wonder it got a bad name.
Let's not eschew recursion because of some out-of-date wisdom.
--
John Doner, UCSB Math. Dept., ·····@math.ucsb.edu
John Doner wheezed these wise words:
> Let's not eschew recursion because of some out-of-date wisdom.
A little history can be very informative. I didn't have the details,
but I've read about the introduction of hardware support for stacks.
Many CPU features that we take for granted today were created at some
point in computing history.
It may be hard to believe, but it appears that even CPU registers
haven't always existed. (I've seen them credited to the late Seymour
Cray, BTW.) These things are easily "forgotten" by later generations.
By the time I began playing with computers (micros, in fact), it was
very late in the game, and so none of this history was available from
manuals etc. I had to pick up some of it from - yes, you guess it -
computer science books. Some of the authors of these tomes have wisely
included the history of various ideas. Like disoveries in other areas
of science, ideas can occur to several people simultaneously, even
when they've never met.
The truth is out there. If you're prepared to look for it, then you'll
see that it's not that hard to find. You can even find some of it
online. However, you'll have to accept that some of it may be a little
hard to believe, at first. Since nobody can claim to know everything
that is happening or has happened in computing, there will inevitably
be a few suprises. Some of them may be big suprises, but I guess that
would depend on how well you know the limits of your own knowledge.
As you pointed out, "wisdom" (i.e. knowledge) can age. Without an
expiry date, how can we tell when something is no longer true? The
great risk is to assume that the limits of your knowledge and the
limits of what is possible are the same. That is, that you all there
is to know about some subject, that this will never change, that no
new discoveries will - or can ever - be made.
Follow the examples of various Popes, and re-evaluate the "truth" once
in a while. ;) Vaccums _do_ exist! Strange but true. Even evolution is
now accepted as a reality. Maybe one day a Pope will decree that tail
recursion can be done O(1) space.
--
<URL:http://www.wildcard.demon.co.uk/> You can never browse enough
"As you read this: Am I dead yet?" - Rudy Rucker
Please note: my email address is gubbish
>>>>> "GB" == Georg Bauer <···········@ms3.maus.westfalen.de> writes:
GB> Sajid Ahmed the Peaceman <········@capital.net> wrote:
>> I promised I would post the iterative version of some code that
>> was posted before in this Newsgroup. I'm a man of my word, so
>> here it is.
GB> That's not true iterative - you are using a simulated
GB> stack. Actually you only do what the compiler would do. Just
GB> to leave out the _function_call_ doesn't make an algorithm
GB> non-recursive. Your algorithm still is recursive, it's just
GB> differently (and much uglier IMO) coded.
100% agree.
GB> And actually I don't see why one should do that - simulating a
GB> stack. Actually current processors have a highly efficient
GB> implementation of a stack in them, already. Why not use it?
Exactly what I thought, and this is what I got, after running the
program through stock GCC 2.7.2.2 with
gcc -O6 -fomit-frame-pointer -Wall -ansi -pedantic and
running it on a lowly AMD5x86-133 under Linux 2.0:
<screen>
recursive Preorder traversal
68 26 21 0 20 2 35 27 48 43 59 82 76 72 71 80 86 95
nonrecursive Preorder traversal
68 26 21 0 20 2 35 27 48 43 59 82 76 72 71 80 86 95
Running nonrecursive preorder traversal 8,000,000 times.
Each dot represents 100,000 calls.
................................................................................
Total elapsed time in seconds: 39
Running recursive preorder traversal 8,000,000 times.
Each dot represents 100,000 calls.
................................................................................ Total elapsed time in seconds: 38
</tscreen>
Now this should tell us something, especially since this is under C,
which is traditionally not good at optimizing funcalls. I'd expect
the results to be more drastic under CL/Scheme...
So what we get in summary:
More time spent writing the "iterative" version
Uglier, unmaintainable code generated
More possible bugs introduced
Net gain in speed: 0/Zero/nil/zilch/nada...
As had of course been expected...
GB> A better way is to optimize your data-structures to fit the
GB> problem. If the problem is minimal stack consumption on
GB> traversal, why not use some balanced tree structure?
This is of course a much better course of action, but requires much
more careful analysis, than the simple-minded "My Program is Slow" ->
"Write iteratively instead", or even "Never use recursion, it is
slow".
This is true of optimization (and many other areas) in general: There
is no silver bullet. You need to carefully analyze and profile your
code, and only then can you tune the hot parts of your program, in
sometimes non-obvious ways. And this of course only happens _after_
the program is running correctly, and a regression-test-suite has been
built, to verify the continued correct operation of the program after
optimization.
Regs, Pierre.
[CC'ed to our friend]
Pierre Mai (····@cs.tu-berlin.de) wrote:
: >>>>> "GB" == Georg Bauer <···········@ms3.maus.westfalen.de> writes:
: GB> And actually I don't see why one should do that - simulating a
: GB> stack. Actually current processors have a highly efficient
: GB> implementation of a stack in them, already. Why not use it?
: Exactly what I thought, and this is what I got, after running the
: program through stock GCC 2.7.2.2 with
: gcc -O6 -fomit-frame-pointer -Wall -ansi -pedantic and
: running it on a lowly AMD5x86-133 under Linux 2.0:
: Running nonrecursive preorder traversal 8,000,000 times.
: Total elapsed time in seconds: 39
: Running recursive preorder traversal 8,000,000 times.
Total elapsed time in seconds: 38
: Now this should tell us something, especially since this is under C,
: which is traditionally not good at optimizing funcalls. I'd expect
: the results to be more drastic under CL/Scheme...
: So what we get in summary:
: More time spent writing the "iterative" version
: Uglier, unmaintainable code generated
: More possible bugs introduced
: Net gain in speed: 0/Zero/nil/zilch/nada...
: As had of course been expected...
Thanks very much for the timings, Pierre! I must say I'm amazed, as I
had expected the own stack management to be slightly faster than the
explicitly recursive function, as only one word need be pushed/popped
onto/from the stack in the former case. I think I'll compile the
functions one my Amiga and see if the result varies. A very nice
argument *pro* recursion and most readable code.
Regards,
Jo"rg Ho"hle.
············@gmd.de http://zeus.gmd.de/~hoehle/amiga-clisp.html