One of the caching techniques we have is precomputation, which performs an initial computation in order to create a lookup table. This lookup table is used to avoid repetitive computation when a particular process is executed. Now we are going to create code to compare the difference in the process with and without precomputation. Let's take a look at the following code, which we can find in the Precomputation.csproj project:

public partial class Program 
{ 
  private static void WithoutPrecomputation() 
  { 
    Console.WriteLine("WithoutPrecomputation()"); 
    Console.Write( 
      "Choose number from 0 to 99 twice "); 
    Console.WriteLine( 
      "to find the power of two result: "); 
    Console.Write("First Number: "); 
    int iInput1 = Convert.ToInt32(Console.ReadLine()); 
    Console.Write("Second Number: "); 
    int iInput2 = Convert.ToInt32(Console.ReadLine()); 
    int iOutput1 = (int) Math.Pow(iInput1, 2); 
    int iOutput2 = (int)Math.Pow(iInput2, 2); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput1, 
      iOutput1); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput2, 
      iOutput2); 
  } 
} 

The preceding simple WithoutPrecomputation() function will calculate the square of the two numbers that we input from 0 to 99. Suppose we want to calculate the number 19 and 85; we will get the following output on the console window:

As you can see, the function has done its job well. It asks for two input numbers from the user with the following code snippet:

Console.Write("First Number: "); 
int iInput1 =Convert.ToInt32(Console.ReadLine()); 
Console.Write("Second Number: "); 
int iInput2 = Convert.ToInt32(Console.ReadLine()); 

It uses the Math.Pow() method in the System namespace in order to get to the power of n, as shown in the following code snippet:

int iOutput1 = (int) Math.Pow(iInput1, 2); 
int iOutput2 = (int)Math.Pow(iInput2, 2); 

We can refactor the WithoutPrecomputation() function to use precomputation techniques so that it doesn't need any repetition calculation every time the user asks to calculate the power of the same numbers by two. The function we are going to have will be as follows:

public partial class Program 
{ 
  private static void WithPrecomputation() 
  { 
    int[]powerOfTwos = new int[100]; 
    for (int i = 0; i < 100; i++) 
    { 
      powerOfTwos[i] = (int)Math.Pow(i, 2); 
    } 
    Console.WriteLine("WithPrecomputation()"); 
    Console.Write( 
      "Choose number from 0 to 99 twice "); 
    Console.WriteLine( 
      "to find the power of two result: "); 
    Console.Write("First Number: "); 
    int iInput1 = Convert.ToInt32(Console.ReadLine()); 
    Console.Write("Second Number: "); 
    int iInput2 = Convert.ToInt32(Console.ReadLine()); 
    int iOutput1 = FindThePowerOfTwo(powerOfTwos, iInput1); 
    int iOutput2 = FindThePowerOfTwo(powerOfTwos, iInput2); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput1, 
      iOutput1); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput2, 
      iOutput2); 
  } 
} 

As you can see in the preceding code, we create a lookup table named powerOfTwos in the beginning of the function, as shown in the following code snippet:

int[] powerOfTwos = new int[100]; 
for (int i = 0; i < 100; i++) 
{ 
  powerOfTwos[i] = (int)Math.Pow(i, 2); 
} 

Since we ask the user to input a number from 0 to 99, the lookup table will store the database of the power of two numbers from the range numbers. Moreover, the difference between the WithPrecomputation() function and the WithoutPrecomputation() function is that we have the collection of the power of two result. Now we use the FindThePowerOfTwo() function, as shown in the following code snippet:

int iOutput1 = FindThePowerOfTwo(squares, iInput1); 
int iOutput2 = FindThePowerOfTwo(squares, iInput2); 

The FindThePowerOfTwo() function will look for the selected number in the lookup table, which in this case is powerOfTwos. And the implementation of the FindThePowerOfTwo() function will be as follows:

public partial class Program 
{ 
  private static int FindThePowerOfTwo ( 
    int[] precomputeData, 
    int baseNumber) 
  { 
    return precomputeData[baseNumber]; 
  } 
} 

As you can see, the FindThePowerOfTwo() function returns the value of the lookup table, whose index we specify with the baseNumber parameter. We will get the following output on the console if we run the WithPrecomputation() function:

Again, we calculate the square of 19 and 85 and, indeed, we have the exact same result as what we get when we run the WithoutPrecomputation() function. Now, we have a lookup table of squared numbers from 0 to 99. The advantages in our program are more effective since every time we ask to calculate the same number (19 and 85), it will not need to run the calculation but will look for the result in the lookup table.

However, the precomputation code we explored earlier is not a functional approach since, each time the FindThePowerOfTwo() function is called, it will iterate the squares again. We can refactor it so that it will be functional using the power of currying, a technique to change structure arguments by sequence, which we discussed in Chapter 1, Tasting Functional Style in C#. Now let's take a look at the following code:

public partial class Program 
{ 
  private static void WithPrecomputationFunctional() 
  { 
    int[]powerOfTwos = new int[100]; 
    for (int i = 0; i < 100; i++) 
    { 
      powerOfTwos[i] = (int) Math.Pow(i, 2); 
    } 
    Console.WriteLine("WithPrecomputationFunctional()"); 
    Console.Write( 
      "Choose number from 0 to 99 twice "); 
    Console.WriteLine( 
      "to find the power of two result: "); 
    Console.Write("First Number: "); 
    int iInput1 = Convert.ToInt32(Console.ReadLine()); 
    Console.Write("Second Number: "); 
    int iInput2 = Convert.ToInt32(Console.ReadLine()); 
    var curried = CurriedPowerOfTwo(powerOfTwos); 
    int iOutput1 = curried(iInput1); 
    int iOutput2 = curried(iInput2); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput1, 
      iOutput1); 
    Console.WriteLine( 
      "2 the power of {0} is {1}", 
      iInput2, 
      iOutput2); 
  } 
} 

If we compare the preceding WithPrecomputationFunctional() function with the WithPrecomputation() function, we can see that it uses the CurriedPowerOfTwo() function now, as shown in the following code snippet:

var curried = CurriedSquare(squares); 
int iOutput1 = curried(iInput1); 
int iOutput2 = curried(iInput2); 

Using the CurriedPowerOfTwo() function, we split the function argument so that the curried variable can now handle the lookup table and we can call the WithPrecomputationFunctional() function as many times as we want with no need to iterate the lookup table again. The CurriedPowerOfTwo() function implementation can be found in the following code:

public partial class Program 
{ 
  public static Func<int, int> 
  CurriedPowerOfTwo(int[] intArray) 
      => i => intArray[i]; 
} 

If we run the WithPrecomputationFunctional() function, the following output will be displayed in our console window:

Again, we have the exact same output compared to our previous functions: the WithoutPrecomputation() function and the WithPrecomputation() function. We have successfully refactored the function and the functional approach has been fulfilled in this precomputation technique.

Besides performing precomputation techniques to optimize the code, we can also use memoization techniques to make our code more optimal. Memoization is the process of remembering the result of the function with a specific input. Each time we execute a particular function with a specific input argument, the code will remember the result. So, each time we call the function with the exact same input argument again, the code doesn't need to run the code; instead. it will get it from the place it stores the result in.

Let's borrow the repetitive GetFactorial() function we discussed in Chapter 5, Querying Any Collection Easily with LINQ and then refactor it in order to use the memoization technique. As we know, the implementation of the GetFactorial() function is as follows:

public partial class Program 
{ 
  private static int GetFactorial(int intNumber) 
  { 
    if (intNumber == 0) 
    { 
      return 1; 
    } 
    return intNumber * GetFactorial(intNumber - 1); 
  } 
} 

To make the GetFactorial() function use memoization, we have to save the result every time the GetFactorial() function returns a value. The refactoring code of the preceding GetFactorial() function will be as follows and we can find it in the Memoization.csproj project:

public partial class Program 
{ 
  private static Dictionary<int, int> 
    memoizeDict = new Dictionary<int, int>(); 
  private static int GetFactorialMemoization(int intNumber) 
  { 
    if (intNumber == 0) 
    { 
      return 1; 
    } 
    if (memoizeDict.ContainsKey(intNumber)) 
    { 
      return memoizeDict[intNumber]; 
    } 
    int i = intNumber * GetFactorialMemoization( 
      intNumber - 1); 
    memoizeDict.Add(intNumber, i); 
    return i; 
  } 
} 

As you can see, we have a Dictionary class named memoizeDict to store all the results when the particular arguments have been passed to the GetFactorialMemoization() function. The definition of this dictionary is like what is shown in the following code snippet:

private static Dictionary<int, int> 
  memoizeDict = new Dictionary<int, int>(); 

Another difference when we compare the GetFactorialMemoization() function to the GetFactorial() function is that it now saves the result when the GetFactorialMemoization() function is run with the particular arguments that have been called so far. The following code snippet shows the code for this algorithm:

private static int GetFactorialMemoization(int intNumber) 
{ 
  if (intNumber == 0) 
  { 
    return 1; 
  } 
  if (memoizeDict.ContainsKey(intNumber)) 
  { 
    return memoizeDict[intNumber]; 
  } 
  int i = intNumber * GetFactorialMemoization( 
    intNumber - 1); 
  memoizeDict.Add(intNumber, i); 
  return i; 
} 

First, we check whether the particular argument has been passed to the function. If so, it doesn't need to run the function; instead, it just retrieves the result from the dictionary. If the parameter arguments haven't been passed yet, the function is run and we save the result in the dictionary. Using memoization, we can optimize the code since we don't need to run the function over and over again if the arguments are exactly the same. Suppose we pass 10 to the GetFactorialMemoization() function. If we run the function again and pass 10 again, the processing speed time will increase since it doesn't need to run the repetitive GetFactorialMemoization() function. Fortunately, by passing 10 to the function parameter, it will also run the function with the 1-9 argument since it's a recursive function. The effect and the result of the invocation of these 10 items will be saved in the directory and calling the function using these arguments will be much faster.

Now let's compare the performance of the GetFactorial() function with the GetFactorialMemoization() function. We will pass 9216 as an argument and run them it times. The following is the RunFactorial() function used to call the GetFactorial() function:

public partial class Program 
{ 
  private static void RunFactorial() 
  { 
    Stopwatch sw = new Stopwatch(); 
    int factorialResult = 0; 
    Console.WriteLine( 
      "RunFactorial() function is called"); 
    Console.WriteLine( 
      "Get factorial of 9216"); 
    for (int i = 1; i <= 5; i++) 
    { 
      sw.Restart(); 
      factorialResult = GetFactorial(9216); 
      sw.Stop(); 
      Console.WriteLine( 
        "Time elapsed ({0}): {1,8} ns", 
        i, 
        sw.ElapsedTicks * 
          1000000000 / 
          Stopwatch.Frequency); 
    } 
  } 
} 

If we run the RunFactorial() function, we will get the following output on the console:

As you can see from the output, we need 281461 ns in the first invocation of the GetFactorial() function and about 75,000- 98,000 nanoseconds in the remaining invocations. The process speed is almost the same for all invocations since the recursive GetFactorial() function is invoked everytime. Now let's move on to the following RunFactorialMemoization() function in order to call the GetFactorialMemoization() function:

public partial class Program 
{ 
  private static void RunFactorialMemoization() 
  { 
    Stopwatch sw = new Stopwatch(); 
    int factorialResult = 0; 
    Console.WriteLine( 
      "RunFactorialMemoization() function is called"); 
    Console.WriteLine( 
      "Get factorial of 9216"); 
    for (int i = 1; i <= 5; i++) 
    { 
      sw.Restart(); 
      factorialResult = GetFactorialMemoization(9216); 
      sw.Stop(); 
      Console.WriteLine( 
        "Time elapsed ({0}): {1,8} ns", 
        i, 
        sw.ElapsedTicks * 
          1000000000 / 
          Stopwatch.Frequency); 
    } 
  } 
} 

If we run the RunFactorialMemoization() function, we will get the following output on the console:

Now we can see that, by using memoization, the process speed has increased to a great extent. Even though it needs the extra time in the first invocation of GetFactorialMemoization(), in the invocation 3 to 5, the process becomes faster.