Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!aioe.org!eternal-september.org!feeder.eternal-september.org!.POSTED!not-for-mail
From: Gene Wirchenko <genew@ocis.net>
Newsgroups: comp.lang.java.programmer
Subject: Passing a Method Name to a Method, Redux
Date: Thu, 23 Jun 2011 16:03:34 -0700
Organization: A noiseless patient Spider
Lines: 256
Message-ID: <fpg7079ca2dtgipdphr8rm234kgmkd1t3l@4ax.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Injection-Info: mx04.eternal-september.org; posting-host="7Qrvczazr82YckO5XW8Vtw"; logging-data="15232"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/TPUl54lz2ln4gnZwP+cR1suCl3I1mWeM="
X-Newsreader: Forte Agent 4.2/32.1118
Cancel-Lock: sha1:wYlRWfcdGHAO5ck5sZ0Pb2QGZcg=
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:5610

Dear Java'ers:

     I have completed my benchmarking.  The code is below.  Note that
the difference in the bodies between ParseSequentialSearch(),
ParseBinarySearch(), and ParseTreesetSearch() is but one line.  I
really would have preferred not having to duplicate the code.

     Oddly, the timings have a LOT of noise in them.  In some runs, a
sequential search has out-performed a binary search.  Occasionally, a
sequential search has beaten both a binary search and a Treeset
search.  The times for sequential searching are only a bit worse than
for binary searching.  Treeset searching is about 20% faster.  Any
explanations?

     I had to kludge this:
          cIdent=""+CurrChar;
cIdent is a String, CurrChar is a char.
          cIdent=CurrChar;
does not compile.

     So how would you have written this benchmark?

***** Start of Code *****
// TimingTesting
// Timing Testing of Character Searching
// Last Modification: 2011-06-23



import java.util.*;



class TimingTesting
   {

   static String cParseString=
    "//identifier//IDENTIFIER//a_b_c abc123
4b5%$__dbl;one;two;three;END";

   static String IdentChars=
    "0123456789"+
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"+
    "_"+
    "abcdefghijklmnopqrstuvwxyz";     // sorted order!

   static SortedSet<Character> IdentCharsSet=new TreeSet<Character>();

   static int nRepetitions=1000000;



   static boolean SequentialSearch
    (
    char CurrChar
    )
      {
      boolean fFound=false;
      for (int i=0; i<IdentChars.length() && !fFound; i++)
         fFound=IdentChars.charAt(i)==CurrChar;
      return fFound;
      }



   static boolean BinarySearch
    (
    char CurrChar
    )
      {
      int xLow=0;
      int xHigh=IdentChars.length()-1;
      int xTry;
      boolean fFound=false;
      while (xLow<=xHigh)
         {
         xTry=(xLow+xHigh)/2;
         if (CurrChar==IdentChars.charAt(xTry))
            return true;
         if (CurrChar<IdentChars.charAt(xTry))
            xHigh=xTry-1;
         else
            xLow=xTry+1;
         }
      return false;
      }



   static boolean TreesetSearch
    (
    char CurrChar
    )
      {
      return IdentCharsSet.contains(CurrChar);
      }



   static void ParseSequentialSearch()
      {
      int xScan=0;
      boolean fBuildingIdent=false;
      boolean fInIdentChars;
      String cIdent="";     // fussy init
      while (xScan<cParseString.length())
         {
         char CurrChar=cParseString.charAt(xScan);
         fInIdentChars=SequentialSearch(CurrChar);
         if (SequentialSearch(CurrChar))     // different code
            if (fBuildingIdent)
               cIdent+=CurrChar;
            else
               {
               fBuildingIdent=true;
               cIdent=""+CurrChar;
               }
         else
            if (fBuildingIdent)
               {
               fBuildingIdent=false;
if (nRepetitions==1)
 System.out.println(cIdent);
               }
            else
               {}
         xScan++;
         }
      if (fBuildingIdent)
if (nRepetitions==1)
 System.out.println(cIdent);
      }



   static void ParseBinarySearch()
      {
      int xScan=0;
      boolean fBuildingIdent=false;
      boolean fInIdentChars;
      String cIdent="";     // fussy init
      while (xScan<cParseString.length())
         {
         char CurrChar=cParseString.charAt(xScan);
         fInIdentChars=SequentialSearch(CurrChar);
         if (SequentialSearch(CurrChar))     // different code
            if (fBuildingIdent)
               cIdent+=CurrChar;
            else
               {
               fBuildingIdent=true;
               cIdent=""+CurrChar;
               }
         else
            if (fBuildingIdent)
               {
               fBuildingIdent=false;
if (nRepetitions==1)
 System.out.println(cIdent);
               }
            else
               {}
         xScan++;
         }
      if (fBuildingIdent)
if (nRepetitions==1)
 System.out.println(cIdent);
      }



   static void ParseTreesetSearch()
      {
      int xScan=0;
      boolean fBuildingIdent=false;
      boolean fInIdentChars;
      String cIdent="";     // fussy init
      while (xScan<cParseString.length())
         {
         char CurrChar=cParseString.charAt(xScan);
         fInIdentChars=SequentialSearch(CurrChar);
         if (TreesetSearch(CurrChar))     // different code
            if (fBuildingIdent)
               cIdent+=CurrChar;
            else
               {
               fBuildingIdent=true;
               cIdent=""+CurrChar;
               }
         else
            if (fBuildingIdent)
               {
               fBuildingIdent=false;
if (nRepetitions==1)
 System.out.println(cIdent);
               }
            else
               {}
         xScan++;
         }
      if (fBuildingIdent)
if (nRepetitions==1)
 System.out.println(cIdent);
      }



   public static void main(String[] args)
      {
      int i;

      long StartTime;
      long EndTime;
      long Duration;

      System.out.println("Timing Testing of Character Searching");
      System.out.println();

      // Initialise Set.
      for (i=0; i<IdentChars.length(); i++)
         IdentCharsSet.add(IdentChars.charAt(i));

      // Character Sequential
      System.out.print("Character Sequential Search");
      StartTime=System.nanoTime();
      for (i=1; i<=nRepetitions; i++)
         ParseSequentialSearch();
      EndTime=System.nanoTime();
      Duration=EndTime-StartTime;
      System.out.println(" Duration="+Duration);

      // Character Binary Search
      System.out.print("Character Binary Search    ");
      StartTime=System.nanoTime();
      for (i=1; i<=nRepetitions; i++)
         ParseBinarySearch();
      EndTime=System.nanoTime();
      Duration=EndTime-StartTime;
      System.out.println(" Duration="+Duration);

      // Character Treeset
      System.out.print("Character Treeset Search   ");
      StartTime=System.nanoTime();
      for (i=1; i<=nRepetitions; i++)
         ParseTreesetSearch();
      EndTime=System.nanoTime();
      Duration=EndTime-StartTime;
      System.out.println(" Duration="+Duration);
      }

   }
***** End of Code *****

Sincerely,

Gene Wirchenko