Memoization in Simple Terms

w7r.blogspot.com

Memoization in real talk

Memoization is a strategy for solving a problem which requires repeated work in some manner. Instead of actually repeating the same work, we memorize it (by we I mean the running program). The program writes memos (reminders) to itself, and then before trying to perform work, it checks to see if there is a memo for the particular problem. The time spent looking at the memos is relatively small when using a special data structure known as the HashTable, but in many cases a flat array, or list of values suffices. If the memo-lookup doesn't exist for a set of parameters, then you will calculate the solution for that set of parameters and then store the result in the hashtable or list for any future calls with that same parameter set.

Why use memoization?

It can turn a recursive function from exponential runtime to something much simpler such as NlogN runtime. Big Oh of k O(k). It is important to remember that the decision of structure for holding "cached" (previously stored) results will effect the program runtime dramatically.

The Hidden Cost

The hidden cost of memoization is the space required to store all of the memos in their data structure. When space is scarce, memoization would not be a good solution.

Who Knew Random Took So Much Thought

If I asked you to give me a random number within 1 to 100 from the top of your head what would you pick?
Would your pick be completely random? If you kept asking yourself for random numbers between 1 to 100 chances are you will repeat numbers several times before even reaching your 50th "random" number. If our brain is not able to respond randomly, do you think randomness exists in nature at all? 


Surprisingly, true randomness is arbitrary (made up) just as much as numbers are themselves. Randomness is a way of describing something that is "completely" unpredictable. Sadly, nothing can be completely unpredictable, or perfectly just, because in nature we experience patterns, sometimes clear ones like the stems of plants and other times obscure ones like the orientation of the mushrooms relative to one another after a light rainfall. The patterns that govern our world are infinitely big, so there is no saying that any human will live to see the completion of some patterns that exist as a function of time.

Why would I or you, a tech enthusiast, a student, or a professional care about the randomness in nature? It is because successful programs, algorithms, and other functions that simulate the real world need to be able to be as close as possible to our theoretical values that have been proven time and time again. Probability for one, is extremely important to the fields of computer science, math, and engineering (of course there are many more fields too) because the products of technology solve problems based on theoretical representation of real life variables.

So, the reason I have been indulging in the thought of randomness is mainly because I have been programming my own version on Tetris in Java code and have realized the inaccuracy in the random function of the Math class. Basically, programming languages cannot generate random numbers without following some pattern or algorithm which means that they are slightly predictable and unusual. By unusual I mean that I may have five blue tetrominos (one of seven of the tetris pieces) in a row, "randomly." The chances of that occuring are (1/7)^(5) * 100 %. I did the math for you: 0.0001214265% chance of that occurring. As a stern programming I wanted to fix this ASAP, well lets say ASAP did not come as soon as I wanted. Turns out the "Math.random()" command generates a psuedo-random number which has poor acurracy as far as random goes. Math.random() would be sufficient for many programs, but in tetris if the pieces are being distributed unevenly, then each game will be more or less fair depending on how the beginning value the psuedo-random algorithm uses.

I wanted to have a little experiment or two, so I did. Here is my code for checking how the random values have been. And don't worry, I'll do my best to explain each step in lines of comments (comments follow double forward slashes //). And the class this was used in I called GameStats. GameStats has a

public static void printPieceStats() {
        int total = pieces[0]+pieces[1]+pieces[2]+pieces[3]+pieces[4]+pieces[5]+pieces[6];

        System.out.println("\nL_PIECE (blue): "+pieces[0]+"   |  Percent: "+((pieces[0])/(double)total)*100+"%");
        System.out.println("J_PIECE (orange): "+pieces[1]+"   |  Percent: "+((pieces[1])/(double)total)*100+"%");
        System.out.println("I_PIECE (teal): "+ pieces[2]+"   |  Percent: "+((pieces[2])/(double)total)*100+"%");
        System.out.println("Z_PIECE (red): "+ pieces[3]+"   |  Percent: "+((pieces[3])/(double)total)*100+"%");
        System.out.println("S_PIECE (green): "+pieces[4]+"   |  Percent: "+((pieces[4])/(double)total)*100+"%");
        System.out.println("O_PIECE (yellow): "+ pieces[5]+"   |  Percent: "+((pieces[5])/(double)total)*100+"%");
        System.out.println("T_PIECE (purple): "+pieces[6]+"   |  Percent: "+((pieces[6])/(double)total)*100+"%");

        System.out.println(total);
        //ideally each piece would be dropped 1/7 of the time.
        double ideal = 1.0/7.0*10.0;

        double[] dubs = new double[7];
        int place=0;
        for(int num: pieces) {
            dubs[ place ]= (num/(double)total)*10.0;
            place++;
        }

        //find their percent error.
        //store the percent error
        //use absolute value to stabilize signs.
        //average all of the percent errors together
        double [] percentErrors = new double[7];
        place=0;
        double errorTotal=0;

        for(double d: dubs) {
            double dub = Math.abs((d-ideal)/(ideal)*100);
            percentErrors[place]=dub;
            errorTotal+=dub;
            place++;
        }

        //errorTotal is the sum of % error of each piece which is divided by 7 to yield the average percent error.
        System.out.println(errorTotal/7);
    }

I use the value that is printed out to determine how close my program is to being completely random. I coded this method and you are free to copy and paste the code. The same method could be adapted for all kinds of applications, just follow its steps that are commented in the code.