Linked Lists/Java/Timing

Timing Linked Lists

This page contains results of timing Java code that performs repeated operations on a custom linked list class, and compares the results to the built-in linked list class. The purposes of doing this are threefold:

• Gain a sense of the big O cost of an operation
• Compare the costs of operations between built-in and custom data structures
• Build a workflow for timing and analyzing code and scalability

Add Function

We start by comparing the custom linked list type to the built-in type for the simplest operation: adding new items to the end. This also tests the speed of randomly adding and removing elements from a list.

Results

Demonstrations of the O(1) behavior of adding, and randomly adding/removing, using a linked list.

Code

About the Linked List Class

The custom Linked List class used here is TLinkedList, implemented following Goodrich et al, Data Structures in Java, Chapter 3 Linked Lists.

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

More details at Linked Lists/Java

Add function timing class

The class doing the timing and outputting a file for the plot software is Timing.java. Here is a link to it in the git repo: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Timing.java

The timing stopwatch class is Tim the Timer: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/Tim.java

Add function timing 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();
	}

The code is implemented as two tests. One is a test that just adds things to a list, and tests that the amortized cost of a dynamically expanding list is O(1).

The second add-remove test successively adds and removes items from a list, in exactly the same sequence, and tests the amount of time it takes.

Add function timing 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