FileDocCategorySizeDatePackage
TernarySearchTreeTest.javaAPI DocExample22493Tue Feb 29 20:37:58 GMT 2000tuning.struct

TernarySearchTreeTest

public class TernarySearchTreeTest extends Object

Fields Summary
Constructors Summary
Methods Summary
static voidUnsynchronizedTreeMap()

    long t1 = System.currentTimeMillis();
    TreeMap h = new TreeMap();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TreeMap", false, false, t1, t2, t3);

    o=null;h=null;System.gc();
static voidUnsynchronizedhashtable()

    long t1 = System.currentTimeMillis();
    HashMap h = new HashMap();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("HashMap", false, false, t1, t2, t3);

    o=null;h=null;System.gc();
public static intcomparisonSearch(java.lang.String[] arr, java.lang.String elem, int fromIndex, int toIndex)
Searches for an occurence of the given argument, between fromIndex and toIndex inclusive in an array pre-sorted according to the ordering given by the Comparator using an iterative binary search algorithm.

Tests for equality using the Comparator object passed, finding objects equal if the Comparator.compare(Object,Object) method returns 0.

If the object is not in the array, the return code gives the position into which the element should be inserted to retain the ordering within the array according to the formula insertionIndex = -(return code) - 1

If the array is not pre-sorted accrding to the given Comparator, the results are undefined (including the possibility of infinitely looping).

If elem or any of the elements of the array are null, then use the Comparator needs to support the comparison against null objects.

param
arr the array being searched.
param
elem the object being searched for.
param
fromIndex the index to start searching from.
param
toIndex the index to finish searching on.
param
comparator the Comparator object which provides ordered comparisons on the elements.
return
the index of an occurrence of the object argument in the array between position fromIndex and toIndex inclusive; returns -(insertionIndex + 1) if the object is not found. If more than one index is valid (because of a series of objects equal to the elem), then the index returned can be that of any of the equal objects.
exception
ArrayIndexOutOfBoundsException if either index is outside the array
see
java.util.Comparator

	int mid,cmp;
	while (fromIndex <= toIndex)
	{
		mid =(fromIndex + toIndex)/2;
		if ( (cmp = arr[mid].compareTo(elem)) < 0)
			fromIndex = mid + 1;
		else if (cmp > 0)
			toIndex = mid - 1;
		else
			return mid;
	}
	return -(fromIndex + 1);
public static voidfind()

find("s");
public static voidfind(java.lang.String s)


    long t1 = System.currentTimeMillis();
  String[] arr = new String[Dict.DICT.length];
  System.arraycopy(Dict.DICT, 0, arr, 0, Dict.DICT.length);
  quicksort_comparator(arr, 0, arr.length-1);
    t1 = System.currentTimeMillis() - t1;

    long t2 = System.currentTimeMillis();
  int startIdx = -(comparisonSearch(arr, s+((char) 0), 0, arr.length-1)+1);
  int endIdx = -(comparisonSearch(arr, s+ ((char) 255), 0, arr.length-1)+1);
if (startIdx < 0 || endIdx < 0)throw new RuntimeException ("no");
  Object[] objs = new Object[endIdx-startIdx];
  for (int i = startIdx ; i < endIdx; i++)
    objs[i-startIdx] = arr[i];
    t2 = System.currentTimeMillis() - t2;
  System.out.println("Create & search & num items found for sorted\t" + t1 + "\t" + t2 + " " + objs.length);
//System.exit(0);
public static voidfind1()

find1("s");
public static voidfind1(java.lang.String s)


    long t1 = System.currentTimeMillis();
    t1 = System.currentTimeMillis() - t1;

    Hashtable h = new Hashtable(2*Dict.DICT.length-1);
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);

    long t2 = System.currentTimeMillis();
    Vector v = new Vector();
    java.util.Enumeration e = h.keys();
    String s1;
    for(;e.hasMoreElements();) {
      s1=(String)e.nextElement();
      if(s1.startsWith(s)){v.addElement(s);}
    }
    Object[] objs = new Object[v.size()];
    for(int i=v.size()-1;i>=0;i--)
	objs[i]=h.get(v.elementAt(i));
    t2 = System.currentTimeMillis() - t2;
  System.out.println("1.Create & search & num items found for sorted\t" + t1 + "\t" + t2 + " " + objs.length);
//System.exit(0);
static voidhashtable()

    long t1 = System.currentTimeMillis();
    Hashtable h = new Hashtable();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("Hashtable", false, false, t1, t2, t3);

    o=null;h=null;System.gc();
public static voidmain(java.lang.String[] args)

    try
    {
      Dict.initialize(true);
find1();
      TernarySearchTree6 h = new TernarySearchTree6();
      for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
        h.put(Dict.RAND_DICT[i], Boolean.TRUE);
      for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
	if ( h.get(Dict.RAND_DICT[i]) != Boolean.TRUE ) throw new Exception(""+i);
      System.out.println(h.nodeCount());
      h.release(); h=null; System.gc();
      TernarySearchTree3.dummy();

      randternarySearchTree2();

      randhashtable();
      hashtable();
      sizedrandhashtable();
      sizedhashtable();

      randUnsynchronizedhashtable();
      Unsynchronizedhashtable();
      sizedrandUnsynchronizedhashtable();
      sizedUnsynchronizedhashtable();

      randUnsynchronizedTreeMap();
      UnsynchronizedTreeMap();

      randternarySearchTree0();
      ternarySearchTree0();

      randternarySearchTree1();
      ternarySearchTree1();

      randternarySearchTree2();
      ternarySearchTree2();

      randternarySearchTree3();
      ternarySearchTree3();

      ternarySearchTree4();
      randternarySearchTree4();

      randternarySearchTree5();
      ternarySearchTree5();

      ternarySearchTree5();
      randternarySearchTree5();

      randternarySearchTree4();
      ternarySearchTree4();

      ternarySearchTree3();
      randternarySearchTree3();

      ternarySearchTree2();
      randternarySearchTree2();

      ternarySearchTree1();
      randternarySearchTree1();

      ternarySearchTree0();
      randternarySearchTree0();

      randUnsynchronizedTreeMap();
      UnsynchronizedTreeMap();

      sizedUnsynchronizedhashtable();
      sizedrandUnsynchronizedhashtable();
      Unsynchronizedhashtable();
      randUnsynchronizedhashtable();

      sizedhashtable();
      sizedrandhashtable();
      hashtable();
      randhashtable();
    }
    catch(Exception e){e.printStackTrace();}
private static voidquicksort_comparator(java.lang.String[] arr, int lo, int hi)

	if( lo >= hi ) 
		return;

	int mid = ( lo + hi ) / 2;
	String tmp;
	String middle = arr[ mid ];

	if( arr[ lo ].compareTo(middle) > 0 )
	{
		arr[ mid ] = arr[ lo ];
		arr[ lo ] = middle;
		middle = arr[ mid ];
	}

	if( middle.compareTo(arr[ hi ]) > 0)
	{
		arr[ mid ] = arr[ hi ];
		arr[ hi ] = middle;
		middle = arr[ mid ];

		if( arr[ lo ].compareTo(middle) > 0)
		{
			arr[ mid ] = arr[ lo ];
			arr[ lo ] = middle;
			middle = arr[ mid ];
		}
	}

	int left = lo + 1;
	int right = hi - 1;

	if( left >= right ) 
		return;

	for( ;; ) 
	{
		while( arr[ right ].compareTo(middle ) > 0)
		{
			right--;
		}

		while( left < right && arr[ left ].compareTo(middle ) <= 0)
		{
			left++;
		}

		if( left < right )
		{
			tmp = arr[ left ];
			arr[ left ] = arr[ right ];
			arr[ right ] = tmp;
			right--;
		}
		else
		{
			break;
		}
	}

	quicksort_comparator(arr, lo, left);
	quicksort_comparator(arr, left + 1, hi);
static voidrandUnsynchronizedTreeMap()

    long t1 = System.currentTimeMillis();
    TreeMap h = new TreeMap();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TreeMap", true, false, t1, t2, t3);

    o=null;h=null;System.gc();
static voidrandUnsynchronizedhashtable()

    long t1 = System.currentTimeMillis();
    HashMap h = new HashMap();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("HashMap", true, false, t1, t2, t3);

    o=null;h=null;System.gc();
static voidrandhashtable()

    long t1 = System.currentTimeMillis();
    Hashtable h = new Hashtable();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("Hashtable", true, false, t1, t2, t3);

    o=null;h=null;System.gc();
static voidrandternarySearchTree0()

    long t1 = System.currentTimeMillis();
    TernarySearchTree0 h = new TernarySearchTree0();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree0", true, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidrandternarySearchTree1()

    long t1 = System.currentTimeMillis();
    TernarySearchTree1 h = new TernarySearchTree1();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree1", true, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidrandternarySearchTree2()

    long t1 = System.currentTimeMillis();
    TernarySearchTree2 h = new TernarySearchTree2();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree2", true, false, t1, t2, t3);
    h.release();o=null;h=null;System.gc();
static voidrandternarySearchTree3()

    long t1 = System.currentTimeMillis();
    TernarySearchTree3 h = new TernarySearchTree3();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree3", true, false, t1, t2, t3);
    h.release();o=null;h=null;System.gc();
static voidrandternarySearchTree4()

    long t1 = System.currentTimeMillis();
    TernarySearchTree4 h = new TernarySearchTree4();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree4", true, false, t1, t2, t3);
    h.release();o=null;h=null;System.gc();
static voidrandternarySearchTree5()

    long t1 = System.currentTimeMillis();
    TernarySearchTree5 h = new TernarySearchTree5();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree5", true, false, t1, t2, t3);
    h.release();o=null;h=null;System.gc();
static voidreport(java.lang.String type, boolean rand, boolean sized, long create, long update, long access)

    System.out.print("cr, up, ac ");
    System.out.print(rand ? "rnd " : "    ");
    System.out.print(sized ? "szd " : "    ");
    for (int i = 25-type.length(); i>=0;i--)
      System.out.print(" ");
    System.out.print(type);
    System.out.print(" is ");
    System.out.print(create);
    System.out.print("\t");
    System.out.print(update);
    System.out.print("\t");
    System.out.println(access);
static voidsizedUnsynchronizedhashtable()

    long t1 = System.currentTimeMillis();
    HashMap h = new HashMap(2*Dict.DICT.length-1);
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("HashMap", false, true, t1, t2, t3);

    o=null;h=null;System.gc();
static voidsizedhashtable()

    long t1 = System.currentTimeMillis();
    Hashtable h = new Hashtable(2*Dict.DICT.length-1);
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("Hashtable", false, true, t1, t2, t3);

    o=null;h=null;System.gc();
static voidsizedrandUnsynchronizedhashtable()

    long t1 = System.currentTimeMillis();
    HashMap h = new HashMap(2*Dict.DICT.length-1);
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("HashMap", true, true, t1, t2, t3);

    o=null;h=null;System.gc();
static voidsizedrandhashtable()

    long t1 = System.currentTimeMillis();
    Hashtable h = new Hashtable(2*Dict.DICT.length-1);
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      h.put(Dict.RAND_DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.RAND_DICT.length-1; i>=0; i--)
      o = h.get(Dict.RAND_DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("Hashtable", true, true, t1, t2, t3);

    o=null;h=null;System.gc();
static voidternarySearchTree0()

    long t1 = System.currentTimeMillis();
    TernarySearchTree0 h = new TernarySearchTree0();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree0", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidternarySearchTree1()

    long t1 = System.currentTimeMillis();
    TernarySearchTree1 h = new TernarySearchTree1();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree1", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidternarySearchTree2()

    long t1 = System.currentTimeMillis();
    TernarySearchTree2 h = new TernarySearchTree2();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree2", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidternarySearchTree3()

    long t1 = System.currentTimeMillis();
    TernarySearchTree3 h = new TernarySearchTree3();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree3", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidternarySearchTree4()

    long t1 = System.currentTimeMillis();
    TernarySearchTree4 h = new TernarySearchTree4();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree4", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();
static voidternarySearchTree5()

    long t1 = System.currentTimeMillis();
    TernarySearchTree5 h = new TernarySearchTree5();
    t1 = System.currentTimeMillis() -  t1;

    long t2 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      h.put(Dict.DICT[i], Boolean.TRUE);
    t2 = System.currentTimeMillis() -  t2;

    Object o;
    long t3 = System.currentTimeMillis();
    for (int i = Dict.DICT.length-1; i>=0; i--)
      o = h.get(Dict.DICT[i]);
    t3 = System.currentTimeMillis() -  t3;

    report("TernarySearchTree5", false, false, t1, t2, t3);

    h.release();o=null;h=null;System.gc();