root/trunk/ComplexityTest.java

// ComplexityTest - copyright Tom Felker, <tfelker2@uiuc.edu>, December 2004
//
// this is a rough test of the time it takes to perform certain operations
// on TreeMaps.  It was not used in the report.

import java.io.*;
import java.util.*;

class ComplexityTest {
        public static void main(String argv[]) {
                TreeSet t = new TreeSet();

                if(argv.length < 4) {
                        System.out.println("Usage - java ComplexityTest min max step trials");
                        return;
                }

                int min = Integer.parseInt(argv[0]);
                int max = Integer.parseInt(argv[1]);
                int step = Integer.parseInt(argv[2]);
                int trials = Integer.parseInt(argv[3]);

                // values are in nanoseconds (milliseconds / 1000000)
                float [][]performance = new float[(max-min)/step+1][4];

                for(int n = min, i = 0; n <= max && i < performance.length; n += step, ++i) {

                        performance[i][0]=n;

                        for(int trial = 0; trial < trials; ++trial) {

                                System.out.println("Trial " + trial + " of " + trials);
                                System.out.println("Inserting " + n + " random values.");
                                Random random = new Random();
                                System.gc();
                                long time = System.currentTimeMillis();
                                for(int j = 0; j < n; ++j) t.add(new Integer(random.nextInt()));
                                time = System.currentTimeMillis() - time;
                                performance[i][1] += (double)time / (double)n * 1.0e6;
                                System.out.println("Total time: " + time + " ms" );
                                System.out.println("Average time: " + performance[i][1] + " ns");

                                System.out.println("Finding the lowest value... (pinky to lips) ONE MILLION TIMES");
                                Integer lowest = null;
                                System.gc();
                                time = System.currentTimeMillis();
                                for(int j = 0; j < 1000000; ++j) lowest = (Integer)t.first();
                                time = System.currentTimeMillis() - time;
                                performance[i][2] += time;
                                System.out.println("That took " + time + " ns per operation");

                                System.out.println("Removing the lowest value, then adding a random one, 1e6 times");
                                System.gc();
                                time = System.currentTimeMillis();
                                for(int j = 0; j < 1000000; ++j) {
                                        lowest = (Integer)t.first();
                                        t.remove(lowest);
                                        t.add(new Integer(random.nextInt()));
                                }
                                time = System.currentTimeMillis() - time;
                                performance[i][3] += time;
                                System.out.println("That took " + time + " ns per operation");
                        }
                        for(int j = 1; j <= 3; ++j)
                                performance[i][j] /= trials;
                }
                System.out.println("N\tInsert\tLowest\tRemoveLowest");
                for(int i = 0; i < performance.length; ++i) {
                        System.out.println(
                                (int)performance[i][0] + "\t" +
                                (int)performance[i][1] + "\t" +
                                performance[i][2] + "\t" +
                                performance[i][3]);
                }

        }
}