Algorithmen & Datenstrukturen mit Java: Test mit zufälligem und sortiertem Einfügen
| Algorithmen & Datenstrukturen mit Java: Test mit zufälligem und sortiertem Einfügen |
|
1package tests.persistent.map;
2
3import java.util.Iterator;
4import java.util.Random;
5
6import ds.persistent.map.BinaryTree;
7import ds.util.KV;
8import ds.util.K;
9
10import static ds.util.K.mkK;
11import static ds.util.V.mkV;
12import static ds.util.KV.mkPair;
13
14import tests.util.Args;
15
16public class BinaryTreeRandom {
17
18 public static void main(String [] args) {
19 int noOfElems = Args.getInt(args, 0, 1023);
20
21 new Main(noOfElems)
22 .run();
23 }
24
25 private static
26 class Main
27 extends tests.persistent.map.util.MainBinaryTree {
28
29 final Random r;
30
31 Main(int n1) {
32 super(n1);
33 r = new Random(42);
34 }
35
36 protected void buildTree() {
37 buildTreeSimple();
38 buildTreeSmart();
39 }
40
41 protected void buildTreeSimple() {
42 startTime("building binary search tree by inserting " +
43 n +
44 " random integers\n" +
45 "(simple version by stepwise insertion)");
46 for (int i = 0; i < n; ++i) {
47 int k = r.nextInt();
48 t = t.insert(mkK(k), mkV(i));
49 }
50 stopTime();
51 }
52
53 protected void buildTreeSmart() {
54 startTime("building binary search tree by inserting " +
55 n +
56 " random integers\n" +
57 "(with iterator)");
58
59 Iterator<KV> elems
60 = new ds.util.Iterator<KV>() {
61 int i = 0;
62 public boolean hasNext() {
63 return
64 i < n;
65 }
66 public KV next() {
67 int k = r.nextInt();
68 ++i;
69 return
70 mkPair(mkK(k), mkV(i));
71 }
72 };
73 t = BinaryTree.fromIterator(elems);
74
75 stopTime();
76 }
77
78 protected void removeAll() {
79 startTime("removing all elements by stepwise removing the root element");
80
81 for (int i = t.size(); i > 0; --i) {
82 K k = t.findRoot().fst;
83 t = t.remove(k);
84 }
85 stopTime();
86 }
87 }
88}
1package tests.persistent.map;
2
3import ds.persistent.map.BinaryTree;
4import ds.util.KV;
5import ds.util.K;
6
7import static ds.util.K.mkK;
8import static ds.util.V.mkV;
9import static ds.util.KV.mkPair;
10
11import tests.util.Args;
12
13public class BinaryTreeWorstCase {
14
15 public static void main(String [] args) {
16 int noOfElems = Args.getInt(args, 0, 1023);
17
18 (new Main(noOfElems)).run();
19 }
20
21 private static
22 class Main
23 extends tests.persistent.map.util.MainBinaryTree {
24
25 Main(int n1) {
26 super(n1);
27 }
28
29 protected void buildTree() {
30 startTime("building binary search tree by inserting " +
31 n +
32 " elements in ascending order (worst case)");
33 for (int i = 0; i < n; ++i) {
34 t = t.insert(mkK(i), mkV(i));
35 }
36 stopTime();
37 }
38
39 protected void removeAll() {
40 startTime("removing all elements in ascending order");
41
42 for (int i = 0; i < n; ++i) {
43 t = t.remove(mkK(i));
44 }
45 stopTime();
46 }
47 }
48}
1package tests.persistent.map.util;
2
3import ds.persistent.map.BinaryTree;
4import ds.util.KV;
5
6import static ds.persistent.map.BinaryTree.empty;
7
8public abstract class MainBinaryTree
9 extends tests.util.Main {
10
11 protected BinaryTree t;
12 protected final int n;
13
14 protected MainBinaryTree(int n1) {
15 t = (BinaryTree)empty();
16 n = n1;
17 }
18
19 protected abstract void buildTree();
20 protected abstract void removeAll();
21
22 protected void balanceTree() {
23 startTime("balance tree");
24 t = t.balance();
25 stopTime();
26 }
27
28 protected void lookupAll(int times) {
29 startTime("looking up all elements in tree " + times + " times");
30
31 boolean found = true;
32 for (int j = 0; j < times; ++j)
33 for (KV p : t) {
34 found &= (t.lookup(p.fst) == p.snd);
35 }
36 stopTime();
37 }
38
39 protected void traverse(int times) {
40 startTime("traversing all elements in tree " + times + " times");
41
42 int res = 0;
43 for (int j = 0; j < times; ++j)
44 for (KV p : t) {
45 res += p.fst.key;
46 }
47 stopTime();
48 }
49
50 protected void stats() {
51 if ( n < 10 )
52 msg("t = " + t);
53 msg("t.inv() = " + t.inv());
54 msg("t.size() = " + t.size());
55 msg("t.depth() = " + t.depth());
56 msg("t.minDepth() = " + t.minDepth());
57 msg("t.balanced() = " + t.balanced());
58 msg("");
59 }
60
61 protected void memStats() {
62 msg(t.objStats());
63 msg("");
64 }
65
66 protected void classStats() {
67 msg(BinaryTree.stats());
68 }
69
70 public void run() {
71 nl();
72 buildTree();
73 stats();
74 memStats();
75 traverse(20);
76 lookupAll(20);
77 balanceTree();
78 lookupAll(20);
79 stats();
80 removeAll();
81 stats();
82 classStats();
83 }
84}
|
| Letzte Änderung: 18.12.2015 | © Prof. Dr. Uwe Schmidt |
