public class RemovalComparisons
2: import java.util.ArrayList;
3: import java.util.Iterator;
4: import java.util.LinkedList;
5: import java.util.List;
6: import java.util.Random;
7: import java.util.Scanner;
8: import java.util.function.Consumer;
9: import java.io.OutputStream;
10: import java.io.PrintStream;
12: /**
13: * A program to compare the running times to remove about 20% of a long list
14: * using three different methods: List::remove(int), List::remove(T), and
15: * Iterator::remove().
16: *
17: * @author Mark Young (A00000000)
18: */
19: public class RemovalComparisons {
21: public static final Scanner input = Utilities.KBD;
22: private static final String HEADER = "%10s %15s %15s%n";
23: private static final String RESULT = "%,10d %,15d %,15d%n";
24: private static final int MIN_N = 10;
25: private static final int MAX_N = 100000;
26: private static final int MULT = 10;
27: private static final int MAX_LEN = 5;
29: /**
30: * @param args the command line arguments
31: */
32: public static void main(String[] args) {
33: printIntroduction();
34: Utilities.pause();
36: Utilities.printTitle("Using List.remove(int)");
37: compareArrayLinked(list -> removeInt(list));
38: Utilities.pause();
40: Utilities.printTitle("Using List.remove(T)");
41: compareArrayLinked(list -> removeValue(list));
42: Utilities.pause();
44: Utilities.printTitle("Using Iterator.remove()");
45: compareArrayLinked(list -> removeIterator(list));
46: Utilities.pause();
47: }
49: private static void printIntroduction() {
50: Utilities.printTitle("Comparing Times for Removing List Elements");
51: Utilities.printParagraph("This program compares timing data for "
52: + "removing elements from ArrayLists and LinkedLists. "
53: + "It compares three different ways of doing the task.");
54: Utilities.printParagraph("All times are in nano-seconds. "
55: + "Times will vary from one run to another, "
56: + "sometimes by significant amounts. "
57: + "The pattern of results is what you should be considering.");
58: Utilities.printParagraph("By Mark Young (A00000000)");
59: }
61: /**
62: * Compare the run time for ArrayLists versus LinkedLists on the same task.
63: * Print out the timing comparison for various sizes of list.
64: *
65: * NOTE: Java optimizes its code as it runs. Thus the first few times you
66: * call a method it will take longer than the next few times. In order to
67: * prevent that optimization from messing up our timing data, we start by
68: * "warming up the engine". That is, we run the code for a little while
69: * before we start timing it. After it's been run a few times, the code
70: * should be totally optimized, so no more slow runs. Only then do we get
71: * down to measuring the time it takes to complete the full task.
72: *
73: * @param task the task to compare the lists on
74: */
75: private static void compareArrayLinked(
76: Consumer<List<String>> task) {
77: // warm up the engine
78: task.accept(getArrayList(10000));
79: task.accept(getLinkedList(10000));
81: // run the tests
82: System.out.printf(HEADER,
83: "N", "ArrayList(N)", "LinkedList(N)");
84: System.out.printf(HEADER,
85: "----------", "------------", "-------------");
86: for (int n = MIN_N; n <= MAX_N; n *= MULT) {
87: long arrayTime = time(getArrayList(n), task);
88: long linkTime = time(getLinkedList(n), task);
89: System.out.printf(RESULT, n, arrayTime, linkTime);
90: }
91: }
93: /**
94: * Create an ArrayList of the given size.
95: *
96: * @param size the size of the List to return
97: * @return a List of the given length
98: */
99: private static List<String> getArrayList(int size) {
100: return addItems(size, new ArrayList<>());
101: }
103: /**
104: * Create a LinkedList of the given size.
105: *
106: * @param size the size of the List to return
107: * @return a List of the given length
108: */
109: private static List<String> getLinkedList(int size) {
110: return addItems(size, new LinkedList<>());
111: }
113: /**
114: * Fill the given list with the first {@code size} items of the same
115: * pseudo-random sequence. When called twice with the same first argument,
116: * this method will produce two equal lists in its second argument.
117: *
118: * @param size the number of items to take
119: * @param list the list to put those items in
120: * @return a list containing the first {@code size} items of a fixed
121: * sequence
122: */
123: private static List<String> addItems(int size, List<String> list) {
124: // start with same random number generator every time
125: Random rand = getRandom();
127: // make sure the list is empty
128: list.clear();
130: // fill up the list
131: for (int i = 0; i < size; ++i) {
132: list.add(nextString(rand));
133: }
135: // send it back
136: return list;
137: }
139: /**
140: * Create a new Random object with the same seed every time. This guarantees
141: * the ability to generate the same pseudo-random sequence time and time
142: * again.
143: *
144: * @return a Random with the same seed every time
145: */
146: private static Random getRandom() {
147: return new Random(20240229);
148: }
150: /**
151: * Generate a random-length [0 to MAX_LEN) String of 'a's.
152: *
153: * @param rand the random number generator to use
154: * @return a String with 0 to MAX_LEN-1 'a's.
155: */
156: private static String nextString(Random rand) {
157: return "a".repeat(rand.nextInt(MAX_LEN));
158: }
160: /**
161: * Time how long it takes to run the consumer method with the given
162: * argument.
163: *
164: * @param list the List to give to the consumer method
165: * @param method a method that takes one List argument
166: * @return the amount of time it takes to complete the task, to nearest 100
167: * nanoseconds
168: */
169: private static long time(List<String> list, Consumer<List<String>> method) {
170: long start = System.nanoTime();
171: method.accept(list);
172: return System.nanoTime() - start;
173: }
175: /**
176: * Remove empty Strings from the given list. Use a count-controlled loop to
177: * go thru the list and use List.remove(int) to remove the String.
178: *
179: * @param list the List to remove empty Strings from
180: */
181: private static void removeInt(List<String> list) {
182: for (int i = 0; i < list.size(); ++i) {
183: if (list.get(i).isEmpty()) {
184: list.remove(i);
186: // BEEP the index so we don't skip what was the next item
187: --i;
188: }
189: }
190: }
192: /**
193: * Remove empty Strings from the given list. Use a count-controlled loop to
194: * go thru the list and use List.remove(T) to remove the String.
195: *
196: * @param list the List to remove empty Strings from
197: */
198: private static void removeValue(List<String> list) {
199: for (int i = 0; i < list.size(); ++i) {
200: String word = list.get(i);
201: if (word.isEmpty()) {
202: list.remove(word);
204: // BEEP the index so we don't skip what was the next item
205: --i;
206: }
207: }
208: }
210: /**
211: * Remove empty Strings from the given list. Use an iterator to go thru the
212: * list and use Iterator.remove() to remove the String.
213: *
214: * @param list the List to remove empty Strings from
215: */
216: private static void removeIterator(List<String> list) {
217: Iterator<String> it = list.iterator();
218: while (it.hasNext()) {
219: String word = it.next();
220: if (word.isEmpty()) {
221: it.remove();
222: }
223: }
224: }
226: }