public class ListComparisons
1: import java.util.ArrayList;
2: import java.util.LinkedList;
3: import java.util.List;
4: import java.util.Random;
5: import java.util.Scanner;
6: import java.util.function.Consumer;
7: import java.io.OutputStream;
8: import java.io.PrintStream;
10: /**
11: *
12: * @author Mark Young (A00000000)
13: */
14: public class ListComparisons {
16: private static final String HEADER = "%10s %15s %15s%n";
17: private static final String RESULT = "%,10d %,15d %,15d%n";
18: private static final int MIN_N = 10;
19: private static final int MAX_N = 100000;
20: private static final int MULT = 10;
21: private static final Scanner KBD = new Scanner(System.in);
23: public static void main(String[] args) {
24: // introduce yourself
25: printIntroduction();
26:
27: // warm up the engine
28: PrintStream oldOut = System.out;
29: try {
30: System.out.println("\n...warming up the engine...");
31: System.setOut(new PrintStream(OutputStream.nullOutputStream()));
32: testBuildAndTearDown();
33: testRandomAccess();
34: System.setOut(oldOut);
35: } catch (Exception ex) {
36: System.err.println("Something went terribly wrong!");
37: System.err.println(ex);
38: System.exit(1);
39: }
40: pause();
42: // get timing data
43: long start = System.nanoTime();
44: testBuildAndTearDown();
45: testRandomAccess();
46: long end = System.nanoTime();
47: long total = end - start;
48: double seconds = total / 1000000000.0;
49:
50: // report total duration
51: System.out.printf("Elapsed time: %.1f seconds.%n",
52: seconds);
53: }
54:
55: private static void printIntroduction() {
56: System.out.println("\n"
57: + "This program compares the time it takes for ArrayLists "
58: + "and LinkedLists\nto do the equivalent things.\n\n"
59: + "All times in nano-seconds.\n\n"
60: + "Original program: Mark Young (A00000000)");
61: }
63: /**
64: * Compare ArrayLists and LinkedLists for how long it takes to add multiple
65: * elements and then remove them one by one from the front.
66: */
67: private static void testBuildAndTearDown() {
68: System.out.println("\nTime to build up and then empty a list.\n");
70: // create the tests
71: Consumer<Integer> testArrayList
72: = t -> buildAndTearDown(t, new ArrayList<>());
73: Consumer<Integer> testLinkedList
74: = t -> buildAndTearDown(t, new LinkedList<>());
76: // run the tests
77: compareTimes(testArrayList, testLinkedList);
78: System.out.println();
79: }
81: /**
82: * Compare ArrayLists and LinkedLists for how long it takes to select
83: * elements at random from them.
84: */
85: private static void testRandomAccess() {
86: System.out.println("\nTime to build up and then randomly access "
87: + "elements of a list.\n");
89: // create the tests
90: Consumer<Integer> testArrayList
91: = t -> randomAccess(t, new Random(0), new ArrayList<>());
92: Consumer<Integer> testLinkedList
93: = t -> randomAccess(t, new Random(0), new LinkedList<>());
95: // run the tests
96: compareTimes(testArrayList, testLinkedList);
97: System.out.println();
98: }
99:
100: /**
101: * Compare the times taken by an ArrayList vs a LinkedList to accomplish
102: * some task. The two Consumer arguments should be doing essentially the
103: * same thing so that the time comparisons are meaningful.
104: *
105: * @param testArrayList the version of the task using an ArrayList
106: * @param testLinkedList the version of the task using a LinkedList
107: */
108: private static void compareTimes(
109: Consumer<Integer> testArrayList,
110: Consumer<Integer> testLinkedList) {
111: // warm up the tests (first use takes extra time)
112: testArrayList.accept(10);
113: testLinkedList.accept(10);
115: // run the tests
116: System.out.printf(HEADER,
117: "N", "ArrayList(N)", "LinkedList(N)");
118: System.out.printf(HEADER,
119: "----------", "------------", "-------------");
120: for (int n = MIN_N; n <= MAX_N; n *= MULT) {
121: long arrayTime = time(n, testArrayList);
122: long linkTime = time(n, testLinkedList);
123: System.out.printf(RESULT, n, arrayTime, linkTime);
124: }
125: }
126:
127: /**
128: * Time how long it takes to run the consumer method with the given
129: * argument.
130: *
131: * @param n the number to give to the consumer method
132: * @param method a method that takes one integer argument
133: * @return the amount of time it takes to complete the task, to nearest 100
134: * nanoseconds
135: */
136: private static long time(int n, Consumer<Integer> method) {
137: long start = System.nanoTime();
138: method.accept(n);
139: return System.nanoTime() - start;
140: }
142: /**
143: * Add <code>numElts</code> elements to the given list, then remove those
144: * elements one at a time from the front until the list is empty.
145: *
146: * @param numElts the number of elements to add/remove
147: * @param list the list to add/remove the elements to/from
148: */
149: private static void buildAndTearDown(int numElts, List<String> list) {
150: for (int i = 0; i < numElts; ++i) {
151: list.add("A");
152: }
153: while (!list.isEmpty()) {
154: list.remove(0);
155: }
156: }
157:
158: /**
159: * Test how long it takes to build up a list of the given length and then
160: * add up half its elements, chosen at random.
161: *
162: * @param numElts the number of elements to add to the list
163: * @param list the list to add the elements to
164: */
165: private static void randomAccess(
166: int numElts, Random rand, List<Double> list) {
167: // create random elements
168: for (int i = 0; i < numElts; ++i) {
169: list.add(rand.nextDouble());
170: }
171:
172: // choose several elements at random
173: for (int i = 0; i < numElts / 2; ++i) {
174: list.get(rand.nextInt(numElts));
175: }
176: }
178: /**
179: * Prompt the user and wait for them to press the enter key.
180: */
181: private static void pause() {
182: System.out.print("\n...press enter...");
183: KBD.nextLine();
184: System.out.println();
185: }
186: }