public static void test(Comparator<String> comparator, String name)
{
for (int i = 0; i < tests; ++i)
{
List<String> list = createList();
Benchmark bm = new Benchmark(name);
bm.start();
Collections.sort(list, comparator); // <--- hier
bm.stop();
System.out.println(bm);
}
System.out.println();
}
}/[code]
Die markierten Zeile wird ja 10x durchlaufen, aber es wird immer dasselbe Comparator-Objekt verwendet. Man muss hier aber mit einem frischen Comparator anfangen, sonst sind die Tests ja nicht unabhängig voneinander. Jetzt implementieren die Comparatoren ein neues Interface, das das Erzeugen eines frischen Objekts polymorph ermöglicht:
[code]interface Vergleich extends Comparator<String>
{
public Vergleich neuerVergleich();
}
class Direct implements Vergleich
{
public int compare(String s1, String s2)
{
final int minlen = Math.min(s1.length(), s2.length());
for (int i = 0; i < minlen; ++i)
{
char c = s1.charAt(i);
if (c == '*') c = '\uffff';
char d = s2.charAt(i);
if (d == '*') d = '\uffff';
if (c < d)
return -1;
else if (d < c) return 1;
}
final int deltalen = s1.length() - s2.length();
return deltalen < 0 ? -1 : deltalen > 0 ? 1 : 0;
}
public Vergleich neuerVergleich()
{
return this;
}
}
class Uncached implements Vergleich
{
public int compare(String s1, String s2)
{
String t1 = s1.replace('*', '\uffff');
String t2 = s2.replace('*', '\uffff');
return t1.compareTo(t2);
}
public Vergleich neuerVergleich()
{
return this;
}
}
class Cached implements Vergleich
{
private final Map<String, String> cache = new HashMap<String, String>();
private String lookup(String s)
{
String t = cache.get(s);
if (t == null)
{
t = s.replace('*', '\uffff');
cache.put(s, t);
}
return t;
}
public int compare(String s1, String s2)
{
return lookup(s1).compareTo(lookup(s2));
}
public Vergleich neuerVergleich()
{
return new Cached();
}
}
class Capacity implements Vergleich
{
private final Map<String, String> cache;
private final int capacity;
public Capacity(int capacity)
{
cache = new HashMap<String, String>(capacity);
this.capacity = capacity;
}
private String lookup(String s)
{
String t = cache.get(s);
if (t == null)
{
t = s.replace('*', '\uffff');
cache.put(s, t);
}
return t;
}
public int compare(String s1, String s2)
{
return lookup(s1).compareTo(lookup(s2));
}
public Vergleich neuerVergleich()
{
return new Capacity(capacity);
}
}
public class Test
{
private static final int tests = 10;
private static final int size = 100000;
private static final int maxlen = 50;
private static final int seed = 0;
private static List<String> createList()
{
List<String> list = new ArrayList<String>(size);
Random random = new Random(seed);
for (int i = 0; i < size; ++i)
{
int n = 1 + random.nextInt(maxlen);
char[] a = new char[n];
for (int k = 0; k < n; ++k)
a[k] = (char) (97 + random.nextInt(26));
if (random.nextBoolean()) a[n - 1] = '*';
list.add(new String(a));
}
return list;
}
public static void main(String[] args)
{
test(new Direct(), "direct");
test(new Uncached(), "uncached");
test(new Cached(), "cached");
test(new Capacity(2 * size), "capacity");
}
private static void test(Vergleich vergleich, String name)
{
for (int i = 0; i < tests; ++i)
{
List<String> list = createList();
Vergleich neuerVergleich = vergleich.neuerVergleich();
Benchmark bm = new Benchmark(name);
bm.start();
Collections.sort(list, neuerVergleich);
bm.stop();
System.out.println(bm);
}
System.out.println();
}
}
class Benchmark
{
private final String name;
private boolean running;
private long start;
private long sum;
public Benchmark(String name)
{
this.name = name;
running = false;
}
public void start()
{
assert !running;
running = true;
start = System.nanoTime();
}
public void stop()
{
long stop = System.nanoTime();
assert running;
sum += stop - start;
running = false;
}
public String toString()
{
long l = sum;
String s = "ns";
if (l > 9999)
{
l /= 1000;
s = "µs";
if (l > 9999)
{
l /= 1000;
s = "ms";
}
}
return String.format("%s: %d %s", name, l, s);
}
}
