Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import org.ardverk.collection.PatriciaTrie;
- import org.ardverk.collection.StringKeyAnalyzer;
- import org.junit.Test;
- import org.magnos.trie.Trie;
- public class CompareTries
- {
- public static String[] KEYS = {
- "apple", "aardvark", "application", "aptitude", "apply", "ample", "abbey",
- "barney", "cotton", "carnival", "dirty", "dirtskank", "dirtyman", "dirtpoo",
- "dirtshirt", "echo", "ego", "purple", "zealot", "zebra"
- };
- public static String[] QUERIES = {
- "ap", "app", "a", "a", "b", "z", "p", "pur", "appl", "apt", "ab", "b",
- "c", "ca", "co", "cod", "bar", "bart", "di", "dirt", "dirts", "d", "f",
- "e", "g", "h", "i", "j", "k", "ze", "carnivalride"
- };
- @Test
- public void comparePut()
- {
- Trie<String, Integer> t0;
- PatriciaTrie<String, Integer> t1;
- for (int i = 0; i < 100000; i++)
- {
- t0 = Trie.forStrings();
- t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );
- for (int k = 0; k < KEYS.length; k++)
- {
- t0.put( KEYS[k], Integer.valueOf( k ) );
- }
- for (int k = 0; k < KEYS.length; k++)
- {
- t1.put( KEYS[k], Integer.valueOf( k ) );
- }
- }
- int iterations = 10000;
- long total0 = 0;
- long total1 = 0;
- long min0 = Long.MAX_VALUE;
- long max0 = Long.MIN_VALUE;
- long min1 = Long.MAX_VALUE;
- long max1 = Long.MIN_VALUE;
- for (int i = 0; i < iterations; i++)
- {
- t0 = Trie.forStrings();
- t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );
- long time0 = System.nanoTime();
- for (int k = 0; k < KEYS.length; k++)
- {
- t0.put( KEYS[k], Integer.valueOf( k ) );
- }
- long time1 = System.nanoTime();
- for (int k = 0; k < KEYS.length; k++)
- {
- t1.put( KEYS[k], Integer.valueOf( k ) );
- }
- long time2 = System.nanoTime();
- long duration0 = (time1 - time0);
- long duration1 = (time2 - time1);
- total0 += duration0;
- total1 += duration1;
- min0 = Math.min( min0, duration0 );
- max0 = Math.max( max0, duration0 );
- min1 = Math.min( min1, duration1 );
- max1 = Math.max( max1, duration1 );
- }
- System.out.println( "COMPARE PUT" );
- System.out.println( "Mine:" );
- System.out.format( "\tAvg: %.9f s\n", total0 * 0.000000001 / iterations );
- System.out.format( "\tMin: %.9f s\n", min0 * 0.000000001 );
- System.out.format( "\tMax: %.9f s\n", max0 * 0.000000001 );
- System.out.println( "Patricia:" );
- System.out.format( "\tAvg: %.9f s\n", total1 * 0.000000001 / iterations );
- System.out.format( "\tMin: %.9f s\n", min1 * 0.000000001 );
- System.out.format( "\tMax: %.9f s\n", max1 * 0.000000001 );
- }
- @Test
- public void compareGet()
- {
- Trie<String, Integer> t0 = Trie.forStrings();
- PatriciaTrie<String, Integer> t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );;
- for (int k = 0; k < KEYS.length; k++)
- {
- t0.put( KEYS[k], Integer.valueOf( k ) );
- t1.put( KEYS[k], Integer.valueOf( k ) );
- }
- for (int i = 0; i < 100000; i++)
- {
- for (int k = 0; k < QUERIES.length; k++)
- {
- t0.get( QUERIES[k] );
- }
- for (int k = 0; k < QUERIES.length; k++)
- {
- t1.get( QUERIES[k] );
- }
- }
- int iterations = 10000;
- long total0 = 0;
- long total1 = 0;
- long min0 = Long.MAX_VALUE;
- long max0 = Long.MIN_VALUE;
- long min1 = Long.MAX_VALUE;
- long max1 = Long.MIN_VALUE;
- for (int i = 0; i < iterations; i++)
- {
- long time0 = System.nanoTime();
- for (int k = 0; k < QUERIES.length; k++)
- {
- t0.get( QUERIES[k] );
- }
- long time1 = System.nanoTime();
- for (int k = 0; k < QUERIES.length; k++)
- {
- t1.get( QUERIES[k] );
- }
- long time2 = System.nanoTime();
- long duration0 = (time1 - time0);
- long duration1 = (time2 - time1);
- total0 += duration0;
- total1 += duration1;
- min0 = Math.min( min0, duration0 );
- max0 = Math.max( max0, duration0 );
- min1 = Math.min( min1, duration1 );
- max1 = Math.max( max1, duration1 );
- }
- System.out.println( "COMPARE GET" );
- System.out.println( "Mine:" );
- System.out.format( "\tAvg: %.9f s\n", total0 * 0.000000001 / iterations );
- System.out.format( "\tMin: %.9f s\n", min0 * 0.000000001 );
- System.out.format( "\tMax: %.9f s\n", max0 * 0.000000001 );
- System.out.println( "Patricia:" );
- System.out.format( "\tAvg: %.9f s\n", total1 * 0.000000001 / iterations );
- System.out.format( "\tMin: %.9f s\n", min1 * 0.000000001 );
- System.out.format( "\tMax: %.9f s\n", max1 * 0.000000001 );
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement