Tag Archives: Java

Clojure and Spring

I did some googling on using Spring with Clojure.

These links were good reads but both written in 2009.
Writing Spring MVC Controllers In Clojure
Practical Clojure With SWT Junit And Spring

Java Networking Goodness

I just gave myself a mini refresher course on networking with Java, anyway here are some links I found pretty useful.

Clojure

Sockets

Datagrams

Network Interfaces

Exchanging files

Cookies

Keytool Information

TimSort Source Code in Java

This was an pretty interesting read, TimSort.java
TimSort is a stable form of merge-sort algorithm invented by Tim Peters.  Tim orginal wrote the sorting algorithm for the python language and was ported into the Java language by Josh Bloch.

How To Design A Good API and Why it Matters – Joshua Bloch

Enjoy
[youtube:http://www.youtube.com/watch?v=aAb7hSCtvGw&feature=player_detailpage%5D

Creating Secure Passwords in Java

I found this gem on reddit a few days ago and spent 5 minutes playing around with the code.

Secure Password Storage Lots of Dont’s, a Few Dos, and a Concrete Java SE Example
By: Jeremiah Orr
http://java.dzone.com/articles/secure-password-storage-lots

Using Jeremiah’s code sample I only needed two lines to generate an encrypted password. One is for generating a salt and the other for generating an encrypted password. Pretty light weight but extremely useful. In this case the symbol encryption is a reference to the PasswordEncryptionService object. It could be rewritten as PasswordEncryptionServerice.generateSalt() but I’m lazy and don’t want to type all of that out each time.

byte[] salt = encryption.generateSalt();
byte[] encryptedPassword = encryption.getEncryptedPassword(password, salt);

Calling generateSalt will generate a random 8 byte value. The code makes use of the random number generator, SecureRandom, to create a unique salt.

http://docs.oracle.com/javase/6/docs/api/java/security/SecureRandom.html

With a unique salt we can generate a secure byte array from a given password. There is another method in Jeremiah’s sample worth taking a look at, authenticate(). The method authenticate takes in a potential match for a password along with the encrypted password with it’s salt to check if the validity of the potential password. The method generates a new encrypted password using the potential password and salt to compare to with the encrypted password. Only storing the salt and encrypted password we can remove the need for storing password in clear text or don’t and take Sony’s approach to user security.

Here is my full test harness.

import java.security.NoSuchAlgorithmException;
import java.security.spec.InvalidKeySpecException;

public class Tester {
    private PasswordEncryptionService encryption = new PasswordEncryptionService();

    public Tester(String password){
        try {
            System.out.println("Password: " + password);

            byte[] salt = encryption.generateSalt();
            System.out.println("Salt: " + salt);

            byte[] encryptedPassword = encryption.getEncryptedPassword(password, salt);
            System.out.println("Encrypted Password: " + encryptedPassword + "\n" );

            System.out.println("Does it pass authentication?\n" + encryption.authenticate(password, encryptedPassword, salt) + "\n" );
            
            System.out.println("Sanity authentication check\n" + encryption.authenticate("Rawr", encryptedPassword, salt) );

        } catch (NoSuchAlgorithmException e) {
            e.printStackTrace();
        } catch (InvalidKeySpecException e) {
            e.printStackTrace();
        }		
    }	
}

Along with my main.

public class Run {
    public static void main(String[] args){
        Tester test = new Tester("password");
    }
}

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. ;(

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);
   }
}