Tutorial: Palendrome Algorithm Runtime Comparison

HelloWorld · #1 (**permalink**) 07-24-2007, 09:36 PM

In this tutorial, we will be creating a program that reads from a file named input.txt that contains the following:

Code:

10 11 12 13 14 14 13 12 11 10
10 11 12 13 12 11 10
10 11 12 10 11 12

We want to determine whether this is a PALENDROME or not with different type of Data Structures Algorithm and see the actual running time for each algorithm

Sounds fun?

You may also want to refer to the previous tutorial that I made for Tutorial: How to read from ASCII files

Hopefully the code is self explanatory, and as usual, you will take your own risk by using my code

However, if you do have any questions regarding this program, feel free to throw me some questions

Data Structures Used in this Program:
1. Stack/Queue
2. Vector
3. Array
4. Doubly Linked List

PHP Code:

  import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.Vector;

import sun.misc.Queue;

public class Palendrome {
    
    public Palendrome(String filename) {
        
        double stack_t1, stack_t2, stack_r;
        double vector_t1, vector_t2, vector_r;
        double array_t1, array_t2, array_r;
        double ll_t1, ll_t2, ll_r;
        
        try {
            BufferedReader br = new BufferedReader(new FileReader(filename));
            String line = br.readLine();
            Stack s = new Stack();
            Queue q = new Queue();
            Vector v = new Vector();
            String[] array = new String[99];
            LinkedList ll = new LinkedList();
            
            System.out.println("Result\tStack/Queue\tVector\tArray\tDoubly LL");
            System.out.println("------\t-----------\t------\t-----\t---------");
            
            while (line != null) {
                String result = null;
                if (line.length() == 0) {
                    // ignores blank line
                } else {
                    s = new Stack();
                    q = new Queue();
                    v = new Vector();
                    array = new String[99];
                    ll = new LinkedList();
                    
                    StringTokenizer st = new StringTokenizer(line.trim(), " ");
                    int cnt = 0;
                    int length = 0;
                    while (st.hasMoreTokens()) {
                        String num = st.nextToken();
                        s.push(num);
                        q.enqueue(num);
                        v.add(num);
                        array[cnt] = num;
                        ll.add(num);
                        cnt++;
                        length++;
                    }
                    // STACK/QUEUE
                    stack_t1 = System.nanoTime();
                    for (int i = 0; i < length; i++) {
                        if (!s.pop().equals(q.dequeue())) {
                            result = "FALSE";
                        } else {
                            result = "TRUE";
                        }
                    }
                    stack_t2 = System.nanoTime();
                    stack_r = stack_t2 - stack_t1;
                    // VECTOR
                    vector_t1 = System.nanoTime();
                    for (int i = 0; i < length; i++) {
                        if (!v.get(i).equals(v.get(v.size()-(i+1)))) {
                            result = "FALSE";
                        } else {
                            result = "TRUE";
                        }
                    }
                    vector_t2 = System.nanoTime();
                    vector_r = vector_t2 - vector_t1;
                    // ARRAY
                    array_t1 = System.nanoTime();
                    for (int i = 0; i < cnt; i++) {
                        if (!array[i].equals(array[cnt-(i+1)])) {
                            result = "FALSE";
                        } else {
                            result = "TRUE";
                        }
                    }
                    array_t2 = System.nanoTime();
                    array_r = array_t2 - array_t1;
                    // DOUBLY LINKED LIST
                    ll_t1 = System.nanoTime();
                    for (int i = 0; i < length; i++) {
                        if (!ll.get(i).equals(ll.get(ll.size()-(i+1)))) {
                            result = "FALSE";
                        } else {
                            result = "TRUE";
                        }
                    }
                    ll_t2 = System.nanoTime();
                    ll_r = ll_t2 - ll_t1;
                    System.out.println(result + "\t" + stack_r + "\t\t" + vector_r + "\t" + array_r + "\t" + ll_r);
                }
                line = br.readLine();
            }
        } catch (FileNotFoundException fnfe) {
            System.out.println("FileNotFoundException: " + fnfe.getMessage());
        } catch (IOException ioe) {
            System.out.println("IOException: " + ioe.getMessage());
        } catch (InterruptedException ie) {
            System.out.println("InterruptedException: " + ie.getMessage());
        }
    }
    
    public static void main(String[] args) {
        if (args.length != 1) {
            System.out.println("USAGE: java Palendrome [filename]");
        } else {
            new Palendrome(args[0]);
        }
    }
}

RESULT

Code:

Result    Stack/Queue    Vector    Array    Doubly LL
------    -----------    ------    -----    ---------
TRUE    37938.0        12117.0    5977.0    16898.0
TRUE    13526.0        5929.0    2171.0    7748.0
FALSE    14921.0        5396.0    2344.0    6596.0

Pretty neat program eh? TRUE means that it is a "PALENDROME"

The numbers are the time it takes to determine whether it's a palendrome or not for each Data Structures