Tag Archives: Code

To Cache or Not to Cache

Caching data can save a computer from doing unnecessary processing work and can be a simple way to speed up your programs. There are two types of caching you could use, in-memory(RAM) and out-of-memory(Physical Storage). Storing data onto a hard drive is generally the way to go if you’re working with larger data. The downsides of storing information within a system’s RAM is that won’t always know how much is available at run-time or how it will affect the system overall. The benefits on the other hand is that it’s a fast and simple way to allocate memory for a program when you need it.

I’m not going into too much detail on how to set up a physical cache, this post was created because I wanted to run some speed tests on a simple Java program I wrote using a mapping data structure. I made two different types of Fibonacci sequence generators. I’ll mention a few other designs considerations if you want to take this a step further but this was quick program I spent about 45 minutes on. I wrote these scripts pretty quickly and didn’t completely iron out a few details I found annoying so bare with me. The first version of a Fibonacci sequence generator I made was a basic recursive version that might look familiar.

package euler;

public class Recursion extends FibonacciSequencer {
	int sequenceRange;
	public Recursion(int sequenceRange) { 
		super(); 
		this.sequenceRange = sequenceRange;
	}

	@Override
	public long findFibonacci(int i) {
		if(i <= 1)
			return 1;
		else
			return(findFibonacci(i-1) + findFibonacci(i-2));
	}
	
	@Override
	public void printSequence() {
		//I'm sorry about this
		for(int i = 0; i < sequenceRange; i++)
			if(i == (sequenceRange -1))
				System.out.print(findFibonacci(i)+".\n");
			else
				System.out.print(findFibonacci(i)+", ");
	}
}

There wasn’t a lot of code I had to write, findFibonacci() will generate the sequence up to a given range. As I mention annoying details, I didn’t store any of the data generated to print out the data. I consider about storing every found Fibonacci number into a map so you could see when that number was generated but that would quickly grow into a large data set that wouldn’t print neatly at the console. Feel free to store or print each generated value if you want to see when a number is generated. You can also break down the logic into a process tree by hand if you’re filling up to it. Word of warning, if you’re not familiar with the Fibonacci sequence, it’s a repeating pattern found in natural and grows exponentially. Also not a reason not to bread rabbits. The next version I made was to take this code to store any new Fibonacci numbers into an map and retrieve them when necessary.

package euler;

import java.util.HashMap;
import java.util.Map;

public class MemCache extends FibonacciSequencer {

	Map<Integer,Long> memCache;

	public MemCache(){
		super();
		memCache = new HashMap<Integer,Long>();
	}
	
	@Override
	public long findFibonacci(int i) {
		//Index of 0 & 1 will have a Fibbonacii number of 1.
		if(i <= 1){
			memCache.put(i,1)
			return 1;
                }
	
		// Returns cached Fibonacii number.
		else if(memCache.containsKey(i))
			return(memCache.get(i));
	
		// Adds new Fibonacii number into the cache and returns the number.
		else{
			memCache.put(i, (findFibonacci(i-1) + findFibonacci(i-2)) );
			return(memCache.get(i));
		}
	}
	
	@Override
	public void printSequence() {
		for(int i = 0; i <= memCache.size(); i++){
			System.out.print( memCache.get(i)) ; 
			
			if(i == memCache.size() )
				System.out.print(".\n");
			else
				System.out.print(", ");
		}
	}
}

If you hadn’t notice I used an abstract class called FibonacciSequencer to build these two Java classes. The objects Recursion() and MemCache() only contain the Fibonacci algorithm but they both use the testing code within the FibonacciSequencer() object. There are some unused code here but I only executed the function, trials() outside this object. My trials() method takes two arguments, one for how many trials to run and the second is the range of the Fibonacci sequence. I was pretty lazy so I print out how well the sequence generated did I made throw the output from the trials() function into the printTrials(). The next part after this class if my test harness if you want to see how I used these two functions.

public abstract class FibonacciSequencer {		
	public FibonacciSequencer(){}
	public abstract long findFibonacci(int i);
	public abstract void printSequence();

//---Some inefficient code ;(
	protected boolean isLength(int len, long fib){
		if(len >= 0 && len == findDigitLength(fib) )
			return true;
		else
			return false;		
	}
	
	protected boolean isWithinRange(long i, long x, long y){
		if(i >= x && i <= y)
			return true;
		else
			return false;
	}
	
	protected int findDigitLength(long fib) {
		int count = 0;
		
		while(fib > 0){
			count++;
			fib /= 10;
		}
		
		return count;
	}

//-----Time Trials Code
	
	public long[] trials(int numTrials, int sequenceRange){
		long[] trials = new long[numTrials];
		
		for(int i = 0; i < numTrials; i++)
			trials[i] = timeIt(System.nanoTime(), findFibonacci(sequenceRange));
		
		return(trials);
	}
	
	protected long timeIt( long time, long fib ){
		return(System.nanoTime() - time);
	}
	
	public void printTrials(long[] trials){
		long avg = 0;
		
		for(long trial : trials)
			avg += trial;
		
		avg /= trials.length;
		
		System.out.println(trials.length+" trials where exicuted.");
		System.out.println("Average time of completion was, " + nanoToMicroseconds(avg) + " microseconds.");
		System.out.println("Time of completion as nanoseconds, " + avg + ".");
		System.out.println("Time of completion as milliseconds, " + nanoToMilliseconds(avg) + ".");
	}
	
	protected long nanoToMicroseconds(long nano){
		return((nano/1000));
	}
	
	protected double nanoToMilliseconds(long nano){
		return(nano*(Math.pow(10, -6)));
	}
}

How much better was the program with the hash map?


Well, averaging the results from ten trials and finding up to the sixth index of a Fibonacci sequence generated these results.

Memory Cache Test

10 trials where executed.
Average time of completion was, 87 microseconds.
Time of completion as nanoseconds, 87637.
Time of completion as milliseconds, 0.08763699999999999.
1, 1, 2, 3, 5, 8.

Recursion Test

10 trials where executed.
Average time of completion was, 4 microseconds.
Time of completion as nanoseconds, 4274.
Time of completion as milliseconds, 0.004274.
1, 1, 2, 3, 5, 8.

Ok, the recursion function won out because I used a small Fibonacci sequence. There was some small overhead in the hash map version that slowed down program but lets try running a slightly larger sequence. The next tests found a sequence of fifty values. Let’s see how long it takes only for the hash map.

Memory Cache Test

10 trials where executed.
Average time of completion was, 92 microseconds.
Time of completion as nanoseconds, 92246.
Time of completion as milliseconds, 0.092246.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025.

It only took about 92 microseconds the reach this point not too bad. Lets see if the recursion method fare any better.

Recursion Test

10 trials where executed.
Average time of completion was, 95281927 microseconds.
Time of completion as nanoseconds, 95281927647.
Time of completion as milliseconds, 95281.92764699999.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049,

Minus that little bug at the end of the sequence the program average around 95,281 milliseconds to complete, not microseconds. As you can see the recursion method breaks down quickly once you start increasing the scale. This is pretty much end of how far I took this simple script but here are few ideas you could try implementing to improve the performance.

Store the data into a file, simple and highly efficient. This way you’re not dependent on the scale of the Fibonacci sequence and you can still incorporate in-memory caching to tackle the problem in manageable blocks. You also should use some kind of compression on the file to keep it manageable, if you don’t want to code you’re own compression algorithm you can using an existing algorithm like gZip to do the heavy lifting. Also try working with binary files rather than text string files.

Here is my test harness if you want to try running my scripts. I have some time this weekend to work on another quick and simple programming exercise. Right now I’m leaning towards writing a Monty Carlo program in Python, but it would feel a little weird doing it in any other language besides lisp. Side note, why can’t languages support an non-crippled lambda expression. ;(

Advertisements

Introduction to Sorting Algorithms

I’ve just starting watching lectures of the Introduction to Algorithms class hosted on Harvard’s OpenCourseWare.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/

The class is taught by Erik Demaine, Ronald Rivest, and Srinivas Devadas.  Ronald was also one of the co-authors the book Introduction to Algorithms, a good book worth checking out.

I figure good place to start would be to write up a few sorting algorithms I’m already familiar with and see if I optimize them while going through the lectures.  Here are is my non-optimized Java code.

To make my life a little easier, I made an abstract class called Algorithm to hide some ugly code and make sure my sorting algorithm class just have a sort() method.

*Note: I’ve did this in a VM and I don’t have a flash drive with me at the moment. I just rewrote these objects but they may contain some typos. Later I copy and paste them here along with a few others I made.

package algorithms;

public abstract class Algorithm(){
    public int[] arr;
    public int count = 0;

    public Algorithm(int[] arr){
        this.arr = arr;
        long start = System.nanoTime();

        printTestingWelcomeMessage();
        printArrType();
        print();
        printTestingLineSepartor();

        long nanoTime = (System.nanoTime() - start);

        // There is a loss of precision when converting to microseconds but,
        // it's hard to cry over the loss of a faction of a mircosecond.
        System.out.println("Time: "
            + (nanoTime / 1000) + " microseconds || "
            + nanoTime + " nanoseconds || "
            + (nanoTime * (Math.pow(10,-6)) + " milliseconds"
        );

        System.out.println("Moves: " ( (count != 0) ? count : "?") );
    }
    protected abstract void sort();
    protected abstract void printTestingWelcomeMessage();

    public int[] get(){ return(arr); }

    public void swap(int x, int y){
        int temp = arr[x];
        arr[x] = arr[y]
        arr[y] = temp;
        count++;
    }

    public void print(){
        System.out.println("[");
        for(int i = 0; i < arr.length; i++)
            if(i <= arr.length)
                System.out.print(arr[i]+ ", ");
            else if( i == (arr.length -1) )
                System.out.println(arr[i]+"]\n");
    
    private void printArrType(){
        if(arr.length > 1)
            System.out.println( (arr[0] - arr[1] == 1) ? ("Inverse Sequence Matrix") : ("Random Values Matrix") );
        else
            System.err.println("Single Value Matrix");
    }

    private void printTestingLineSepartor(){
        System.out.println("________________________");
    }
}

Now that’s out of the way lets get to the fun part. I wrote most of these algorithms with help from WikiBook’s Sorting Algorithm page. If you want any more additional information about these algorithms, check out Wikipedia, cool things can be found there.

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting

First up, the classic and extremely inefficient, bubble sort algorithm.

package algorithms;

public BubbleSort extends Algorithm{

    public BubbleSort(int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Bubble Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        int i = 0;

       while( i < (arr.length - 1))             if( arr[i] > arr[i+1]){
                swap(i,i+1);
                i=0;
            }
            else
                i++

    }
}

I’ve found another way to code a heap sort in java so I’ve made a class for each version. The first up is using priority queue and I really like this version for the lite coding and speed.

package algorithms;

public PriorityQueHeapSort extends Algorithm{

    public PriorityQueHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Priority Queue Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
         PriorityQueue heap = new PriorityQueue(arr.length);

        for(int elem : arr)
            heap.add(elem);

        for(int i; i < arr.length; i++)
            arr[i] = heap.remove();
    }
}

Sadly, this version is a tad bit too slow for my tastes so I’ve made another heap sort using the in-place method. You are about too see why I liked the priority queue version. I didn’t bother cleaning up the source code much. The code one big iteration loop with nested if statements that work off the branches.

package algorithms;

public InPlaceHeapSort extends Algorithm{

    public InPlaceHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting In-Place Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        for(int i = 0; i < arr.length; i++){             while( i > 0 ){
                int p = (i-1)/2;

                if(arr[i] > arr[p])
                    swap(i,p);
                else
                    break;
            }
        }

        for(int i= arr.length; i > 0;){
            swap(0,--i);

            int n = 0;

            while(true){
                int left = (n*2) + 1;

                if(left >= i)
                    break;

                int right = left+1;

                if(right >=i){
                    if(arr[left] > arr[n])
                        swap(left,n);
                    break;
                }

                if(arr[left] > arr[n])
                    if(arr[left] > arr[right]){
                        swap(left,n);
                        n = left;
                        continue;
                    }
                    else{
                        swap(right, n);
                        n = right;
                        continue;
                    }
                else
                    if(arr[right] > arr[n]){
                        swap(right, n);
                        n = right;
                        continue;
                    }
                    else
                        break;
            }
        }
    }
}

Next algorithm up is quick sort. Like the namesake it’s a pretty quick sorting algorithm. Other sorting algorithms that are faster exists but this one gets the most attention.

public QuickSort extends Algorithm{

    public QuickSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Quick Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        divideAndConquer(0, (arr.length -1));
    }

    private void divideAndConquer(int low, int high){
        int x = low;
        int y = high;
        int pivot = arr[low+ (high-low)/2];

        while(x < y){
            while(arr[x] < pivot)                 x++;             while(arr[y] > pivot)
                y++;

            if( x                 swap(x,y)
                x++;
                y--;
            }
        }

        if(low < y)
            divideAndConquer(low, y);

        else if(x < high)
            divideAndConquer(x, high);
    }
}

For completion sake I included my test harness. I used two different types of matrices. One matrix I used was an array arrange with a inverse sequence, the bubble sort’s worst nightmare.

[5,4,3,2,1]

Along with an array filled with random integers.

public class Run{
    int[] arrInverse;
    int[] arrRandom;
    Random rand;

    public Run(int MAX){
        rand = new Random();
        arrInverse = new int[MAX];
        arrRandom = new int[MAX];

        for(int i = 0; i < arrInverse.length; i++)
            arrInverse[i] = (arrInverse.length - i);

        for(int i = 0; i < arrRandom.length; i++)
            arrRandom[i] = (arrRandom.length - i);
    }
   // I've omitted my other methods but they are all set up the same.
   public void testBubbleSort(){
       new BubbleSort(arrInverse);
       new BuubleSort(arrRandom);
   }

   public void testQuickSort(){
       new QuickSort(arrInverse);
       new QuickSort(arrRandom);
   }
}

Text Compression in Java

I’ve made this compression program in Java after watching this lecture from Harvard’s OpenCourseWare class, Information and Entropy. My code is still incomplete but it appears to be working as it should. I also took out some of my code and only included the example to compress a single string. I chose to solve this problem with iteration rather than recursion. As it is now it’s kinda of a mess of nested while loops. Later I’m going to try to encapsulate that code into an iterator and add some extra logic to build the dictionary faster.
 
Here is the video of the lecture, you can also visit the class site for more infomation:
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-050j-information-and-entropy-spring-2008/
[youtube:https://www.youtube.com/watch?feature=player_detailpage&v=mM9m9uDlHno%5D
 

import java.util.ArrayList;
import java.util.Hashtable;

public class Compress {
	public Hashtable<Object, Integer> dict; // Encryption Dictionary
	public int code; 			// Compression Code

	public Compress(){
		dict = new Hashtable<Object, Integer>();

		dict.put( true, 256 );  // Beginning of the message
		dict.put( false, 257 ); // End of the message
		code = 257;		// New codes should start at 258
	}

	// Compresses a single string.
	public ArrayList<Integer> scan(String line){
		ArrayList<Integer> msg = new ArrayList<Integer>();		
                int i = 0; // Index pointer

		msg.add( dict.get( true ) ); // Can also be a hard coded as 256.
		
		// Traverse the string
		while( i < line.length() ){
			int r = ( i + 1 ); // Range pointer of the slice

			// Peeks next characters after the index.
			while( r <= line.length() ){
//-------------------------------------------------------------------------
// Case 1: New dictionary keys with the length of 2.
//-------------------------------------------------------------------------
//  - Conditions: The range pointer must be less than the line length. 
//    + ( r < line.length() ) 
//  - Conditions: The range pointer must be set one index ahead.
//    + ( (r - i) == 1 )
//  - Conditions: The dictionary must not contain a string of the index and following character. 
//    + !dict.containsKey( line.substring(i, ( r + 1) ) )
//-------------------------------------------------------------------------
				if( r < line.length() && (r - i) == 1 && !dict.containsKey( line.substring(i, ( r + 1) ) ) ){
					dict.put( line.substring(i, (r + 1) ), ++code );
					msg.add( (int) line.charAt(i) );
					i = r;
					break;
				}
//-------------------------------------------------------------------------
// Case 2: New dictionary keys with the length of greater than 2.
//-------------------------------------------------------------------------
//  - Conditions: The range pointer must be less than the line length. 
//    + ( r < line.length() ) 
//  - Conditions: The range pointer must be at least two positions ahead of the index.
//    + ( (r - i) > 1 )
//  - Conditions: The dictionary must not contain the slice of the string.
//    + !dict.containsKey( line.substring(i, ( r + 1) ) )
//-------------------------------------------------------------------------
				else if( r < line.length() && (r - i) > 1 && !dict.containsKey( line.substring(i, (r + 1) ) ) ){
					dict.put( line.substring(i, (r + 1) ), ++code );
					msg.add( dict.get( line.substring( i, (r - 1) ) ) );
					i = r;
					break;
				}
//-------------------------------------------------------------------------
// Case 3: End of string, last known sequence. 
//-------------------------------------------------------------------------
//  - Conditions: The range pointer must be set as the line length. 
//    + ( r == line.length() ) 
//  - Conditions: The slice of the string must contain more than a single character.
//    + ( (r - i) > 1 )
//  - Conditions: The dictionary must contain the slice of the string.
//    + dict.containsKey( line.substring(i, r)
//-------------------------------------------------------------------------
				else if( r == line.length() && ( r - i ) > 1 && dict.containsKey( line.substring(i, r) ) ){
					msg.add( dict.get( line.substring(i, r) ) );
					i = r;
					break;
				}

//-------------------------------------------------------------------------
// Case 4: End of string, unknown prior sequence.
//-------------------------------------------------------------------------
//  - Conditions: The range pointer must be set as the line length. 
//    + ( r == line.length() ) 
//  - Conditions: The index must be set at the last available character.
//    + ( (r - i) == 1 )
//-------------------------------------------------------------------------
				else if( r == line.length() && ( r - i ) == 1 ){
					msg.add( (int) line.charAt(i) );
					i = r;
					break;
				}
				// Alternative: Advances the range
				else
					r++;
			} // !while( r <= line.length() )
		} // !while( i < ( line.length() - 1 ) )

		msg.add( dict.get( false ) ); // Can also be a hard coded as 257.
		return( msg );
	} // !scan()

//-------------------------------------------------------------------------
// Debuggers
//-------------------------------------------------------------------------
	// Prints contents of dictionary
	public void debugDict(){
		for(Object key : dict.keySet() ){
			if( dict.get(key) > 257 )
				System.out.println(dict.get(key) +" : " + key);
		}
	}

	// Prints ArrayList<Integer>
	public void debugMsg( ArrayList<Integer> msg ){
		for( int i : msg ){
			
			// Single chars
			if( i <= 255 )
				System.out.println( i +" -> "+ (char) i);
			
			// Sliced strings
			else {
				for(Object key : dict.keySet() ){
					if( i == dict.get(key) && i > 255 ){
						System.out.println( i + " -> " + key );
						break;
					}
				}
			}
		}
	}
}

Reworked Sierpinski Triangle JavaScript

I’m just about done reworking the recursive function to plot the mid points of a triangle and create nested triangles within it. I still have to tweak it a bit because I want the middle triangle to be the color of the canvas. Not entirely sure how to do that yet but I’ll update this post when I figure it out.

Also this was a pretty good read:
http://sixrevisions.com/html/canvas-element/
Continue reading

Drawing Lines Onto HTML5 Canvas

There are a few things I want to quickly fix on my Sierpinski triangle JavaScript. I reworked how I drew the triangle onto the canvas this morning and I like how it turned out. Next I’m going to attempt to dynamically plot an equilateral triangle onto the canvas.

var canvas = document.getElementById('canvas');
var context = canvas.getContext('2d');
						
/* 
    draw()
     - Draws a triangle from three given points.
     - Is able to a set fill color.
     - Is able to a set line color.
     - Is able to a set line width. 
*/
function draw( pointA, pointB, pointC, fillStyle, strokeStyle, lineWidth ){

	// Setting start point
	context.moveTo( pointA.x, pointA.y );

	// Connecting the points
	context.lineTo( pointB.x, pointB.y );
	context.lineTo( pointC.x, pointC.y );
	context.lineTo( pointA.x, pointA.y );
							
	// Line style variables may be false 
	if( fillStyle != false ){
		context.fillStyle = fillStyle;
		context.fill();
	}

	if( strokeStyle != false )
		context.strokeStyle = strokeStyle;

	if( lineWidth != false )
		context.lineWidth = lineWidth;

	// Draws the line
	context.stroke();
}

draw( {x: 20, y: 20}, {x:20, y:60}, {x:60, y:20}, false, false, false );

HTML DOM Events

I spent around 10 minutes adding some extra mouse events to my particle simulation JavaScript this morning.

Continue reading

Simple Particle Animation in JavaScript

I’ve been hitting a few walls trying to learn how to do some simple sprite animation but here is simple JavaScript animation that was pretty fun to work with to see how you can code with the canvas.

This animation randomly drops a circle onto the canvas and was originally created by Josh Marinacci.

http://projects.joshy.org/presentations/HTML/CanvasDeepDive/presentation.html

Also check out his blog, he has some interesting stuff on there.

http://joshondesign.com/

Continue reading