Pastebin launched a little side project called VERYVIRAL.com, check it out ;-) Want more features on Pastebin? Sign Up, it's FREE!
Guest

TrieHard vs. Patricia Trie

By: ClickerMonkey on Jul 29th, 2013  |  syntax: Java  |  size: 5.00 KB  |  views: 40  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. import org.ardverk.collection.PatriciaTrie;
  2. import org.ardverk.collection.StringKeyAnalyzer;
  3. import org.junit.Test;
  4. import org.magnos.trie.Trie;
  5.  
  6.  
  7. public class CompareTries
  8. {
  9.  
  10.    public static String[] KEYS = {
  11.       "apple", "aardvark", "application", "aptitude", "apply", "ample", "abbey",
  12.       "barney", "cotton", "carnival", "dirty", "dirtskank", "dirtyman", "dirtpoo",
  13.       "dirtshirt", "echo", "ego", "purple", "zealot", "zebra"
  14.    };
  15.    
  16.    public static String[] QUERIES = {
  17.       "ap", "app", "a", "a", "b", "z", "p", "pur", "appl", "apt", "ab", "b",
  18.       "c", "ca", "co", "cod", "bar", "bart", "di", "dirt", "dirts", "d", "f",
  19.       "e", "g", "h", "i", "j", "k", "ze", "carnivalride"
  20.    };
  21.  
  22.    @Test
  23.    public void comparePut()
  24.    {
  25.       Trie<String, Integer> t0;
  26.       PatriciaTrie<String, Integer> t1;
  27.  
  28.       for (int i = 0; i < 100000; i++)
  29.       {
  30.  
  31.          t0 = Trie.forStrings();
  32.          t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );
  33.  
  34.          for (int k = 0; k < KEYS.length; k++)
  35.          {
  36.             t0.put( KEYS[k], Integer.valueOf( k ) );
  37.          }
  38.  
  39.          for (int k = 0; k < KEYS.length; k++)
  40.          {
  41.             t1.put( KEYS[k], Integer.valueOf( k ) );
  42.          }
  43.       }
  44.  
  45.       int iterations = 10000;
  46.       long total0 = 0;
  47.       long total1 = 0;
  48.       long min0 = Long.MAX_VALUE;
  49.       long max0 = Long.MIN_VALUE;
  50.       long min1 = Long.MAX_VALUE;
  51.       long max1 = Long.MIN_VALUE;
  52.  
  53.       for (int i = 0; i < iterations; i++)
  54.       {
  55.  
  56.          t0 = Trie.forStrings();
  57.          t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );
  58.  
  59.          long time0 = System.nanoTime();
  60.          for (int k = 0; k < KEYS.length; k++)
  61.          {
  62.             t0.put( KEYS[k], Integer.valueOf( k ) );
  63.          }
  64.          long time1 = System.nanoTime();
  65.          for (int k = 0; k < KEYS.length; k++)
  66.          {
  67.             t1.put( KEYS[k], Integer.valueOf( k ) );
  68.          }
  69.          long time2 = System.nanoTime();
  70.  
  71.          long duration0 = (time1 - time0);
  72.          long duration1 = (time2 - time1);
  73.  
  74.          total0 += duration0;
  75.          total1 += duration1;
  76.          min0 = Math.min( min0, duration0 );
  77.          max0 = Math.max( max0, duration0 );
  78.          min1 = Math.min( min1, duration1 );
  79.          max1 = Math.max( max1, duration1 );
  80.       }
  81.  
  82.       System.out.println( "COMPARE PUT" );
  83.       System.out.println( "Mine:" );
  84.       System.out.format( "\tAvg: %.9f s\n", total0 * 0.000000001 / iterations );
  85.       System.out.format( "\tMin: %.9f s\n", min0 * 0.000000001 );
  86.       System.out.format( "\tMax: %.9f s\n", max0 * 0.000000001 );
  87.  
  88.       System.out.println( "Patricia:" );
  89.       System.out.format( "\tAvg: %.9f s\n", total1 * 0.000000001 / iterations );
  90.       System.out.format( "\tMin: %.9f s\n", min1 * 0.000000001 );
  91.       System.out.format( "\tMax: %.9f s\n", max1 * 0.000000001 );
  92.    }
  93.  
  94.    @Test
  95.    public void compareGet()
  96.    {
  97.       Trie<String, Integer> t0 = Trie.forStrings();
  98.       PatriciaTrie<String, Integer> t1 = new PatriciaTrie<>( StringKeyAnalyzer.CHAR );;
  99.  
  100.       for (int k = 0; k < KEYS.length; k++)
  101.       {
  102.          t0.put( KEYS[k], Integer.valueOf( k ) );
  103.          t1.put( KEYS[k], Integer.valueOf( k ) );
  104.       }
  105.      
  106.       for (int i = 0; i < 100000; i++)
  107.       {
  108.          for (int k = 0; k < QUERIES.length; k++)
  109.          {
  110.             t0.get( QUERIES[k] );
  111.          }
  112.          
  113.          for (int k = 0; k < QUERIES.length; k++)
  114.          {
  115.             t1.get( QUERIES[k] );
  116.          }
  117.       }
  118.  
  119.       int iterations = 10000;
  120.       long total0 = 0;
  121.       long total1 = 0;
  122.       long min0 = Long.MAX_VALUE;
  123.       long max0 = Long.MIN_VALUE;
  124.       long min1 = Long.MAX_VALUE;
  125.       long max1 = Long.MIN_VALUE;
  126.  
  127.       for (int i = 0; i < iterations; i++)
  128.       {
  129.          long time0 = System.nanoTime();
  130.          for (int k = 0; k < QUERIES.length; k++)
  131.          {
  132.             t0.get( QUERIES[k] );
  133.          }
  134.          long time1 = System.nanoTime();
  135.          for (int k = 0; k < QUERIES.length; k++)
  136.          {
  137.             t1.get( QUERIES[k] );
  138.          }
  139.          long time2 = System.nanoTime();
  140.  
  141.          long duration0 = (time1 - time0);
  142.          long duration1 = (time2 - time1);
  143.  
  144.          total0 += duration0;
  145.          total1 += duration1;
  146.          min0 = Math.min( min0, duration0 );
  147.          max0 = Math.max( max0, duration0 );
  148.          min1 = Math.min( min1, duration1 );
  149.          max1 = Math.max( max1, duration1 );
  150.       }
  151.  
  152.       System.out.println( "COMPARE GET" );
  153.       System.out.println( "Mine:" );
  154.       System.out.format( "\tAvg: %.9f s\n", total0 * 0.000000001 / iterations );
  155.       System.out.format( "\tMin: %.9f s\n", min0 * 0.000000001 );
  156.       System.out.format( "\tMax: %.9f s\n", max0 * 0.000000001 );
  157.  
  158.       System.out.println( "Patricia:" );
  159.       System.out.format( "\tAvg: %.9f s\n", total1 * 0.000000001 / iterations );
  160.       System.out.format( "\tMin: %.9f s\n", min1 * 0.000000001 );
  161.       System.out.format( "\tMax: %.9f s\n", max1 * 0.000000001 );
  162.    }
  163.  
  164. }