Code optimization techniques

Announcements, comments, ideas, feedback, and "How do I... ?" questions
User avatar
kenbrooker
Posts: 102
Joined: Mon Feb 19, 2018 3:05 am
Location: Oregon, USA

Re: Code optimization techniques

Post by kenbrooker » Thu Jan 10, 2019 6:45 am

Final Report on my goal of an automated Stack History for Fibonacci by Memoization,
the complication for me being Memoization's use of a "lookup" table or cache, and
I wish to first thank MHealy and v6ph1 without whose generous insight
I'd still be struggling late into the night(s)...


Outputting only the incoming lookup[] table rows for/and
the calls of fib(n) generates the following and
suggests the Recursion "Tree" on the right:

								    Recursion "Tree"
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]		    ***************		    
								   
fib(5) called with above lookup[]:					(first call downward v) v 5
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with above lookup[]:							v 4
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with above lookup[]:						v 3 (last call upward ^)
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with above lookup[]:					v 2 ^ 
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]		       
								    
fib(1) called with above lookup[]:				v 1 ^
lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]	       
							   
fib(0) called with above lookup[]:			  0 ^
lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with above lookup[]:
lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]

fib(2) called with above lookup[]:
lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
			   (v)
fib(3) called with above lookup[]:
			   (v)
             Fibonacci(5) = 5

Which looks (humorously) straight-forward enough, however,
outputting more lookup[] table states proves
the Stack History not so obvious:


Expand
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(5) called with lookup[] above
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(4) called with lookup[] above
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(3) called with lookup[] above
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(2) called with lookup[] above
lookup[] = [-1, -1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with lookup[] above
lookup[1] == NIL and n < 2 so lookup[1] = 1 gives [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
return lookup[1] called with [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]
lookup[] = [-1, 1, -1, -1, -1, -1, -1, -1, -1, -1]

fib(0) called with lookup[] above
lookup[0] == NIL and n < 2 so lookup[0] = 0 gives [0, 1, -1, -1, -1, -1, -1, -1, -1, -1]
return lookup[0] called with [0, 1, -1, -1, -1, -1, -1, -1, -1, -1]
lookup[2] == NIL and n > 1 so lookup[2] = fib(1) + fib(0)
return lookup[2] called with [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
lookup[] = [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]

fib(1) called with lookup[] above
return lookup[1] called with [0, 1, 1, -1, -1, -1, -1, -1, -1, -1]
lookup[3] == NIL and n > 1 so lookup[3] = fib(2) + fib(1)
return lookup[3] called with [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
lookup[] = [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]

fib(2) called with lookup[] above
return lookup[2] called with [0, 1, 1, 2, -1, -1, -1, -1, -1, -1]
lookup[4] == NIL and n > 1 so lookup[4] = fib(3) + fib(2)
return lookup[4] called with [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
lookup[] = [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]

fib(3) called with lookup[] above
return lookup[3] called with [0, 1, 1, 2, 3, -1, -1, -1, -1, -1]
lookup[5] == NIL and n > 1 so lookup[5] = fib(4) + fib(3)
return lookup[5] called with [0, 1, 1, 2, 3, 5, -1, -1, -1, -1]
					     ^
                                             ^
                              Fibonacci(5) = 5

Fortunately for me v6ph1 kindly provided the following
(stark) Stack History, with still more annotations than
I am showing (and indeed with fewer steps than
I found for the simplest Fibonacci by Recursion:
17 vs 31 steps for fib(5)):


	   fib: 5
	   fib: 5  	4
	   fib: 5  	4  	3
	   fib: 5  	4  	3  	2
	   fib: 5  	4  	3  	2  	1  		<-- lookup[1] set to 1
	   fib: 5  	4  	3  	2
	   fib: 5  	4  	3  	2  		0	<-- lookup[0] set to 0
     	   fib: 5  	4  	3  	2  			<-- lookup[2] set to 1 via fib(1)+fib(0)
	   fib: 5  	4  	3
	   fib: 5  	4  	3  		1*		<-- lookup[1] = 1*
	   fib: 5  	4  	3  				<-- lookup[3] set to 2 via fib(2)+fib(1)
	   fib: 5  	4
	   fib: 5  	4  		2*			<-- lookup[2] = 1*
	   fib: 5  	4  					<-- lookup[4] set to 3 via fib(3)+fib(2) 
	   fib: 5
	   fib: 5  		3*				<-- lookup[3] = 2*
	   fib: 5  						<-- lookup[5] set to 5 via fib(4)+fib(3) and 
								     returned as Fibonacci(5) = 5
				 * = lookup[n] already in lookup[]

Using only the easily listed sequential calls to the fib function:
int fibCall[] = {5, 4, 3, 2, 1, 0, 1, 2, 3}; (and
not using the also easily output lookup table)
my code (last, below) replicates the above:


   fib: [5, 0, 0, 0, 0, 0]
   fib: [5, 4, 0, 0, 0, 0]
   fib: [5, 4, 3, 0, 0, 0]
   fib: [5, 4, 3, 2, 0, 0]
   fib: [5, 4, 3, 2, 1, 0] <-- lookup[1] set to 1
   fib: [5, 4, 3, 2, 0, 0]
   fib: [5, 4, 3, 2, 0, 0] <-- lookup[0] set to 0
   fib: [5, 4, 3, 2, 0, 0] <-- lookup[2] set to 1 via fib(1)+fib(0)
   fib: [5, 4, 3, 0, 0, 0]
   fib: [5, 4, 3, 0, 1, 0] <-- lookup[1] = 1*
   fib: [5, 4, 3, 0, 0, 0] <-- lookup[3] set to 2 via fib(2)+fib(1)
   fib: [5, 4, 0, 0, 0, 0]
   fib: [5, 4, 0, 2, 0, 0] <-- lookup[2] = 1*
   fib: [5, 4, 0, 0, 0, 0] <-- lookup[4] set to 3 via fib(3)+fib(2)
   fib: [5, 0, 0, 0, 0, 0]
   fib: [5, 0, 3, 0, 0, 0] <-- lookup[3] = 2*
   fib: [5, 0, 0, 0, 0, 0] <-- lookup[5] set to 5 via fib(4)+fib(3)
                                and returned as Fibonacci(5) = 5

					    * = lookup[n] already in lookup[]
RunTime = 0.0 Secs

BOTTOM LINE: I understand Stacks better now but computing the nth Fibonacci term by
Memoization hardly shows the advantage of Memoization... In this case,
following the progression of the lookup[] cache, Memoization is a...
Hell of a way to mimic Fibonacci-by-Iteration, which
computes Fibonacci(5) in 4 steps, and has
none of the cripplings of recursion...

Code: Select all

import java.util.Arrays;			

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

	System.out.println();

	int n = 5;
	int size = n+1;
	int fibpntr = 0;
	int rowpntr = 0;
	int colpntr = 5;
	int stkpntr = 0;
	int setbak1 = -1;
	int setbak2 = -2;

	int Stack[] = new int[size];

	int fibCall[] = {5, 4, 3, 2, 1, 0, 1, 2, 3};
		       //0  1  2  3  4  5  6  7  8

	int lookup[][] = new int[20][size];
//---------------------------------------------------------------------------------------------------------

	for(int i = 0; i < lookup.length; i++)
	{
		for(int j = 0; j < size; j++)
		{
			lookup[i][j] = -1;
		}
	}
//---------------------------------------------------------------------------------------------------------

	for(int i = 0; i < size; i++)
	{
		if(lookup[i][i] == -1 && fibCall[i] > 1)
		{
			Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack));

			fibpntr += 1;;
			stkpntr += 1;
			rowpntr += 1;
			colpntr = fibCall[fibpntr];
		}	
	}
//---------------------------------------------------------------------------------------------------------

	while(lookup[rowpntr][n] == -1)	
	{   
		if(lookup[rowpntr][fibCall[fibpntr]] != -1)
		{
			Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +fibCall[fibpntr]+ "] = " +
								lookup[rowpntr][fibCall[fibpntr]]+ "*"); 

			lookup[rowpntr+1] = lookup[rowpntr];

			setbak1 = setbak2;
			setbak2 = fibpntr;

			Stack[stkpntr] = 0;
			fibpntr -= 2;				//Alway after "*" case...
			colpntr = fibCall[fibpntr];
			rowpntr += 1;
			stkpntr = fibpntr;
		}
//---------------------------------------------------------------------------------------------------------

		if(fibCall[fibpntr] <= 1 && lookup[rowpntr][colpntr] == -1)
		{
			Stack[stkpntr] = fibCall[fibpntr];

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +Stack[stkpntr]+ "] set to " +
											Stack[stkpntr]);

			lookup[rowpntr][colpntr] = fibCall[fibpntr];

			setbak1 = setbak2;
			setbak2 = fibpntr;

			Stack[stkpntr] = 0;
			if(fibCall[fibpntr] == 1) fibpntr -= 1;	//Note...
			if(fibCall[fibpntr] == 0) fibpntr -= 2;	//Note...
			colpntr = fibCall[fibpntr];
			stkpntr = fibpntr;
		}
//---------------------------------------------------------------------------------------------------------

		else
		{
			if(fibCall[fibpntr] > 1 && !(fibpntr+1 == setbak1 && fibpntr+2 == setbak2))
			{		

System.out.println("   fib: " +Arrays.toString(Stack));

				lookup[rowpntr+1] = lookup[rowpntr];

				fibpntr += 2;			//Always after "No comment" case...
				stkpntr = fibpntr;
				colpntr = fibCall[fibpntr];
				rowpntr += 1;
			}
//---------------------------------------------------------------------------------------------------------
						       
			else
			{

				if(fibCall[fibpntr] > 1 && (fibpntr+1 == setbak1 && fibpntr+2 == setbak2))
				{
					int first = lookup[rowpntr][colpntr-1];
					int secnd = lookup[rowpntr][colpntr-2];
					int sum = first + secnd; 

					lookup[rowpntr][colpntr] = sum;

					setbak1 = setbak2;
					setbak2 = fibpntr;  

System.out.println("   fib: " +Arrays.toString(Stack)+ " <-- lookup[" +fibCall[fibpntr]+ "] set to " +sum+
								 " via fib(" +(fibCall[fibpntr]-1)+
								     ")+fib(" +(fibCall[fibpntr]-2)+ ")"); 

					lookup[rowpntr+1] = lookup[rowpntr];

					Stack[stkpntr] = 0;
					if(fibpntr > 0)		//for Final Fibonacci fibpntr = 0...
					fibpntr -= 1;		//Always after "set to" case...
					stkpntr = fibpntr;
					colpntr = fibCall[fibpntr];
					rowpntr += 1;
					lookup[rowpntr] = lookup[rowpntr-1];
				}
			}
		}
	}
	
System.out.println("                                and returned as Fibonacci(" +n+ ") = " +
										lookup[rowpntr][n]);
System.out.println();
System.out.println("                                            * = lookup[n] already in lookup[]");										
System.out.println();				

	double finish = System.currentTimeMillis();

System.out.println("RunTime = " + (finish - start)/1000 + " Secs");					
} 
}
"Good Judgment comes from Experience;
Experience comes from Bad Judgment
..."
Image

Post Reply