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