|
|
|
Sponsored Link •
|
Summary
This entry is a replacement for "When Generics Fail" (which was deleted). In that, I began with casting solution, thinking that there wasn't a generic solution, then Krzysztof Sobolewski corrected me. So instead, I will compare the two solutions.
|
Advertisement
|
Both solutions work, but with generics you get static type checking -- although you may decide that the syntax is fairly heavy in the generic version.
Here's the old solution, for comparison. It uses Object and casting, instead of generics.
To prevent code duplication and to provide consistency among tests, I've put the basic functionality of the test process into a framework. This is another example of the Template Method design pattern. In this case, however, the core code (that doesn't change) is in the timedTest() method in a separate class Tester, and the Test.test() method is overridden for each particular test:
//: containers/Test.java
// Framework for performing timed tests on containers.
public abstract class Test {
static int size;
protected static int reps = 50000;
private String name;
// Pass the command-line arguments to this
// method, to modify the default number of reps:
public static void setReps(String[] commandLineArgs) {
if(commandLineArgs.length > 0)
reps = new Integer(commandLineArgs[0]);
}
public Test(String name) { this.name = name; }
public String toString() {
return String.format(Tester.stringField(), name);
}
// Override this Template Method for different tests:
abstract void test(Object container);
} ///:~
To use the framework, you create an array of Test objects and an array of container objects to be tested, and pass these to the Tester constructor. When you call run(), each test is run for each one of the container objects in your list, for three different data set sizes (given by the sizes array, which you can also change):
//: containers/Tester.java
// Applies Test objects to lists of different containers.
import java.util.*;
public class Tester {
public static int fieldWidth = 8;
public int[] sizes = { 10, 100, 1000 };
private Test[] tests;
private String alternateName;
private List containers;
static String stringField() {
return "%-" + fieldWidth + "s";
}
static String doubleField() {
return "%-" + fieldWidth + ".2f";
}
public Tester(Test[] tests, List containers) {
this.tests = tests;
this.containers = containers;
System.out.println(Test.reps + " repetitions");
}
public Tester(Test[] tests, List containers,
String alternateName) {
this(tests, containers);
this.alternateName = alternateName;
}
// Override this to modify pre-test initialization:
protected Object initialize(Object container) {
return container;
}
public void run() {
for(Object container : containers)
timedTest(container);
}
private void timedTest(Object container) {
String name = alternateName;
if(name == null)
name = container.getClass().getSimpleName();
System.out.println("-------------- " + name +
" --------------");
System.out.format(stringField(), "size");
for(Test tst : tests)
System.out.print(tst);
System.out.println();
for(int size : sizes) {
Test.size = size;
System.out.format(stringField(), size);
for(Test tst : tests) {
container = initialize(container);
long start = System.nanoTime();
tst.test(container); // Call the template method
double duration = System.nanoTime() - start;
duration /= (double)Test.size;
System.out.format(doubleField(), duration/1.0e7);
}
System.out.println();
}
}
} ///:~
The first constructor just uses the name of the class as the header, but if you want an alternate name, use the second constructor.
If you need to perform special initialization, override the initialize() method. This takes the container object and returns it after it's been initialized. You can see in test() that the result is assigned back to the container reference, and this allows you to replace the container with a completely different initialized container.
Tester also manages the formatting of the output, so it contains a fieldWidth that you can change. This is used to produce format strings.
All Lists hold their elements in the sequence in which you insert those elements. This program is a performance test for the most essential of the List operations:
//: containers/ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static Test[] tests = {
new Test("add") {
void test(Object container) {
List list = (List)container;
for(int i = 0; i < reps; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.add(j);
}
}
},
new Test("get") {
void test(Object container) {
List list = (List)container;
for(int i = 0; i < reps; i++) {
for(int j = 0; j < size; j++)
list.get(j);
}
}
},
new Test("set") {
void test(Object container) {
List list = (List)container;
for(int i = 0; i < reps; i++) {
for(int j = 0; j < size; j++)
list.set(j, 1);
}
}
},
new Test("iterate") {
void test(Object container) {
List list = (List)container;
//int passes = reps / 10;
for(int i = 0; i < reps; i++) {
for(Integer t : list)
;
}
}
},
new Test("insert") {
void test(Object container) {
List list = (List)container;
int half = list.size() / 2;
for(int i = 0; i < reps; i++)
list.add(half, 1);
}
},
new Test("remove") {
void test(Object container) {
List list = (List)container;
int half = list.size() / 2;
while(list.size() > half)
list.remove(0);
}
},
};
public static void main(String[] args) {
Test.setReps(args);
// Can only do these three tests on an array:
new Tester(new Test[] { tests[1], tests[2], tests[3] },
Arrays.asList(1), "Array as List") {
// This will be called before each test. The dummy
// container argument is replaced with an
// non-resizeable array-backed list:
protected Object initialize(Object container) {
Integer[] ia =
new CountingIntegerList(Test.size)
.toArray(new Integer[]{});
return Arrays.asList(ia);
}
}.run();
List> lists = Arrays.asList(
new ArrayList(),
new LinkedList(),
new Vector());
new Tester(tests, lists).run();
}
} /* Output: (Sample)
50000 repetitions
-------------- Array as List --------------
size get set iterate
10 0.12 0.17 0.45
100 0.09 0.12 0.28
1000 0.09 0.12 0.27
50000 repetitions
-------------- ArrayList --------------
size add get set iterate insert remove
10 0.31 0.17 0.28 0.36 16.59 12.46
100 0.57 0.16 0.33 0.33 1.67 1.24
1000 0.50 0.15 0.25 0.33 0.22 0.13
-------------- LinkedList --------------
size add get set iterate insert remove
10 0.67 0.19 0.27 0.38 0.14 0.04
100 0.59 0.41 0.46 0.22 0.05 0.00
1000 0.81 8.11 8.01 0.21 0.02 0.00
-------------- Vector --------------
size add get set iterate insert remove
10 0.45 0.14 0.17 0.39 17.12 12.49
100 0.45 0.13 0.19 0.33 1.67 1.25
1000 0.64 0.12 0.16 0.32 0.17 0.13
*///:~
Because the container argument is passed as an Object, each Test.test() method must cast the container argument to a Test ...
Depending on the behavior you desire, you can choose a TreeSet, a HashSet, or a LinkedHashSet. The following test program gives an indication of the performance trade-off between the implementations:
The performance of HashSet is generally superior to TreeSet, but in particular for addition and lookup, the two most important operations. The only reason TreeSet exists is because it maintains its elements in sorted order, so you use it only when you need a sorted Set. Because of the internal structure necessary to support sorting and because iteration is something you're more likely to do, iteration is faster with a TreeSet than a HashSet.
Note that LinkedHashSet is somewhat more expensive for insertions than HashSet; this is because of the extra cost of maintaining the linked list along with the hashed container. However, traversal appears to be more expensive for LinkedHashSet.
This program gives an indication of the trade-off between Map implementations:
To use the framework, you create an array of Test objects and an array of container objects to be tested, and pass these to the Tester constructor. When you call run(), each test is run for each one of the container objects in your list, for three different data set sizes (given by the sizes array, which you can also change):
//: containers/Tester.java
// Applies Test objects to lists of different containers.
import java.util.*;
public class Tester<C> {
public static int fieldWidth = 8;
public int[] sizes = { 10, 100, 1000 };
private List<Test<C>> tests;
private List<C> containers;
private String alternateName;
static String stringField() {
return "%-" + fieldWidth + "s";
}
static String doubleField() {
return "%-" + fieldWidth + ".2f";
}
public Tester(List<Test<C>> tests, List<C> containers) {
this.tests = tests;
this.containers = containers;
System.out.println(Test.reps + " repetitions");
}
public Tester(List<Test<C>> tests, List<C> containers,
String alternateName) {
this(tests, containers);
this.alternateName = alternateName;
}
// Override this to modify pre-test initialization:
protected C initialize(C container) {
return container;
}
public void run() {
for(C container : containers)
timedTest(container);
}
private void timedTest(C container) {
String name = alternateName;
if(name == null)
name = container.getClass().getSimpleName();
System.out.println("-------------- " + name +
" --------------");
System.out.format(stringField(), "size");
for(Test tst : tests)
System.out.print(tst);
System.out.println();
for(int size : sizes) {
Test.size = size;
System.out.format(stringField(), Test.size);
for(Test<C> tst : tests) {
container = initialize(container);
long start = System.nanoTime();
// Call the template method:
tst.test(container);
double duration = System.nanoTime() - start;
duration /= Test.size; // Normalize
System.out.format(doubleField(), duration / 1.0e7);
}
System.out.println();
}
}
} ///:~
The first constructor just uses the name of the class as the header, but if you want an alternate name, use the second constructor.
If you need to perform special initialization, override the initialize() method. This takes the container object and returns it after itÂ’s been initialized. You can see in test() that the result is assigned back to the container reference, and this allows you to replace the container with a completely different initialized container.
Tester also manages the formatting of the output, so it contains a fieldWidth that you can change. This is used to produce format strings.
All Lists hold their elements in the sequence in which you insert those elements. This program is a performance test for the most essential of the List operations:
//: containers/ListPerformance.java
// Demonstrates performance differences in Lists.
// {Args: 500} Small to keep build testing short
import java.util.*;
import net.mindview.util.*;
public class ListPerformance {
static List<Test<List<Integer>>> tests = Arrays.asList(
new Test<List<Integer>>("add") {
void test(List<Integer> list) {
for(int i = 0; i < reps; i++) {
list.clear();
for(int j = 0; j < size; j++)
list.add(j);
}
}
},
new Test<List<Integer>>("get") {
void test(List<Integer> list) {
for(int i = 0; i < reps; i++) {
for(int j = 0; j < size; j++)
list.get(j);
}
}
},
new Test<List<Integer>>("set") {
void test(List<Integer> list) {
for(int i = 0; i < reps; i++) {
for(int j = 0; j < size; j++)
list.set(j, 1);
}
}
},
new Test<List<Integer>>("iterate") {
void test(List<Integer> list) {
for(int i = 0; i < reps; i++) {
Iterator<Integer> it = list.iterator();
while(it.hasNext())
it.next();
}
}
},
new Test<List<Integer>>("insert") {
void test(List<Integer> list) {
int half = list.size() / 2;
for(int i = 0; i < reps; i++)
list.add(half, 1);
}
},
new Test<List<Integer>>("remove") {
void test(List<Integer> list) {
int half = list.size() / 2;
while(list.size() > half)
list.remove(0);
}
}
);
public static void main(String[] args) {
Test.setReps(args);
List<List<Integer>> dummy =
new ArrayList<List<Integer>>(1);
dummy.add(new ArrayList<Integer>());
// Can only do these three tests on an array:
new Tester<List<Integer>>(tests.subList(1, 4), dummy,
"Array as List") {
// This will be called before each test. The
// dummy container argument is replaced with
// a non-resizeable array-backed list:
@Override protected List<Integer> initialize(
List<Integer> container) {
Integer[] ia = Generated.array(Integer.class,
new CountingGenerator.Integer(), Test.size);
return Arrays.asList(ia);
}
}.run();
List<List<Integer>> lists =
Arrays.<List<Integer>>asList(
new ArrayList<Integer>(),
new LinkedList<Integer>(),
new Vector<Integer>());
new Tester<List<Integer>>(tests, lists).run();
}
} /* Output: (Sample)
50000 repetitions
-------------- Array as List --------------
size get set iterate
10 0.12 0.18 0.41
100 0.09 0.13 0.25
1000 0.09 0.14 0.25
50000 repetitions
-------------- ArrayList --------------
size add get set iterate insert remove
10 0.39 0.17 0.24 0.31 18.05 13.55
100 0.57 0.16 0.32 0.28 1.91 1.46
1000 0.72 0.17 0.31 0.35 0.19 0.15
-------------- LinkedList --------------
size add get set iterate insert remove
10 0.80 0.35 0.35 0.37 0.16 0.05
100 0.87 0.57 0.72 0.24 0.06 0.00
1000 0.93 8.16 13.05 0.20 0.03 0.00
-------------- Vector --------------
size add get set iterate insert remove
10 0.48 0.15 0.27 0.40 18.36 13.43
100 0.44 0.13 0.26 0.34 1.78 1.36
1000 0.58 0.13 0.25 0.37 0.21 0.16
*///:~
To compare array access to container access (primarily against ArrayList), a special test is created for arrays by wrapping an array as a List using Arrays.asList( ). Only three of the tests can be performed in this case, because you cannot insert or remove elements from an array. Notice that the initialize() method throws away the container argument (so that argument is a dummy object) and creates a completely new object using Generated.array() (which was defined in the Arrays chapter).
In main(), the definition of lists requires an explicit type argument specification to give a hint to the Arrays.asList() method call.
Depending on the behavior you desire, you can choose a TreeSet, a HashSet, or a LinkedHashSet. The following test program gives an indication of the performance trade-off between the implementations:
//: containers/SetPerformance.java
// {Args: 500}
import java.util.*;
public class SetPerformance {
static List<Test<Set<Integer>>> tests = Arrays.asList(
new Test<Set<Integer>>("add") {
void test(Set<Integer> set) {
for(int i = 0; i < reps; i++) {
set.clear();
for(int j = 0; j < size; j++)
set.add(j);
}
}
},
new Test<Set<Integer>>("contains") {
void test(Set<Integer> set) {
for(int i = 0; i < reps; i++)
for(int j = 0; j < size; j++)
set.contains(j);
}
},
new Test<Set<Integer>>("iterate") {
void test(Set<Integer> set) {
for(int i = 0; i < reps * 10; i++) {
Iterator<Integer> it = set.iterator();
while(it.hasNext())
it.next();
}
}
}
);
public static void main(String[] args) {
Test.setReps(args);
List<Set<Integer>> sets = Arrays.<Set<Integer>>asList(
new TreeSet<Integer>(),
new HashSet<Integer>(),
new LinkedHashSet<Integer>());
Tester.fieldWidth = 10;
new Tester<Set<Integer>>(tests, sets).run();
}
} /* Output: (Sample)
50000 repetitions
-------------- TreeSet --------------
size add contains iterate
10 2.12 0.67 5.01
100 2.97 0.97 3.32
1000 4.60 2.48 3.40
-------------- HashSet --------------
size add contains iterate
10 1.01 0.32 4.36
100 0.98 0.30 3.89
1000 1.25 0.88 4.20
-------------- LinkedHashSet --------------
size add contains iterate
10 1.59 0.43 4.73
100 1.60 0.33 3.33
1000 1.83 0.68 3.05
*///:~
This program gives an indication of the trade-off between Map implementations:
//: containers/MapPerformance.java
// Demonstrates performance differences in Maps.
// {Args: 500}
import java.util.*;
public class MapPerformance {
static List<Test<Map<Integer,Integer>>> tests =
Arrays.asList(
new Test<Map<Integer,Integer>>("put") {
void test(Map<Integer,Integer> map) {
for(int i = 0; i < reps; i++) {
map.clear();
for(int j = 0; j < size; j++)
map.put(j, j);
}
}
},
new Test<Map<Integer,Integer>>("get") {
void test(Map<Integer,Integer> map) {
for(int i = 0; i < reps; i++)
for(int j = 0; j < size; j++)
map.get(j);
}
},
new Test<Map<Integer,Integer>>("iterate") {
void test(Map<Integer,Integer> map) {
for(int i = 0; i < (reps * 10); i++) {
Iterator it = map.entrySet().iterator();
while(it.hasNext())
it.next();
}
}
}
);
public static void main(String[] args) {
Test.setReps(args);
List<Map<Integer,Integer>> maps = Arrays.asList(
new TreeMap<Integer,Integer>(),
new HashMap<Integer,Integer>(),
new LinkedHashMap<Integer,Integer>(),
new IdentityHashMap<Integer,Integer>(),
new WeakHashMap<Integer,Integer>(),
new Hashtable<Integer,Integer>());
new Tester<Map<Integer,Integer>>(tests, maps).run();
}
} /* Output: (Sample)
50000 repetitions
-------------- TreeMap --------------
size put get iterate
10 2.13 0.71 5.18
100 3.11 0.95 3.16
1000 4.34 1.94 3.43
-------------- HashMap --------------
size put get iterate
10 0.95 0.37 4.51
100 0.91 0.28 3.94
1000 1.40 0.62 4.01
-------------- LinkedHashMap --------------
size put get iterate
10 1.37 0.47 3.62
100 1.32 0.38 2.45
1000 1.98 0.75 2.50
-------------- IdentityHashMap --------------
size put get iterate
10 1.22 0.69 4.23
100 1.02 0.63 3.87
1000 2.04 1.34 3.41
-------------- WeakHashMap --------------
size put get iterate
10 1.60 0.59 7.45
100 1.49 0.54 6.81
1000 2.26 0.76 1.07
-------------- Hashtable --------------
size put get iterate
10 1.08 0.51 5.45
100 0.99 0.67 4.08
1000 1.50 0.82 3.81
*///:~
Have an opinion?
Readers have already posted
6
comments
about this weblog entry. Why not
add yours?
If you'd like to be notified whenever Bruce Eckel adds a new entry to his weblog, subscribe to his RSS feed.
Choosing between Sets
//: containers/SetPerformance.java
// {Args: 500}
import java.util.*;
public class SetPerformance {
private static Test[] tests = {
new Test("add") {
void test(Object container) {
Set
Choosing between Maps
//: containers/MapPerformance.java
// Demonstrates performance differences in Maps.
// {Args: 500}
import java.util.*;
public class MapPerformance {
private static Test[] tests = {
new Test("put") {
void test(Object container) {
Map
The generic solution
Here's the new solution, which uses generics:
//: containers/Test.java
// Framework for performing timed tests.
public abstract class Test<C> {
static int size;
protected static int reps = 50000;
private String name;
// Pass the command-line arguments to this
// method, to modify the default number of reps:
public static void setReps(String[] commandLineArgs) {
if(commandLineArgs.length > 0)
reps = Integer.parseInt(commandLineArgs[0]);
}
public Test(String name) { this.name = name; }
public String toString() {
return String.format(Tester.stringField(), name);
}
// Override this Template Method for different tests:
abstract void test(C container);
} ///:~
Choosing between Lists
Choosing between Sets
Choosing between Maps
Talk Back!
RSS Feed
About the Blogger
Bruce Eckel (www.BruceEckel.com) provides development assistance in Python with user interfaces in Flex. He is the author of Thinking in Java (Prentice-Hall, 1998, 2nd Edition, 2000, 3rd Edition, 2003, 4th Edition, 2005), the Hands-On Java Seminar CD ROM (available on the Web site), Thinking in C++ (PH 1995; 2nd edition 2000, Volume 2 with Chuck Allison, 2003), C++ Inside & Out (Osborne/McGraw-Hill 1993), among others. He's given hundreds of presentations throughout the world, published over 150 articles in numerous magazines, was a founding member of the ANSI/ISO C++ committee and speaks regularly at conferences. This weblog entry is Copyright © 2005 Bruce Eckel. All rights reserved.
|
Sponsored Links
|
Digg
del.icio.us
Reddit