[ Pobierz całość w formacie PDF ]
.5151.1206.51000150.6177.440.041055.082.0192.0HashSet10045.690.0202.2100036.14106.539.39The performance of HashSet isgenerally superior to TreeSet for all operations (but in particularaddition and lookup, the two most important operations).The only reasonTreeSet exists is because it maintains its elements in sorted order, soyou only use it when you need a sortedSet.Choosing between MapsWhen choosing between implementations ofMap, the size of the Map is what moststrongly affects performance, and the following test program gives an indicationof this trade-off:[ Add Comment ]//: c09:MapPerformance.java// Demonstrates performance differences in Maps.import java.util.*;import com.bruceeckel.util.*;public class MapPerformance {private abstract static class Tester {String name;Tester(String name) { this.name = name; }abstract void test(Map m, int size, int reps);}private static Tester[] tests = {new Tester("put") {void test(Map m, int size, int reps) {for(int i = 0; i < reps; i++) {m.clear();Collections2.fill(m,Collections2.geography.reset(), size);}}},new Tester("get") {void test(Map m, int size, int reps) {for(int i = 0; i < reps; i++)for(int j = 0; j < size; j++)m.get(Integer.toString(j));}},new Tester("iteration") {void test(Map m, int size, int reps) {for(int i = 0; i < reps * 10; i++) {Iterator it = m.entrySet().iterator();while(it.hasNext())it.next();}}},};public static voidtest(Map m, int size, int reps) {System.out.println("Testing " +m.getClass().getName() + " size " + size);Collections2.fill(m,Collections2.geography.reset(), size);for(int i = 0; i < tests.length; i++) {System.out.print(tests[i].name);long t1 = System.currentTimeMillis();tests[i].test(m, size, reps);long t2 = System.currentTimeMillis();System.out.println(": " +((double)(t2 - t1)/(double)size));}}public static void main(String[] args) {int reps = 50000;// Or, choose the number of repetitions// via the command line:if(args.length > 0)reps = Integer.parseInt(args[0]);// Small:test(new TreeMap(), 10, reps);test(new HashMap(), 10, reps);test(new Hashtable(), 10, reps);// Medium:test(new TreeMap(), 100, reps);test(new HashMap(), 100, reps);test(new Hashtable(), 100, reps);// Large:test(new TreeMap(), 1000, reps);test(new HashMap(), 1000, reps);test(new Hashtable(), 1000, reps);}} ///:~Because the size of the map is the issue,you’ll see that the timing tests divide the time by the size to normalizeeach measurement.Here is one set of results.(Yours will probably bedifferent.)TypeTest sizePutGetIteration10143.0110.0186.0TreeMap100201.1188.4280.11000222.8205.240.71066.083.0197.0HashMap10080.7135.7278.5100048.2105.741.41061.093.0302.0Hashtable10090.6143.3329.0100054.1110.9547.3As you might expect,Hashtable performance is roughly equivalent toHashMap.(You can also see that HashMap is generally a bit faster.HashMap is intended to replace Hashtable.) TheTreeMap is generally slower than theHashMap, so why would you use it? So you could use it not as aMap, but as a way to create an ordered list.The behavior of atree is such that it’s always in order and doesn’t have to bespecially sorted.Once you fill a TreeMap, you can callkeySet( ) to get a Set view of thekeys, then toArray( ) to produce an array ofthose keys.You can then use the static methodArrays.binarySearch( ) (discussed later) to rapidly find objects inyour sorted array.Of course, you would probably only do this if, for somereason, the behavior of a HashMap was unacceptable, since HashMapis designed to rapidly find things.Also, you can easily create a HashMapfrom a TreeMap with a single object creation In the end, whenyou’re using a Map your first choice should be HashMap, andonly if you need a constantly sorted Map will you needTreeMap.Sorting and searchingListsUtilities to perform sorting andsearching for Lists have the same names andsignatures as those for sorting arrays of objects, but are static methodsof Collections instead of Arrays.Here’s an example, modified fromArraySearching.java://: c09:ListSortSearch.java// Sorting and searching Lists with 'Collections.'import com.bruceeckel.util.*;import java.util.*;public class ListSortSearch {public static void main(String[] args) {List list = new ArrayList();Collections2.fill(list,Collections2.capitals, 25);System.out
[ Pobierz całość w formacie PDF ]