1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.directory.server.core.avltree;
21
22
23 import java.io.File;
24 import java.io.FileInputStream;
25 import java.io.FileOutputStream;
26 import java.io.ObjectInputStream;
27 import java.io.ObjectOutputStream;
28 import java.util.Comparator;
29 import java.util.HashSet;
30 import java.util.Set;
31
32 import org.junit.AfterClass;
33 import org.junit.Before;
34 import org.junit.Test;
35 import org.slf4j.Logger;
36 import org.slf4j.LoggerFactory;
37
38
39
40
41
42
43
44
45
46 public class AvlTreePerfTest
47 {
48 AvlTree<Integer> tree;
49
50 static String tempDir = System.getProperty( "java.io.tmpdir" );
51
52 static File setSerialFile = new File( tempDir + File.separator + "hashset.ser" );
53 static File treeSerialFile = new File( tempDir + File.separator + "avltree.ser" );
54
55 Set<Integer> set;
56
57 long start, end;
58
59 int numKeys = 100000;
60
61 Comparator<Integer> comparator = new Comparator<Integer>()
62 {
63 public int compare( Integer i1, Integer i2 )
64 {
65 return i1.compareTo( i2 );
66 }
67
68 };
69
70 AvlTreeMarshaller<Integer> treeMarshaller = new AvlTreeMarshaller<Integer>( comparator, new IntegerKeyMarshaller() );
71
72 private final static Logger LOG = LoggerFactory.getLogger( AvlTreePerfTest.class );
73
74 @Before
75 public void createTree()
76 {
77 tree = new AvlTree<Integer>( new Comparator<Integer>()
78 {
79
80 public int compare( Integer i1, Integer i2 )
81 {
82 return i1.compareTo( i2 );
83 }
84
85 });
86
87 set = new HashSet<Integer>();
88
89 start = end = 0;
90 }
91
92
93 @AfterClass
94 public static void deleteFiles()
95 {
96 setSerialFile.delete();
97 treeSerialFile.delete();
98 }
99
100
101 @Test
102 public void testRBTreeInsertPerf()
103 {
104 start = System.nanoTime();
105
106 for( int i=0; i < numKeys; i++ )
107 {
108 set.add( i );
109 }
110
111 end = System.nanoTime();
112
113 LOG.info( "total time for inserting " + numKeys + " items into the RBTree-->" + getTime( start, end ) );
114
115 }
116
117
118 @Test
119 public void testRBTreeLookupPerf()
120 {
121 for( int i=0; i < numKeys; i++ )
122 {
123 set.add( i );
124 }
125
126 start = System.nanoTime();
127
128 set.contains( 70 );
129 set.contains( -1000 );
130 set.contains( 10 );
131 set.contains( 90 );
132 set.contains( 9999 );
133
134 end = System.nanoTime();
135
136 LOG.info( "total time took to read an item from set " + getTime( start, end ) ) ;
137 }
138
139
140 @Test
141 public void testRemoveFromRBTree()
142 {
143 for( int i=0; i < numKeys; i++ )
144 {
145 set.add( i );
146 }
147
148 start = System.nanoTime();
149
150 set.remove( 90 );
151 set.remove( 912 );
152 set.remove( -1 );
153 set.remove( 192 );
154
155 end = System.nanoTime();
156
157 LOG.info( "total time took to remove an item from set " + getTime( start, end ) ) ;
158
159 }
160
161
162 @Test
163 public void testAvlTreeInsertPerf()
164 {
165 start = System.nanoTime();
166
167 for( int i=0; i < numKeys; i++ )
168 {
169 tree.insert( i );
170 }
171
172 end = System.nanoTime();
173
174 LOG.info("total time for inserting " + numKeys + " items into the AVLTree-->" + getTime(start, end));
175 }
176
177
178 @Test
179 public void testAVLTreeLookupPerf()
180 {
181
182 for( int i=0; i < numKeys; i++ )
183 {
184 tree.insert( i );
185 }
186
187 start = System.nanoTime();
188
189 tree.find( 70 );
190 tree.find( -1000 );
191 tree.find( 10 );
192 tree.find( 90 );
193 tree.find( 9999 );
194
195 end = System.nanoTime();
196
197 LOG.info("total time took to read an item from tree " + getTime( start, end ) ) ;
198 }
199
200
201 @Test
202 public void testAVLTreeRemovePerf()
203 {
204 for( int i=0; i < numKeys; i++ )
205 {
206 tree.insert( i );
207 }
208
209 start = System.nanoTime();
210
211 tree.remove( 90 );
212 tree.remove( 912 );
213 tree.remove( -1 );
214 tree.remove( 192 );
215
216 end = System.nanoTime();
217
218 LOG.info("total time took to remove an item from AVLTree " + getTime( start, end ) ) ;
219
220 }
221
222
223 @Test
224 public void testRBTreeSerializationPerf() throws Exception
225 {
226 FileOutputStream fout = new FileOutputStream( setSerialFile );
227 ObjectOutputStream objOut = new ObjectOutputStream( fout );
228
229 Set<Integer> set = new HashSet<Integer>();
230
231 for( int i=0; i < numKeys; i++ )
232 {
233 set.add( i );
234 }
235
236 long start = System.nanoTime();
237
238 objOut.writeObject( set );
239 objOut.flush();
240 objOut.close();
241
242 long end = System.nanoTime();
243
244 LOG.info( "total time taken for serializing HashSet ->" + getTime( start, end ) );
245 }
246
247
248 @SuppressWarnings("unchecked")
249 @Test
250 public void testRBTreeDeserializationPerf() throws Exception
251 {
252
253 FileInputStream fin = new FileInputStream( setSerialFile );
254 ObjectInputStream objIn = new ObjectInputStream( fin );
255
256 start = System.nanoTime();
257
258 set = ( HashSet ) objIn.readObject();
259
260 end = System.nanoTime();
261
262 LOG.info("total time taken for reconstructing a serialized HashSet ->" + getTime( start, end ) );
263 }
264
265
266 @Test
267 public void testAVLTreeSerializationPerf() throws Exception
268 {
269
270 for( int i=0; i < numKeys; i++ )
271 {
272 tree.insert( i );
273 }
274
275 FileOutputStream fout = new FileOutputStream( treeSerialFile );
276
277 start = System.nanoTime();
278
279 fout.write( treeMarshaller.serialize( tree ) );
280 fout.flush();
281 fout.close();
282
283 end = System.nanoTime();
284
285 LOG.info( "total time taken for serializing AVLTree ->" + getTime( start, end ) );
286 }
287
288
289 @Test
290 public void testAVLTreeDeserializationPerf() throws Exception
291 {
292 FileInputStream fin = new FileInputStream( treeSerialFile );
293
294 byte data[] = new byte[ ( int ) treeSerialFile.length() ];
295
296 start = System.nanoTime();
297
298 fin.read(data);
299 tree = (AvlTree<Integer>) treeMarshaller.deserialize( data );
300
301 end = System.nanoTime();
302 LOG.info("total time taken for reconstructing a serialized AVLTree ->" + getTime( start, end ) );
303 }
304
305
306
307
308
309 private String getTime(long nanoStartTime, long nanoEndTime)
310 {
311 long temp = nanoEndTime - nanoStartTime;
312
313 if( temp == 0)
314 {
315 return "0 msec";
316 }
317
318 double d = temp / (1000 * 1000);
319
320 return String.valueOf( d ) + " msec";
321 }
322 }