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;
10: ;
12: /**
13: *
14: * @author Mark Young (A00000000)
15: */
16: public class RemovalComparisons {
18: public static final Scanner input = Utilities.KBD;
19: private static final String HEADER = "%10s %15s %15s%n";
20: private static final String RESULT = "%,10d %,15d %,15d%n";
21: private static final int MIN_N = 10;
22: private static final int MAX_N = 100000;
23: private static final int MULT = 10;
24: private static final int MAX_LEN = 5;
26: /**
27: * @param args the command line arguments
28: */
29: public static void main(String[] args) {
30: printIntroduction();
32: Utilities.printTitle("Using List.remove(int)");
33: compareArrayLinked(list -> removeInt(list));
34: Utilities.pause();
36: Utilities.printTitle("Using List.remove(T)");
37: compareArrayLinked(list -> removeValue(list));
38: Utilities.pause();
40: Utilities.printTitle("Using Iterator.remove()");
41: compareArrayLinked(list -> removeIterator(list));
42: Utilities.pause();
43: }
45: private static void printIntroduction() {
46: Utilities.printTitle("Comparing Times for Removing List Elements");
47: Utilities.printParagraph("This program compares timing data for "
48: + "removing elements from ArrayLists and LinkedLists. "
49: + "It compares three different ways of doing the task.");
50: Utilities.printParagraph("By Mark Young (A00000000)");
51: Utilities.pause();
52: }
54: /**
55: * Compare the run time for ArrayLists versus LinkedLists on the same task.
56: * Print out the timing comparison for various sizes of list.
57: *
58: * @param task the task to compare the lists on
59: */
60: private static void compareArrayLinked(
61: Consumer<List<String>> task) {
62: // make sure all JIT compiling done
63: task.accept(getArrayList(10));
64: task.accept(getLinkedList(10));
66: // run the tests
67: System.out.printf(HEADER,
68: "N", "ArrayList(N)", "LinkedList(N)");
69: System.out.printf(HEADER,
70: "----------", "------------", "-------------");
71: for (int n = MIN_N; n <= MAX_N; n *= MULT) {
72: long arrayTime = time(getArrayList(n), task);
73: long linkTime = time(getLinkedList(n), task);
74: System.out.printf(RESULT, n, arrayTime, linkTime);
75: }
76: }
78: /**
79: * Create an ArrayList of the given size.
80: *
81: * @param size the size of the List to return
82: * @return a List of the given length
83: */
84: private static List<String> getArrayList(int size) {
85: return addItems(size, new ArrayList<>());
86: }
88: /**
89: * Create a LinkedList of the given size.
90: *
91: * @param size the size of the List to return
92: * @return a List of the given length
93: */
94: private static List<String> getLinkedList(int size) {
95: return addItems(size, new LinkedList<>());
96: }
98: /**
99: * Fill the given list with the first {@code size} items of the same
100: * pseudo-random sequence. When called twice with the same first argument,
101: * this method will produce two equal lists in its second argument.
102: *
103: * @param size the number of items to take
104: * @param list the list to put those items in
105: * @return a list containing the first {
106: * @size} items of a fixed sequence
107: */
108: private static List<String> addItems(int size, List<String> list) {
109: // start with same random number generator every time
110: Random rand = getRandom();
112: // make sure the list is empty
113: list.clear();
115: // fill up the list
116: for (int i = 0; i < size; ++i) {
117: list.add(nextString(rand));
118: }
120: // send it back
121: return list;
122: }
124: /**
125: * Create a new Random object with the same seed every time. This guarantees
126: * the ability to generate the same pseudo-random sequence time and time
127: * again.
128: *
129: * @return a Random with the same seed every time
130: */
131: private static Random getRandom() {
132: return new Random(20240229);
133: }
135: /**
136: * Generate a random-length (0 to MAX_LEN) String of 'a's.
137: *
138: * @param rand the random number generator to use
139: * @return a String with 0 to MAX_LEN 'a's.
140: */
141: private static String nextString(Random rand) {
142: return "a".repeat(rand.nextInt(MAX_LEN));
143: }
145: /**
146: * Time how long it takes to run the consumer method with the given
147: * argument.
148: *
149: * @param list the List to give to the consumer method
150: * @param method a method that takes one List argument
151: * @return the amount of time it takes to complete the task, to nearest 100
152: * nanoseconds
153: */
154: private static long time(List<String> list, Consumer<List<String>> method) {
155: long start = System.nanoTime();
156: method.accept(list);
157: return System.nanoTime() - start;
158: }
160: /**
161: * Remove empty Strings from the given list. Use a count-controlled loop to
162: * go thru the list and use List.remove(int) to remove the String.
163: *
164: * @param list the List to remove empty Strings from
165: */
166: private static void removeInt(List<String> list) {
167: for (int i = 0; i < list.size(); ++i) {
168: if (list.get(i).isEmpty()) {
169: list.remove(i);
171: // BEEP the index so we don't skip what was the next item
172: --i;
173: }
174: }
175: }
177: /**
178: * Remove empty Strings from the given list. Use a count-controlled loop to
179: * go thru the list and use List.remove(T) to remove the String.
180: *
181: * @param list the List to remove empty Strings from
182: */
183: private static void removeValue(List<String> list) {
184: for (int i = 0; i < list.size(); ++i) {
185: String word = list.get(i);
186: if (word.isEmpty()) {
187: list.remove(word);
189: // BEEP the index so we don't skip what was the next item
190: --i;
191: }
192: }
193: }
195: /**
196: * Remove empty Strings from the given list. Use an iterator to go thru the
197: * list and use Iterator.remove() to remove the String.
198: *
199: * @param list the List to remove empty Strings from
200: */
201: private static void removeIterator(List<String> list) {
202: Iterator<String> it = list.iterator();
203: while (it.hasNext()) {
204: String word = it.next();
205: if (word.isEmpty()) {
206: it.remove();
207: }
208: }
209: }
211: }