Code optimization techniques

Announcements, comments, ideas, feedback, and "How do I... ?" questions
User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Code optimization techniques

Post by uws8505 » Tue Nov 25, 2008 9:52 am

May I have some of the techniques used frequently to optimize a program i.e. to decrease time taken to get an answer?

For example, building a list is often better than branched recursion(at least I think this one is correct, but I'm not sure)
Math and Programming are complements

User avatar
xan
Posts: 621
Joined: Fri Jul 27, 2007 11:43 pm
Location: North Carolina, USA
Contact:

Re: Code optimization techniques

Post by xan » Tue Nov 25, 2008 1:14 pm

See TopCoder tutorials and other more general Google searches. Research dynamic programming, memoization, and sieving.

User avatar
uws8505
Posts: 58
Joined: Tue Sep 30, 2008 2:13 pm
Location: South Korea

Re: Code optimization techniques

Post by uws8505 » Tue Nov 25, 2008 1:37 pm

Oh, thanks for your help.
Math and Programming are complements

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sat Dec 29, 2018 10:22 pm

Trying to learn more about Dynamic Programming vs Recursion and about Tabulation vs Memoization, particularly the latter, as aided by Geeks for Geeks (which I highly recommend for beginner-intermediates like me).

Geeks for Geeks presents an application of Memoization to computing the "n"th Fibonacci number, by recursively referencing a so-called "lookup" table/array.

I will enter their/my code below but to get right to my question -- I've printed out a statement for each call to the recursive function and a listing of the lookup array going into that call, as follows, and I just don't understand --
Why does lookup[2] become 1 from the prior fib(0) call?
Maybe because I turn 71 tomorrow? :-?

fib(5) called with: ***************************** 9 calls total vs 15 for Top-Down Recursion w/o lookup *******************
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(0) called with:
[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] first change, via prior fib(1) and if(n <= 1) lookup[n] = n so lookup[1] = 1

fib(1) called with:
[0, 1, 1, -1, -1, -1, -1, -1, -1, -1] via prior fib(0) and if(n <= 1) lookup[0] = 0 BUT lookup[2] = 1 also??

fib(2) called with:
[0, 1, 1, 2, -1, -1, -1, -1, -1, -1] via prior fib(1)

fib(3) called with:
[0, 1, 1, 2, 3, -1, -1, -1, -1, -1] via prior fib(2)


Fibonacci(5) = 5

Code: Select all

/*
a) Memoization (Top Down): 

The memoized program for a problem is similar to the recursive version with 
a small modification that it looks into a lookup table before computing solutions. 
We initialize a lookup array with all initial values as NIL. 
Whenever we need the solution to a subproblem, we first look into the lookup table. 
If the precomputed value is there then we return that value, otherwise, 
we calculate the value and put the result in the lookup table so that it can be reused later.

Following is the memoized version for nth Fibonacci Number.

// Java program for Memoized version 
public class Fibonacci 
{ 
  final int MAX = 100; 
  final int NIL = -1; 
  
  int lookup[] = new int[MAX]; 
  
  // Function to initialize NIL values in lookup table 
  void _initialize() 
  { 
    for (int i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
  } 
  
  // function for nth Fibonacci number 
  int fib(int n) 
  { 
    if (lookup[n] == NIL)	//Recursion Function but How can lookup[] even be referenced?! Via f._initialize()? 
    { 
      if (n <= 1) 
          lookup[n] = n; 
      else
          lookup[n] = fib(n-1) + fib(n-2); 
    } 
    return lookup[n]; 
  } 
  
  public static void main(String[] args) 
  { 
    Fibonacci f = new Fibonacci(); 
    int n = 9; 
    f._initialize(); 
    System.out.println("Fibonacci number is" + " " + f.fib(n)); 
  } 
  
} 
// This Code is Contributed by Saket Kumar
 
Both Tabulated and Memoized store the solutions of subproblems. 
In Memoized version, table is filled on demand while in Tabulated version, 
starting from the first entry, all entries are filled one by one. 
Unlike the Tabulated version, all entries of the lookup table are not necessarily filled in Memoized version. 
For example, Memoized solution of the LCS problem doesn’t necessarily fill all entries.
--------------------------------------------------------------------------------------------------------------------
OUTPUT from my slightly modified code which is below:

   fib(5) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

   fib(4) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

   fib(3) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

   fib(2) called with:
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

   fib(1) called with:			   *********9 calls vs 15 for Top-Down Recursion w/o lookup*********
[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

   fib(0) called with:
[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] first change, via prior fib(1) and if(n <= 1) lookup[n] = n so lookup[1] = 1

   fib(1) called with:
[0, 1, 1, -1, -1, -1, -1, -1, -1, -1]	via prior fib(0) and if(n <= 1) lookup[0] = 0 BUT lookup[2] = 1 also??
										          ******************
   fib(2) called with:
[0, 1, 1, 2, -1, -1, -1, -1, -1, -1]	via prior fib(1)

   fib(3) called with:
[0, 1, 1, 2, 3, -1, -1, -1, -1, -1]	via prior fib(2)


Fibonacci(5) =  5		
--------------------------------------------------------------------------------------------------------------------
*/

import java.util.Arrays;			

class GeekFibonacciMemoization		//w/o public... and apparently unnecessary 
{
  int MAX = 10;				//w/o final... and apparently unnecessary 
  int NIL = -1;				//w/o final... and apparently unnecessary 
 
  int lookup[] = new int[MAX]; 

  // Function to initialize NIL values in lookup table 
  void _initialize() 
  { 
    for (int i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
  } 
  
  // Function for nth Fibonacci number 
  int fib(int n) 
  {
System.out.println("   fib(" +n+ ") called with:");
System.out.println(Arrays.toString(lookup));
System.out.println();
 
    if (lookup[n] == NIL) 
    { 
      if (n <= 1) 
          lookup[n] = n; 
      else
          lookup[n] = fib(n-1) + fib(n-2); 
    } 
    return lookup[n]; 
  } 
  

  public static void main(String[] args)
  {
    GeekFibonacciMemoization f = new GeekFibonacciMemoization();

    System.out.println();
 
    int n = 5; 
    f._initialize();
 
    System.out.println("Fibonacci(" +n+ ") = " + " " + f.fib(n));
  } 
  
}
Last edited by kenbrooker on Mon Dec 31, 2018 3:09 pm, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

MHealy
Posts: 38
Joined: Sat Nov 17, 2012 11:32 pm

Re: Code optimization techniques

Post by MHealy » Sun Dec 30, 2018 1:10 am

kenbrooker wrote:
Sat Dec 29, 2018 10:22 pm
Why does lookup[2] become 1 from the prior fib(0) call?
It isn't set in the prior fib(0) call, it's set in the prior fib(2) call, but this call has only completed after the fib(0) which it called has completed. The second call to fib(1), where lookup[2] first appears as 1, is part of calculating fib(3), which happens after we have finished the first call to fib(2) and set lookup[2] to 1.

It might help when testing things like this to have a "depth" parameter in a recursion which you increment with each call. And then, for example, use the depth to add a number of spaces/tabs before each line when outputting it, to get a better idea of where you are. I think it would look something like this, with the general flow of the program being to go in as "deep" as it can, then back up to the function which called it and then down to the next thing:

Code: Select all

fib(5) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	fib(4) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
		fib(3) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
			fib(2) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
				fib(1) called with: [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
				fib(0) called with: [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
			fib(1) called with: [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] // *****
		fib(2) called with: [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
	fib(3) called with: [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
Which hopefully makes it a bit clearer what is going on, and that the suspect call to fib(1) is happening after we have already finished calling fib(2), come out of the level of the recursion, and are now carrying on our calculation of fib(3) by calling fib(1) after the fib(2) call has completed and set lookup[2].
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sun Dec 30, 2018 3:11 am

Thanks for a Fine
Birthday Gift
MHealy...

I definitely get lost in recursion and I like your "depth" idea, anything to help me follow the fatal, to me, complication that you describe as "then back up to the function which called it and then down to the next thing."
I think my key problem is concerning the Stack, specifically relating to "return" statements, and
I hope you will bear further with me for a very different approach.

For this fairly simple recursive code with the same
Preorder Straight "Tree" as my Fibonacci code:

Code: Select all

import java.util.Arrays;			

class GeekRecursionMemoryProc
{
	void printFun(int test)
	{
System.out.println("  		printFun(" +test+ "):");
    		if (test < 1)						 
        		return;						// statement 0					 
    		else
    		{ 
        		System.out.println("   test1 = " +test);	// statement 1
 
        		printFun(test-1); 				// statement 2
 
        		System.out.println("   test3 = " +test);	// statement 3
 
        		return;						// statement 4 
    		}
	} 
}

class GeekRecursionMemory		 		
{
public static void main(String args [ ])
{
	double start = System.currentTimeMillis();

	System.out.println();

	GeekRecursionMemoryProc F = new GeekRecursionMemoryProc();		

	F.printFun(3);

System.out.println();	
							
	double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");					
} 
}
The "back ups and then downs" make sense to me as follows
with regard to the Stack --


   test1 = 3						3
   test1 = 2					       /
   test1 = 1					      2		PreOrder "Tree"
   (test = 0)					     /           3 2 1 0 1 2 3 					
   test3 = 1					    1
   test3 = 2					   /
   test3 = 3				          0

RunTime = 0.0 Secs


       	          CALLED
    Printed     ***********
   *********	printFun(3): 	local test initialized to 3 and statements 4 to 0 pushed on stack and 0 false and 
   test1 = 3				test1 = 3 printed by statement 1 and printFun(2) called by statement 2
 
		printFun(2): 	local test initialized to 2 and statements 4 to 0 pushed on stack and 0 false and
   test1 = 2				test1 = 2 printed by statement 1 and printFun(1) called by statement 2
 
		printFun(1): 	local test initialized to 1 and statements 4 to 0 pushed on stack and 0 false and
   test1 = 1				test1 = 1 printed by statement 1 and printFun(0) called by statement 2

   (test = 0)   printFun(0):	local test initialized to 0 and statement 0 reads if(0 < 1) return to...
 
		printFun(1):	finding printFun(1) statement 3 at top of stack
   test3 = 1				test3 = 1 printed by statement 3 and statement 4 is return to... 

		printFun(2):	finding printFun(2) statement 3 at top of stack
   test3 = 2				test3 = 2 printed by statement 3 and statement 4 is return to...

		printFun(3):	finding printFun(3) statement 3 at top of stack
   test3 = 3				test3 = 3 printed by statement 3 and statement 4 is return to/from empty stack

RunTime = 0.0 Secs

Now if I try to take the same approach with my Fibonacci code
with Statement numbers added --

Code: Select all

    if (lookup[n] == NIL)			//statement 0 
    { 
      if (n <= 1) 
          lookup[n] = n;			//statement 1 
      else
          lookup[n] = fib(n-1) + fib(n-2);	//statement 2 
    } 
    return lookup[n];				//statement 3 
  }
I end up with the following and don't understand how to
handle the return lookup[n] Statements (#3)
with regard to the Stack --


   
   CALLED
   ******
   fib(5)	local n initialized to 5 and statements 3 to 1 pushed on stack

   fib(4)	local n initialized to 4 and statements 3 to 1 pushed on stack

   fib(3)	local n initialized to 3 and statements 3 to 1 pushed on stack

   fib(2)	local n initialized to 2 and statements 3 to 1 pushed on stack

   fib(1)	local n initialized to 1 and lookup[1] = 1 by statement 1* and statement 3 return does what?

   fib(0)	local n initialized to 0 and lookup[0] = 0 by statement 1* and statement 3 return does what?

   fib(1)

   fib(2)

   fib(3)
                                                                         *Probably NOT, Right?
Last edited by kenbrooker on Tue Jan 01, 2019 10:44 pm, edited 25 times in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

MHealy
Posts: 38
Joined: Sat Nov 17, 2012 11:32 pm

Re: Code optimization techniques

Post by MHealy » Sun Dec 30, 2018 4:09 am

kenbrooker wrote:
Sun Dec 30, 2018 3:11 am
Thanks for a Fine
Birthday Gift
MHealy...
You're welcome :D

I may make some mistakes/incorrect technical descriptions when using "stack" and "stack frame" :oops: However, I think I can roughly explain the issue here. The line (for example)
fib(5) local n initialized to 5 and statements 3 to 1 pushed on stack
is not quite correct.

After we see statement 1 does not apply, we move onto statement 2. But it is not treated all in one go. We first see we need "fib(4)", so this creates a new stack frame where we now have local n = 4. (I guess we "freeze" inside this statement in the fib(5) stack frame, and create a new one for fib(4), but I am actually curious how this works in practice with the "overall" stack :? I'll have to look into it!) We then need fib(3) but this is being called from inside fib(4), NOT as the "second half" of the fib(5) statement 2. Then fib(2) (again, being called from fib(5)->fib(4)->fib(3)->fib(2) so all are on the stack, each with a new frame/local n).

Inside fib(2), we can calculate fib(1) (put it on stack, add fib(1) result to our cache, pop it off in the return) and fib(0) (similarly). Once we have calculated these, we are back in fib(2) and can now add the result of fib(1) + fib(0) to our cache in lookup[2] and return the result of fib(2) - the "return" statement in fib(2) is not considered until after fib(1) and fib(0) have already been added to the stack, populated the lookup, and returned their results to fib(2) stack frame.

Now we're back in fib(3), and we just got fib(2) returned (and put in the cache). Next, we continue with the second half of statement 2 (inside fib(3)), and call fib(1). This is the call where we see lookup[2] (and lookup[1]) are populated, so no further recursion is needed.

We can then return fib(3) to fib(4), and then inside fib(4) we next call fib(2) (already cached), then add fib(4) to the cache and get back to fib(5) (pop our first fib(4) call from the stack). Now we make our second call to fib(3), which is already cached so we're done. This is when we have finally finished with the "statement 2" from the fib(5) call.

In summary, inside fib(5) we FIRST add a new fib(4) to the stack (as part of statement 2), but then we deal with fib(4) completely before popping it off and adding fib(3) to the stack - the first fib(3) call in inside fib(4), not fib(5)). Maybe the "second half" of fib(5) is on the stack (... somewhere), but we do not meet it until we've dealt the everything inside fib(4)'s frame.

So the stack builds up roughly like this:

Code: Select all

fib(5)					// add fib(5) to stack
fib(5)->fib(4)				// add fib(4) to stack
fib(5)->fib(4)->fib(3)			// add fib(3) to stack (from inside fib(4) function)
fib(5)->fib(4)->fib(3)->fib(2)		// add fib(2) to stack (from inside fib(3) function)
fib(5)->fib(4)->fib(3)->fib(2)->fib(1)	// add fib(1) to stack, return it (pop from stack)
fib(5)->fib(4)->fib(3)->fib(2)->fib(0)	// add fib(0) to stack, return it (pop from stack)
fib(5)->fib(4)->fib(3)->fib(2)		// back to fib(2) , NOW we hit statement 3/ return
fib(5)->fib(4)->fib(3)->fib(1)		// add fib(1) to stack (from inside fib(3) function)
fib(5)->fib(4)->fib(3)			// return fib(3)
fib(5)->fib(4)->fib(2)			// return fib(2)
fib(5)->fib(4)				// return fib(4)
fib(5)->fib(3)				// add fib(3) to stack (from inside fib(5) function), return it from cache
fib(5)
If somebody else has a better understanding of exactly how this works in terms of "the stack", and/or corrections, I'd like to hear it :D
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sun Dec 30, 2018 4:38 am

Gee MHealy...
Couldn't you be...
Briefer?!

Just kidding!! Look at the two lengthy Posts I inflicted upon you and I am amazed at your
Patience, Speed, "Depth" of Reply, and SUPER Kindness, e.g. "not quite correct"... :-D

Well, my first impression is that I wasn't even close to understanding the Stack...
There's a Hell of a lot more going on than I realized and
I look forward to studying your Reply but,
I just want to Thank You ASAP and
Wish You a Happy New Year!

ps - I don't even know what
a/the "cache" is!
:shock:
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

MHealy
Posts: 38
Joined: Sat Nov 17, 2012 11:32 pm

Re: Code optimization techniques

Post by MHealy » Sun Dec 30, 2018 4:57 am

Haha, yes I feel like I did repeat myself a little but unfortunately it is quite late (or early :lol: ) here so I won't be able to edit it much tonight. The "rambling" nature perhaps tells me I am not familiar enough with the subject to be trying to explain it :D I am very much open to somebody else coming here with a much more concise/correct explanation.

But when I say cache I just mean your array (lookup) in this case, not anything more technical than that. (As a noun - "the cache" - I am talking about the array; as a verb - "cached" - I am talking about adding something to the array.)
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sun Dec 30, 2018 5:15 am

Ohhh... Thanks Again!! and I was TOTALLY Kidding about brevity...
I don't think you rambled at all but then again,
You Level 17s have a High Standard...
:D
Last edited by kenbrooker on Sun Dec 30, 2018 11:50 pm, edited 2 times in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sun Dec 30, 2018 11:03 pm

Well, I guess I'm feeling stubborn on my 71st Birthday (Geriatric Immunity-eligible?) and not yet ready to abandon my
(Robotic) approach to mapping a recursion, specifically re the Stack...

I think we would both arrive at exactly the same "Stack Map" for my printFun example, several Posts above, and I'd like to look at another much more interesting example, much more like the Fibonacci-by-Memoization causing me trouble, and that is PE Problem 517 aka "A Real Recursion" (where, incidentally, the advantage of Dynamic Programming (DP)
over Recursion is demonstrated to the tune of G(100) being 10 times faster; G(121), 100 times faster; and,
G(144), 1000 times faster(!); and, StackOverflowError for Recursion initiates at about G(8200) )...

As usual, I'll show the PE517 code below, Recursive and DP/Tabulation, and
here is my Stack Map for the recursion --

              A							4
            /   \					      /   \
          /       \					    /       \
         D         G 					   3         2
       /   \      /  \                                    /  \      /  \
      H     K    M    C					 2    1    1    0 
     /     /    / \					/ \
    W     R    X   T				       1   0
   / \						       
  E   S                                                 preorder as below
                                                        4 3 2 1 0 1 2 1 0
preorder	A D H W E S K R G M X T C
postorder	E S W H R K D X T M C G A
inorder		E W S H D R K A X M T G C
level order	A D G H K M C W R X T E S



    a = 2.0                                            x
						       4
   x1 = 4.0						
   x2 = 4.0

   x1 = 3.0
   x2 = 3.0			       x-1			       x-a
					3				2
   x1 = 2.0			
   x2 = 2.0			
                                                                                     final
   x1 = 1.0			2		1		1		0 <-- call
   x1 = 0.0				      +one	      +one	      +one
   x1 = 1.0		
   x1 = 2.0
   x2 = 2.0		1		0
	    "return"s: one	      +one
   x1 = 1.0
   x1 = 0.0 <-- 9 calls (count x1s only)

   G(4) = 5.0 via Recursion


[1.0, 1.0, 2.0, 3.0, 5.0] via 3 iterations from [1.0, 1.0] via Dynamic Programming/Tabulation
                     ***
RunTime = 0.0 Secs



       	          CALLED
    Printed     **********
    *******	gaofx(2,4) 	local x initialized to 4 and statements 4 to 1 pushed on stack and
     x1 = 4				x1 = 4 printed by statement 1 and statement 2 false and
     x2 = 4				x2 = 4 printed by statement 3 and
					gaofx(2,3) called by statement 4 and +gaofx(2,2) pushed on stack

   		gaofx(2,3) 	local x initialized to 3 and statements 4 to 1 pushed on stack and
     x1 = 3				x1 = 3 printed by statement 1 and statement 2 false and
     x2 = 3				x2 = 3 printed by statement 3 and
					gaofx(2,2) called by statement 4 and +gaofx(2,1) pushed on stack

   		gaofx(2,2) 	local x initialized to 2 and statements 4 to 1 pushed on stack and
     x1 = 2				x1 = 2 printed by statement 1 and statement 2 false and
     x2 = 2				x2 = 2 printed by statement 3 and
					gaofx(2,1) called by statement 4 and +gaofx(2,0) pushed on stack

   		gaofx(2,1) 	local x initialized to 1 and statements 4 to 1 pushed on stack and
     x1 = 1				x1 = 1 printed by statement 1 and statement 2 true so return 1

	       +gaofx(2,0)	on top of stack with local x initialized to 0 and
     x1 = 0				x1 = 0 printed by statement 1 and statement 2 true so return +1

	       +gaofx(2,1)	on top of stack with local x initialized to 1 and
     x1 = 1				x1 = 1 printed by statement 1 and statement 2 true so return +1

   	       +gaofx(2,2) 	on top of stack with local x initialized to 2 and
     x1 = 2				x1 = 2 printed by statement 1 and statement 2 false and
     x2 = 2				x2 = 2 printed by statement 3 and
					gaofx(2,1) called by statement 4 and +gaofx(2,0) pushed on stack

	        gaofx(2,1)	with local x initialized to 1 and
     x1 = 1				x1 = 1 printed by statement 1 and statement 2 true so return 1 (+1 via 2,2?)

	       +gaofx(2,0)	on top of stack with local x initialized to 0 and
     x1 = 0				x1 = 0 printed by statement 1 and statement 2 true so return +1 and
					Stack Empty!!

	       9 Calls and	Returns 1+1+1+1+1 = 5


This is my initial brute-force code for PE517, but serves our purpose, and it includes both the
Recursive and DP versions, with the DP code currently commented out, and
Statements 1 & 3 re printing x1 & x2 are strictly for the purpose of
tracking the mysterious & elusive... "Stack Map" above --
(exactly as all-that-was-executed in printFun...)

Code: Select all

import java.util.Arrays;			
			
class PE517Proc
{
	double gaofx(double a, double x)
	{
System.out.println("   x1 = " +x);				//statement 1

		if(x < a) return 1;				//statement 2

System.out.println("   x2 = " +x);				//statement 3
System.out.println();

		return gaofx(a, x-1) + gaofx(a, x-a);		//statement 4			
	}
}


class PE517		 		
{
	public static void main(String args [ ])
	{
		double start = System.currentTimeMillis();

		System.out.println();

//------------------------------------------------------------------------------------------------------------------
//		CODE FOR RECURSION:

		PE517Proc g = new PE517Proc();
	
		double ax = 4.0;

System.out.print("G(" +(int)ax+ ") = ");
System.out.println(g.gaofx(Math.sqrt(ax), ax) );
//------------------------------------------------------------------------------------------------------------------
/*
//------------------------------------------------------------------------------------------------------------------
//		CODE FOR DP/TABULATION:

		double a = 2.0;
		double max = 4.0;

		double gaRay[] = new double[(int)(max+1)];

		for(int i = 0; i < (int)a; i++)//     	<--problems if 'a' non-integer sqrt of max
		{
			gaRay[i] = 1;
		}

		for(int x = (int)a; x <= max; x++)//	<--problems if 'a' non-integer sqrt of max
		{
			gaRay[x] += gaRay[x-1] + gaRay[(int)(x-a)];//	<--problems if 'a' non-integer sqrt of max	
		}						   //               like Math.sqrt(90)...	
System.out.println(Arrays.toString(gaRay));
//------------------------------------------------------------------------------------------------------------------
*/
		double finish = System.currentTimeMillis();
System.out.println("RunTime = " + (finish - start)/1000 + " Secs");					
	} 
}
Now it's my turn to say I "think" my Stack Maps for printFun and for PE517 are (albeit Robotically) correct and...
"If somebody else has a better understanding of exactly how this works in terms of "the stack",
and/or corrections, I'd like to hear them
:D" AND given that no one finds those Maps incorrect:
What are the mystery (Robotic) steps in my Stack Map for Fibonacci by Memoization?!
Specifically, how do I map "return (to?/from?) lookup[n]" aka a "cache"?

And my apologies, MHealey, I'm afraid it's woefully late again in LondonTown...
Last edited by kenbrooker on Tue Jan 01, 2019 10:53 pm, edited 2 times in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Mon Dec 31, 2018 2:45 pm

MAYBE it starts out like this --

PRINTED                 	              CALLED
lookup[]			              ******
********                                      Fib(5)	local n initialized to 5 and 
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        Fib(4) called by Statement 2 and
                                                        +Fib(3) pushed on stack by Statement 2

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

                                               Fib(4)	local n initialized to 4 and 
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        Fib(3) called by Statement 2 and
                                                        +Fib(2) pushed on stack by Statement 2

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

                                               Fib(3)	local n initialized to 3 and 
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        Fib(2) called by Statement 2 and
                                                        +Fib(1) pushed on stack by Statement 2

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	
                                               Fib(2)	local n initialized to 2 and 
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        Fib(1) called by Statement 2 and
                                                        +Fib(0) pushed on stack by Statement 2

[-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
	
                                               Fib(1)	local n initialized to 1 and 
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        lookup[1] = 1 by Statement 1 and ???

[-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]

                                              +Fib(0)	on top of stack and
                                                        local n initialized to 0 and
                                                        Statements 3 to 0 pushed on stack &
                                                        Statement 0 true and
                                                        lookup[0] = 0 by Statement 1 and ???

[0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
       ^
       ^
      THIS is where lookup[2] has become 1 and I can't (Robotically) figure out... Why?  :(

Statements repeated here for convenience:

Code: Select all

    if (lookup[n] == NIL)			//statement 0 
    { 
      if (n <= 1) 
          lookup[n] = n;			//statement 1 
      else
          lookup[n] = fib(n-1) + fib(n-2);	//statement 2 
    } 
    return lookup[n];				//statement 3 
Please help...
Last edited by kenbrooker on Tue Jan 01, 2019 10:37 pm, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

MHealy
Posts: 38
Joined: Sat Nov 17, 2012 11:32 pm

Re: Code optimization techniques

Post by MHealy » Mon Dec 31, 2018 5:32 pm

I have been doing a bit of reading since I last replied (eg. on Wikipedia), so hopefully I have a better understanding now. I am still open to corrections!

Fundamentally, as far as I understand it, statements (i.e. lines of code) are not put on the stack in this sense; subroutines (i.e. functions) are. A function is not removed from the stack until it "returns", and any inner functions it calls are put on the stack on top of it and dealt with first. The inner function contains information about exactly where it was called from and, when it has returned, it is removed from the stack and the next function down (i.e. the function which called it) continues from where the inner function was called (now knowing the value returned from said function).


To go into slightly more detail in this case, let's look at the top of the stack from when fib(2) is first called. We have local variable n set to 2, and we move on to the call into fib(1). We then stop executing anything inside fib(2), add the new fib(1) frame to the stack (with a new local n = 1 and so on), and go through fib(1).

This has no recursive calls, so we quickly get to the "return". We pop fib(1) from the stack, and now go back to fib(2) where we left it, knowing the result of fib(1). We then get to "+ fib(0)", so we do the same with fib(0). Once this completes, we pop it, get back to fib(2), and continue from after the call to fib(0) (with n = 0, and having the results of fib(1) and fib(0) to hand locally [in its own stack frame?]).

We then continue in this function - having both values so we can finish this line: setting lookup[2] = fib(1) + fib(0) = 1 + fib(0) = 1 + 1, then finally returning. If you were to add another "print" statement inside the "fib" call, just before the return, you would see a line from inside fib(2) print at the point where lookup[2] is mysteriously populated.

If we now remember that we called fib(2) inside fib(3), we see we are about to call into fib(1). When we call into fib(1), this is the first time we have called into a function since populating lookup[2]. Nothing has printed since we stated fib(0) (a long time ago), but a lot has happened - we went back into fib(2) and populated lookup[2], before returning.

Does that help? :oops:


Now, how this all happens at a processor/machine code level, I have no idea. And maybe that is what your question is really about? How does the computer store which function to go to, where to go to in that function, all the variables it needs and so on? How does it deal with all the statements inside one function, whilst leaving it and working on a completely different function? Hmm... We'll have to ask somebody who programs in assembly... Java is as "low-level" as I go :lol:
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Tue Jan 01, 2019 1:00 am

Happy New Year and
Muchas Gracias :D
MHealy...

I was afraid I might have offended you or discouraged you, but you were commendably reading up on what
I must study next re Stacks... Thanks for the Wiki link (at odds, I see already, with Geeks for Geeks)...

And to answer your kind question -- Yes, your Super Reply HELPS would be an understatement, especially --
"If you were to add another "print" statement inside the "fib" call, just before the return"...

As you have probably noticed I like my pretty Decision Trees and I like tell-tale "print" statements so
not only did I add a "print" just before the "return" but I added "print"s just before Any and
Everything, hopefully nowhere misleadingly, and I want you to see them,
immediately below, ASAP (I haven't "studied" them yet) and
hopefully in corroboration of your esteemed analysis (and
hopefully not boring Everyone Else on
PE.chat to... Death by Details...
IF Any read this far)... :(

I've even included some
MHealy "Depth"!

lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(5) called:
   if(lookup[n] == NIL) true
      if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)


lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(4) called:
   if(lookup[n] == NIL) true
      if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)


lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(3) called:
   if(lookup[n] == NIL) true
      if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)


lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(2) called:
   if(lookup[n] == NIL) true
      if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)


lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called:
   if(lookup[n] == NIL) true
      if(n <= 1) true so lookup[n] gets n
   lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n] called


lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1] <-- Note: No change in lookup[] from 
fib(0) called:                                               before return lookup[n] called...
   if(lookup[n] == NIL) true                                 (which does make sense via
      if(n <= 1) true so lookup[n] gets n                     fib(n) = fib(n-1) + fib(n-2),
   lookup[] = [0, 1, -1, -1, -1, -1, -1, -1, -1, -1]                     the latter NIL...)
   return lookup[n] called
   lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] <-- the... sticky point for me and
   return lookup[n] called                                 What's with these DOUBLE 
                                                            return lookup[n]s?! :shock:
                                   How does the code even get to those two "println"s again 
lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1] without first having to print lookup[] and 
fib(1) called:                                                           "fib(n) called:"?!                                                           
   lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n] called
   lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
   return lookup[n] called


lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
fib(2) called:
   lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
   return lookup[n] called
   lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
   return lookup[n] called


lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
fib(3) called:
   lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
   return lookup[n] called
   lookup[] = [0, 1, 1, 2, 3, 5, -1, -1, -1, -1]
   return lookup[n] called    ^
                              ^
                              ^
               Fibonacci(5) = 5

Just in case the above is misleading,
especially re Stack Calls,
here's the short code,
(wherein I do not see
"return lookup[n];"
TWICE!!) -- :-x

Code: Select all

class GeekFibonacciMemoization		//w/o public... and apparently unnecessary 
{
  int MAX = 10;				//w/o final... and apparently unnecessary 
  int NIL = -1;				//w/o final... and apparently unnecessary 
 
  int lookup[] = new int[MAX]; 

  // Function to initialize NIL values in lookup table 
  void _initialize() 
  { 
    for (int i = 0; i < MAX; i++) 
        lookup[i] = NIL; 
  } 
  
  // Function for nth Fibonacci number 
  int fib(int n) 
  {
System.out.println();
System.out.println();
System.out.println("lookup[] = " +Arrays.toString(lookup));
System.out.println("fib(" +n+ ") called:");
 
    	if (lookup[n] == NIL)					//statement 0 
    	{

System.out.println("   if(lookup[n] == NIL) true");
 
      		if (n <= 1)
	  	{

System.out.println("      if(n <= 1) true so lookup[n] gets n");
 
          		lookup[n] = n;				//statement 1
		}
 
      		else
		{

System.out.println("      if(n <= 1) false so lookup[n] gets/calls fib(n-1) + fib(n-2)");

          		lookup[n] = fib(n-1) + fib(n-2);	//statement 2
		}
	}

System.out.println("   lookup[] = " +Arrays.toString(lookup));
System.out.println("   return lookup[n] called");
  
    	return lookup[n];					//statement 3 
  } 

  public static void main(String[] args)
  {
    GeekFibonacciMemoization f = new GeekFibonacciMemoization();

    System.out.println();
 
    int n = 5; 
    f._initialize();
 
    System.out.println("               Fibonacci(" +n+ ") = " + f.fib(n));
  }  
}
ps - I think I somehow got an "A" once in Assembly Language and I know a year later
I couldn't even remember the Professor's name, much less the... Language, so
that is most thoughtful and humble of you to imagine
I might be thinking "Deeper" but I will be thrilled
just to ever understand "return lookup[n]" and,
I am delighted you are a Java Brother... :D
even at about 1.0 am on Big Ben... :(
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

Re: Code optimization techniques

Post by v6ph1 » Wed Jan 02, 2019 12:48 am

It's only the return section of the previously called functions:
The first calls of fib(5), fib(4), fib(3) and fib(2) did not immediately return - they need to call fib(n-1) and fib(n-2) first.

So read it as follows:
Stack: fib(5)
(A.1) Call fib(5) -> nothing known; call fib(4) and fib(3)
Stack: A
To call: A(fib(4), fib(3))
(B.1) Call fib(4) -> nothing known; call fib(3) and fib(2)
Stack: A, B
To call: B(fib(3), fib(2)), A(fib(3))
(C.1) Call fib(3) -> nothing known; call fib(2) and fib(1)
Stack: A, B, C
To call: C(fib(2), fib(1)), B(fib(2)), A(fib(3))
(D.1) Call fib(2) -> nothing known; call fib(1) and fib(0)
Stack: A, B, C, D
To call: D(fib(1), fib(0)), C(fib(1)), B(fib(2)), A(fib(3))
(E.1) Call fib(1) -> Is clear; add to known values and return 1
Stack: A, B, C, D, E
To call: D(fib(0)), C(fib(1)), B(fib(2)), A(fib(3))
(E.2) Return of E
Stack: A, B, C, D
To call: fib(0), fib(1), fib(2), fib(3)
(F.1) Call fib(0) -> Is clear; add to known values and return 0
Stack: A, B, C, D, F
To call: C(fib(1)), B(fib(2)), A(fib(3))
(F.2) Return of F
Stack: A, B, C, D
To call: C(fib(1)), B(fib(2)), A(fib(3))
(D.2) Now fib(2) is clear, as fib(2) = fib(1) + fib(0) = 1 + 0 = 1; store fib(2)=1 and return 1
Stack: A, B, C
To call: C(fib(1)), B(fib(2)), A(fib(3))
(G.1) Call fib(1) a second time but now the value is known; just return the value 1
Stack: A, B, C, G
To call: B(fib(2)), A(fib(3))
(G.2) return fib(2) = 1
Stack: A, B, C
To call: B(fib(2)), A(fib(3))
(C.2) fib(3) is now clear -> so add the value fib(3) = 2 to the table and then return
Stack: A, B
To call: B(fib(2)), A(fib(3))
(H.1) Call fib(2) again; now the value is known -> so look at the table and return
Stack: A, B, H
To call: A(fib(3))
(H.2) Return the value of fib(2)
Stack: A, B
To call: A(fib(3))
(B.2) Now we can calculate fib(4) = fib(3) + fib(2) = 3, store this value and return
Stack: A
To call: A(fib(3))
(I.1) Call fib(3) again; now the value is known -> look at the table and return
Stack: A, I
To call: (nothing more!)
(I.2) Return the value of fib(3)
Stack: A
To call: (nothing)
(A.2) Now fib(5) knows the values of fib(4) and fib(3) (B and I) and it stores and returns the value 5
Stack: (nothing -> only main)
To call: (nothing)

--> Finished
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Wed Jan 02, 2019 2:36 am

Dear v6ph1...

Sincerest thanks for your conspicuous patience in replying with such clarity, via precision, in
such a necessarily long reply and, no doubt, with 100% accuracy...

I guess I was fooled by my "printFun" and PE517 examples into thinking that,
with sufficient print statements, I could track the Stack (from which
print statements apparently/obviously are not executed); however,
with the complication(?) of a "return lookup[n]" table,
I can see by your multitudinous reply that
I can not even get close...

If you could possibly explain how "return lookup[n];" is not only called but
diagnostically printed out twice, in my (simplistic) output,
I would be forever indebted but,
I don't mean to bore you...

(Maybe you are saying that "return lookup[n]" serves the same purpose as
the simpler "return" statement(s) so common in most other
recursive functions?)

The Bottom Line is
Thanks Again!!
Ken
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

v6ph1
Posts: 113
Joined: Mon Aug 25, 2014 6:14 pm

Re: Code optimization techniques

Post by v6ph1 » Wed Jan 02, 2019 11:28 pm

I just changed your output so for each return, the current n is reported:
-> the return is called twice as it's called by different function calls.
For example fib(2) (the 4th call of fib) is startet, but it is still in progress until the result of fib(0) is returned.
Expand
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(5) called:
   if(lookup[n=5] == NIL) true
      if(n <= 1) false so lookup[n=5] gets/calls fib(n-1) + fib(n-2)
<-- fib(5) still in progress

lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(4) called:
   if(lookup[n=4] == NIL) true
      if(n <= 1) false so lookup[n=4] gets/calls fib(n-1) + fib(n-2)
<-- fib(5) and fib(4) still in progress

lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(3) called:
   if(lookup[n=3] == NIL) true
      if(n <= 1) false so lookup[n=3] gets/calls fib(n-1) + fib(n-2)
<-- fib(5), fib(4) and fib(3) still in progress

lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(2) called:
   if(lookup[n=2] == NIL) true
      if(n <= 1) false so lookup[n=2] gets/calls fib(n-1) + fib(n-2)
<-- fib(5), fib(4), fib(3) and fib(2) still in progress

lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called:
   if(lookup[n=1] == NIL) true
      if(n <= 1) true so lookup[n=1] gets n
   lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n=1] called
<-- only fib(1) finished
<-- fib(5), fib(4), fib(3) and fib(2) still in progress

lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
fib(0) called:
   if(lookup[n=0] == NIL) true
      if(n <= 1) true so lookup[n=0] gets n
   lookup[] = [0, 1, -1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n=0] called<-- fib(0) finished
   lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n=2] called<-- fib(2) finished after it was calculated with fib(1) and fib(0)


lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
fib(1) called:
   lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
   return lookup[n=1] called<-- fib(1) finished as it was already known
   lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
   return lookup[n=3] called<-- fib(3) finished after it was calculated with fib(2) and fib(1)


lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
fib(2) called:
   lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
   return lookup[n=2] called
   lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
   return lookup[n=4] called


lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
fib(3) called:
   lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
   return lookup[n=3] called
   lookup[] = [0, 1, 1, 2, 3, 5, -1, -1, -1, -1]
   return lookup[n=5] called
               Fibonacci(5) = 5
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Thu Jan 03, 2019 2:56 am

Excellent Idea!!
v6ph1...

The evidence was there all along and I changed my code accordingly and
your annotations in red are most clear and helpful...

I'm hoping it's still possible to write code to generate
the exact same lengthy Stack History that
you kindly provided...

So far I'm fairly successful with the following
simple recursive code...

Code: Select all

int mystery(int value)
{
if(value <= 10) return value * 3;
else return value + mystery(mystery(value / 5));
}
I'm pretty confident the Stack History
looks like this --


STACK: (Top to the Right)
*******
m(45)
m(45)1, m(9) returns 27
m(45)1
m(45)2, m(27)
m(45)2, m(27)1, m(5) returns 15
m(45)2, m(27)1,
m(45)2, m(27)2, m(15)
m(45)2, m(27)2, m(15)1, m(3) returns 9
m(45)2, m(27)2, m(15)1
m(45)2, m(27)2, m(15)1, m(9) returns 27
m(45)2, m(27)2, m(15)1
m(45)2, m(27)2, m(15)12 returns 15 + 27 = 42
m(45)2, m(27)12 returns 27 + 42 = 69
m(45)12 returns 45 + 69 = 114

m(value)1 refers to the inner mystery() call;
m(value)2, to the outer call...

and so far my code
generates --


        [STACK] (Top to the Right)
        **************************

   mystery(45) called
    and 45 > 10 calls mystery(mystery(9)) so
     Push mystery(-45) on Stack
      [-45, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   mystery(9) called
    and 9 <= 10 so
     Push mystery(9) on Stack
      [-45, 9, 0, 0, 0, 0, 0, 0, 0, 0]

        and mystery(9) returns 27 so  <--
           Pop mystery(9) off Stack
      [-45, 0, 0, 0, 0, 0, 0, 0, 0, 0]

   mystery(27) called
    and 27 > 10 calls mystery(mystery(5)) so
     Push mystery(-27) on Stack
      [-45, -27, 0, 0, 0, 0, 0, 0, 0, 0]

   mystery(5) called
    and 5 <= 10 so
     Push mystery(5) on Stack
      [-45, -27, 5, 0, 0, 0, 0, 0, 0, 0]

        and mystery(5) returns 15 so  <--
           Pop mystery(5) off Stack
      [-45, -27, 0, 0, 0, 0, 0, 0, 0, 0]

   mystery(15) called
    and 15 > 10 calls mystery(mystery(3)) so
     Push mystery(-15) on Stack
      [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0]

   mystery(3) called
    and 3 <= 10 so
     Push mystery(3) on Stack
      [-45, -27, -15, 3, 0, 0, 0, 0, 0, 0]

        and mystery(3) returns 9 so  <--
           Pop mystery(3) off Stack
      [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0]

   mystery(9) called
    and 9 <= 10 so
     Push mystery(9) on Stack
      [-45, -27, -15, 9, 0, 0, 0, 0, 0, 0]

        and mystery(9) returns 27 so  <--
           Pop mystery(9) off Stack
      [-45, -27, -15, 0, 0, 0, 0, 0, 0, 0]
      .
      .
      .
   mystery(45) = 114

I haven't yet figured out how to "unwind" the mystery(mystery()) calls to
mystery(15), mystery(27) and mystery(45), as indicated by the
negative numbers (and, by the way,
the code does not include
memoization)...

If by any chance I can duplicate that
METICULOUS Stack History that
you provided, I will
let you know...

Thanks Again!!
Ken
Last edited by kenbrooker on Sun Jan 06, 2019 6:16 am, edited 3 times in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Fri Jan 04, 2019 12:44 am

Finally, a BRIEF Post to confirm my progress toward
an automated Stack History --

I'm confident that the
correct Stack History
looks like this --


STACK: (Top to the Right)
*******
m(45)
m(45)1, m(9) returns 27
m(45)1
m(45)2, m(27)
m(45)2, m(27)1, m(5) returns 15
m(45)2, m(27)1,
m(45)2, m(27)2, m(15)
m(45)2, m(27)2, m(15)1, m(3) returns 9
m(45)2, m(27)2, m(15)1
m(45)2, m(27)2, m(15)1, m(9) returns 27
m(45)2, m(27)2, m(15)12 returns 15 + 27 = 42
m(45)2, m(27)12 returns 27 + 42 = 69
m(45)12 returns 45 + 69 = 114

m(value)1 refers to the mystery() call;
m(value)2, to the mystery(mystery()) call...

And my automated output is --

         [STACK] (Top to the Right)
         *******
     m[45, 0, 0, 0]
     m[45, 9, 0, 0] returns 27
     m[45, 0, 0, 0]
     m[45, 27, 0, 0]
     m[45, 27, 5, 0] returns 15
     m[45, 27, 0, 0]
     m[45, 27, 15, 0]
     m[45, 27, 15, 3] returns 9
     m[45, 27, 15, 0]
     m[45, 27, 15, 9] returns 27
     m[45, 27, 15, 0] returns 15 + 27 = 42
     m[45, 27, 0, 0] returns 27 + 42 = 69
     m[45, 0, 0, 0] returns 45 + 69 = 114

     mystery(45) = 114

RunTime = 0.0 Secs
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

User avatar
kenbrooker
Posts: 113
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Sun Jan 06, 2019 1:35 am

PROGRESS REPORT: Reminder -- My final goal is an automated
Stack History for Fibonacci by Memoization but...

For the simplest Fibonacci by Recursion --

Code: Select all

int fib(int n) 
{ 
   if (n <= 1) return n; 
   else return fib(n-1) + fib(n-2); 
}
As a first step toward a Stack History, simply inserting
System.out.println(" fib(" +n+ ") Called"); at the
top of function fib gives --


   fib(5) Called
   fib(4) Called
   fib(3) Called
   fib(2) Called
   fib(1) Called
   fib(0) Called
   fib(1) Called
   fib(2) Called
   fib(1) Called
   fib(0) Called
   fib(3) Called
   fib(2) Called
   fib(1) Called
   fib(0) Called
   fib(1) Called

Yielding this Preorder Recursion Tree for fib(5) (and
illustrating all the repeated computations,
e.g. the entire fib(3) sub-tree twice) --


                         fib(5)
			/      \
		       /         \
                     /             \
               fib(4)                fib(3)
             /      \                /     \
         fib(3)      fib(2)         fib(2)   fib(1)
        /     \        /    \       /    \
  fib(2)   fib(1)  fib(1) fib(0) fib(1) fib(0)
  /    \
fib(1) fib(0)

From which one can ascertain the following
Stack History (with patience?) --



Top of Stack to the Right:
	
        5cld
	5	4cld
	5	4	3cld
	5	4	3	2cld
	5	4	3	2	1cld 		returns fib(1) = 1
	5	4	3	2top
	5	4	3	2		0cld 	returns fib(0) = 0
	5	4	3	2top 		 	returns fib(2) = fib(1)+fib(0) = 1
	5	4	3top
	5	4	3		1cld		returns fib(1) = 1
	5	4	3top			 	returns fib(3) = fib(2)+fib(1) = 2
	5	4top 			
	5	4		2cld
	5	4		2	1cld		returns fib(1) = 1
	5	4		2top
	5	4		2		0cld	returns fib(0) = 0
	5	4		2top			returns fib(2) = fib(1)+fib(0) = 1
	5	4top				  	returns fib(4) = fib(3)+fib(2) = 3
	5top

	5		3cld
	5		3	2cld
	5		3	2	1cld		returns fib(1) = 1
	5		3	2top
	5		3	2		0cld	returns fib(0) = 0
	5		3	2top			returns fib(2) = fib(1)+fib(0) = 1
	5		3		1cld		returns fib(1) = 1
	5		3top				returns fib(3) = fib(2)+fib(1) = 2      
	5top					  	returns fib(5) = fib(4)+fib(3) = 5

	 cld = Called
	 top = Top of Stack; Possibly Called...

And my best code to date replicates the above although
I am still pessimistic about replicating Fibonacci by
Memoization, i.e. including a "lookup" table,
though it should take fewer steps!



Top of Stack to the Right:
   
   fib[5, 0, 0, 0, 0, 0] 5cld
   fib[5, 4, 0, 0, 0, 0] 4cld
   fib[5, 4, 3, 0, 0, 0] 3cld
   fib[5, 4, 3, 2, 0, 0] 2cld
   fib[5, 4, 3, 2, 1, 0] 1cld returns 1
   fib[5, 4, 3, 2, 0, 0] 2top
   fib[5, 4, 3, 2, 0, 0] 0cld returns 0
   fib[5, 4, 3, 2, 0, 0] 2top returns 1
   fib[5, 4, 3, 0, 0, 0] 3top
   fib[5, 4, 3, 0, 1, 0] 1cld returns 1
   fib[5, 4, 3, 0, 0, 0] 3top returns 2
   fib[5, 4, 0, 0, 0, 0] 4top
   fib[5, 4, 0, 2, 0, 0] 2cld
   fib[5, 4, 0, 2, 1, 0] 1cld returns 1
   fib[5, 4, 0, 2, 0, 0] 2top
   fib[5, 4, 0, 2, 0, 0] 0cld returns 0
   fib[5, 4, 0, 2, 0, 0] 2top returns 1
   fib[5, 4, 0, 0, 0, 0] 4top returns 3
   fib[5, 0, 0, 0, 0, 0] 5top

   fib[5, 0, 3, 0, 0, 0] 3cld
   fib[5, 0, 3, 2, 0, 0] 2cld
   fib[5, 0, 3, 2, 1, 0] 1cld returns 1
   fib[5, 0, 3, 2, 0, 0] 2top
   fib[5, 0, 3, 2, 0, 0] 0cld returns 0
   fib[5, 0, 3, 2, 0, 0] 2top returns 1
   fib[5, 0, 3, 0, 1, 0] 1cld returns 1
   fib[5, 0, 3, 0, 0, 0] 3top returns 2
   fib[5, 0, 0, 0, 0, 0] 5top returns 5
   fib[0, 0, 0, 0, 0, 0] 0top

			  cld = Called
			  top = Top of Stack; Possibly Called...

   Fibonacci(5) = 5

RunTime = 0.0 Secs
Last edited by kenbrooker on Fri Jan 11, 2019 4:58 am, edited 1 time in total.
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply