public class StringListRemovals
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;
10: /**
11: * A program to compare the running times to remove about 20% of a long list
12: * using three different methods: List::remove(int), List::remove(T), and
13: * Iterator::remove().
14: *
15: * @author Mark Young (A00000000)
16: */
17: public class StringListRemovals {
19: public static final Scanner input = Utilities.KBD;
20: private static final String HEADER = "%10s %15s %15s%n";
21: private static final String RESULT = "%,10d %,15d %,15d%n";
22: private static final int MIN_N = 10;
23: private static final int MAX_N = 100000;
24: private static final int MULT = 10;
25: private static final int MAX_LEN = 5;
27: /**
28: * @param args the command line arguments
29: */
30: public static void main(String[] args) {
31: printIntroduction();
32: Utilities.pause();
34: Utilities.printTitle("Using List.remove(int)");
35: compareArrayLinked(list -> removeInt(list));
36: Utilities.pause();
38: Utilities.printTitle("Using List.remove(T)");
39: compareArrayLinked(list -> removeValue(list));
40: Utilities.pause();
42: Utilities.printTitle("Using Iterator.remove()");
43: compareArrayLinked(list -> removeIterator(list));
44: Utilities.pause();
45: }
47: private static void printIntroduction() {
48: Utilities.printTitle("Comparing Times for Removing List Elements");
49: Utilities.printParagraph("This program compares timing data for "
50: + "removing elements from ArrayLists and LinkedLists. "
51: + "It compares three different ways of doing the task.");
52: Utilities.printParagraph("All times are in nano-seconds. "
53: + "Times will vary from one run to another, "
54: + "sometimes by significant amounts. "
55: + "The pattern of results is what you should be considering.");
56: Utilities.printParagraph("This version of the program uses lists of "
57: + "Strings.");
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("a".repeat(rand.nextInt(MAX_LEN)));
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: * Time how long it takes to run the consumer method with the given
152: * argument.
153: *
154: * @param list the List to give to the consumer method
155: * @param method a method that takes one List argument
156: * @return the amount of time it takes to complete the task, to nearest 100
157: * nanoseconds
158: */
159: private static long time(List<String> list, Consumer<List<String>> method) {
160: long start = System.nanoTime();
161: method.accept(list);
162: return System.nanoTime() - start;
163: }
165: /**
166: * Remove empty Strings from the given list. Use a count-controlled loop to
167: * go thru the list and use List.remove(int) to remove the String.
168: *
169: * @param list the List to remove empty Strings from
170: */
171: private static void removeInt(List<String> list) {
172: for (int i = 0; i < list.size(); ++i) {
173: if (list.get(i).isEmpty()) {
174: list.remove(i);
176: // BEEP the index so we don't skip what was the next item
177: --i;
178: }
179: }
180: }
182: /**
183: * Remove empty Strings from the given list. Use a count-controlled loop to
184: * go thru the list and use List.remove(T) to remove the String.
185: *
186: * @param list the List to remove empty Strings from
187: */
188: private static void removeValue(List<String> list) {
189: for (int i = 0; i < list.size(); ++i) {
190: String word = list.get(i);
191: if (word.isEmpty()) {
192: list.remove(word);
194: // BEEP the index so we don't skip what was the next item
195: --i;
196: }
197: }
198: }
200: /**
201: * Remove empty Strings from the given list. Use an iterator to go thru the
202: * list and use Iterator.remove() to remove the String.
203: *
204: * @param list the List to remove empty Strings from
205: */
206: private static void removeIterator(List<String> list) {
207: Iterator<String> it = list.iterator();
208: while (it.hasNext()) {
209: String word = it.next();
210: if (word.isEmpty()) {
211: it.remove();
212: }
213: }
214: }
216: }