Linked Lists/Java/Timing

This page describes a script that measures the performance of a custom Linked List type, and compares its performance to the built-in LinkedList type.

The custom Linked List type is one implemented following Goodrich et al, Data Structures in Java, Chapter 3 Linked Lists.

Link: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists/TLinkedList.java

More details at Linked Lists/Java

Code

The following code uses the TLinkedList class and the LinkedList class from the Java Collections API, so have those both ready and/or imported.

import java.util.LinkedList;
import java.util.Random;

/** Timing class: measure big-O complexity and runtime of data structures.
 *
 * Compare algorithms, test structures, and verify expected big-O behavior.
 *
 * This program is intended to be run on the command line like so:
 *
 * java Timing > output.txt
 *
 */
public class Timing {

	// Tests
	public static void main(String[] args) {
		linked_list_add_test();
		linked_list_add_remove_test();
	}





	/** Compare the add and remove method - adding and removing from list.
	 *
	 *  NOTE: If this is not constant, then add is not O(1) amortized,
	 *  and there is something wrong with your implementation.
	 *  */
	public static void linked_list_add_remove_test() {
		StringBuffer sb = new StringBuffer();

		sb.append("N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k Mine (us) \n");

		int ntrials = 1000;
		Random r;

		// Loop over values of N
		for(int N = 1024; N <= 5e5; N*=2) {

			sb.append( String.format("%d, ",N) );


			// builtin linked list:
			//
			// b prefix is for built-in datatype
			Tim btim = new Tim();

			// Trials counter is always
			// K for Kafka
			r = new Random(100);
			for(int k = 0; k<ntrials; k++) {
				LinkedList<Integer> blist = new LinkedList<Integer>();
        		for(int i=0; i<N; i++) {
					// 75% of the time, we add something. 25% of the time, we remove something.
					boolean addSomething = r.nextBoolean();
					if(addSomething) {
						blist.add(0,r.nextInt(100));
					} else {
						if(!blist.isEmpty()) {
							blist.remove(0);
						}
					}
				}
			}
			double btime_total = btim.elapsedms();


			// my little linked list:
			//
			// m prefix is for mine
			Tim mtim = new Tim();

			// Trials counter is k
			r = new Random(100);
			for(int k=0; k<ntrials; k++) {
				TLinkedList<Integer> mylist = new TLinkedList<Integer>();
        		for(int i=0; i<N; i++) {
					// 75% of the time, we add something. 25% of the time, we remove something.
					boolean addSomething = r.nextBoolean();
					if(addSomething) {
						mylist.addFirst(r.nextInt(100));
					} else {
						if(!mylist.isEmpty()) {
							mylist.removeFirst();
						}
					}
				}
			}
			double mtime_total = mtim.elapsedms();

			// print amortized cost per 1000 operations, times 1000 ms -> us
			sb.append( String.format("%.3f, ", btime_total/N*1000) );
			sb.append( String.format("%.3f ",  mtime_total/N*1000) );

			sb.append("\n");

		}

		System.out.println(sb.toString());

	}


	/** Compare the add method - appending to the rear of a list.
	 *
	 *  Compares builtin LinkedList type with self-authored TLinkedList class.
	 *
	 *  NOTE: If this is not constant, then add is not O(1) amortized,
	 *  and there is something wrong with your implementation.
	 *  */
	public static void linked_list_add_test() {

		StringBuffer sb = new StringBuffer();

		sb.append("N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k Mine (us) \n");

		int ntrials = 1000;

		// Loop over some values of N,
		// print the total cost,
		// print the cost per add operation
		for(int N = 1024; N < 5e5; N *= 2) {

			sb.append( String.format("%d, ", N) );


			// builtin linked list:
			//
			// b prefix is for built-in datatype
			Tim btim = new Tim();

			// Trials counter is always
			// K for Kafka
			for(int k = 0; k<ntrials; k++) {
				LinkedList<Integer> blist = new LinkedList<Integer>();
        		for(int i=0; i<N; i++) {
					blist.add(i*i);
				}
			}
			double btime_total = btim.elapsedms();

			// my little linked list:
			//
			// m prefix is for mine
			Tim mtim = new Tim();

			// Trials counter is k
			for(int k=0; k<ntrials; k++) {
				TLinkedList<Integer> mylist = new TLinkedList<Integer>();
        		for(int i=0; i<N; i++) {
					mylist.addLast(i*i);
				}
			}
			double mtime_total = mtim.elapsedms();

			// print cost per 1000 add operations us, times 100 ms -> us
			sb.append( String.format("%.3f, ",  btime_total/N*1000) );
			sb.append( String.format("%.3f", mtime_total/N*1000) );
			sb.append("\n");

		}

		System.out.println(sb.toString());
	}

}

Output

N, Add Amortized Walltime Per 1k Builtin (us), Add Amortized Walltime Per 1k Mine (us)
1024, 31.250, 18.555
2048, 15.137, 20.508
4096, 17.822, 8.301
8192, 17.944, 8.301
16384, 14.099, 12.085
32768, 10.742, 7.965
65536, 10.300, 7.248
131072, 10.597, 7.721
262144, 11.223, 9.842

N, Add Remove Amortized Walltime Per 1k Builtin (us), Add Remove Amortized Walltime Per 1k Mine (us)
1024, 53.711, 41.992
2048, 39.551, 19.043
4096, 23.438, 24.658
8192, 22.949, 18.677
16384, 22.949, 19.165
32768, 22.675, 20.172
65536, 23.087, 20.065
131072, 23.651, 19.623
262144, 23.518, 19.264