Algorithmen & Datenstrukturen mit Java: Test mit zufälligem Einfügen
| Algorithmen & Datenstrukturen mit Java: Test mit zufälligem Einfügen |
|
1package tests.persistent.map;
2
3import java.util.Random;
4
5import ds.persistent.map.IntMap;
6
7import ds.util.K; // example class for keys
8import ds.util.V; // example class for values
9import ds.util.KV; // key value pair
10import ds.util.Pair;
11
12import static ds.util.K.mkK;
13import static ds.util.V.mkV;
14import static ds.util.KV.mkPair;
15
16import tests.util.Args;
17
18public class IntMapTest {
19
20 public static void main(String [] args) {
21 int noOfElems = Args.getInt(args, 0, 1023);
22
23 (new Main(noOfElems)).run();
24 }
25
26 private static
27 class Main
28 extends tests.util.Main {
29
30 IntMap t;
31 final int n;
32 final Random r;
33 final int traceTree;
34
35 Main(int n1) {
36 t = IntMap.empty();
37 n = n1;
38 r = new Random(42);
39 traceTree = 255;
40 }
41
42 void buildTree() {
43 startTime("building binary patricia tree by inserting " +
44 n +
45 " random integers");
46 for (int i = 0; i < n; ++i) {
47 int k = (int)r.nextLong() >>> 1; // test with values >= 0;
48 if (n <= traceTree) {
49 // simplify tree output
50 // only the least significant byte
51 // of key is of interest
52 k &= 0xFF;
53 }
54 t = t.insert(mkK(k), mkV(i));
55 /*
56 if ( ! t.inv() ) {
57 msg("t.insert(" + k + "," + i + ") violates invariant");
58 msg("t = " + t);
59 }
60 */
61 }
62 stopTime();
63 }
64
65 void deleteTree() {
66 startTime("deleting a tree by removing " +
67 n +
68 " elements in ascending order");
69
70 // this only works for persistent data structures
71 // "removal" is done during iteration
72
73 for (KV p : t) {
74 t = t.remove(p.fst);
75 }
76 stopTime();
77 }
78
79 void lookupAll(int times) {
80 startTime("looking up all elements in tree " + times + " times");
81
82 boolean found = true;
83 for (int j = 0; j < times; ++j)
84 for (KV p : t) {
85 found &= (t.lookup(p.fst) == p.snd);
86 }
87 stopTime();
88 }
89
90 void traverse(int times) {
91 startTime("traversing all elements in tree " + times + " times");
92
93 int res = 0;
94 for (int j = 0; j < times; ++j)
95 for (KV p : t) {
96 res += p.fst.key;
97 }
98 stopTime();
99 }
100
101 void stats() {
102 int s = t.size();
103 if ( s < 256 ) {
104 msg("t = " + t);
105 }
106 msg("t.inv() = " + t.inv());
107 msg("t.size() = " + t.size());
108 msg("");
109 if ( 0 < s && s <= traceTree ) {
110 msg("internal tree structure:\n");
111 msg(t.showIntMap());
112 msg("");
113 }
114 }
115
116 void memStats() {
117 msg(t.objStats());
118 }
119
120 void classStats() {
121 msg(IntMap.stats());
122 }
123
124 public void run() {
125 nl();
126 buildTree();
127 stats();
128 memStats();
129 classStats();
130 traverse(20);
131 lookupAll(20);
132 deleteTree();
133 stats();
134 classStats();
135 }
136 }
137}
|
| Letzte Änderung: 03.01.2018 | © Prof. Dr. Uwe Schmidt |
