Advertisement
Guest User

Binary search vs. linear search

a guest
May 6th, 2012
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.39 KB | None | 0 0
  1.     public void testSearches() {
  2.         try {
  3.             FileInputStream fstream = new FileInputStream("wordlist.txt");
  4.             DataInputStream in = new DataInputStream(fstream);
  5.             BufferedReader br = new BufferedReader(new InputStreamReader(in));
  6.             List<String> lines = new ArrayList<String>();
  7.             String strLine;
  8.             while ((strLine = br.readLine()) != null) {
  9.                 lines.add(strLine);
  10.             }
  11.             in.close();
  12.  
  13.             long[] totalBinaryResults = new long[3];
  14.             long[] totalLinearResults = new long[3];
  15.            
  16.             String[] wordlist = lines.toArray(new String[lines.size()]);
  17.    
  18.             int wordIndex = 1;
  19.             for (String word : wordlist) {
  20.                 long[] binaryResults = new long[3];
  21.                 long[] linearResults = new long[3];
  22.                 int bsResult = Search.binarySearch(wordlist, word, binaryResults);
  23.                 int lsResult = Search.linearSearch(wordlist, word, linearResults);
  24.                
  25.                 if( bsResult == -1 || lsResult == -1 ) {
  26.                     throw new RuntimeException("A word was not found, the test failed.");
  27.                 }
  28.                
  29.                 for (int i = 0; i < linearResults.length; i++) {
  30.                     totalBinaryResults[i] += binaryResults[i];
  31.                     totalLinearResults[i] += linearResults[i];
  32.                 }
  33.                 if( linearResults[0] < binaryResults[0] ) {
  34.                     System.out.println("Linear search was faster with index "+wordIndex+" ("+word+"): "+
  35.                                        linearResults[0]+" vs "+binaryResults[0]+" ns, or "+
  36.                                        linearResults[2]+" vs "+binaryResults[2]+" comparisons");
  37.                 }
  38.                 wordIndex++;
  39.             }
  40.                        
  41.             System.out.println("*** Binary ***");
  42.             System.out.println("Avg. time: "+totalBinaryResults[0]/(long)wordIndex);
  43.             System.out.println("Avg. comp: "+totalBinaryResults[2]/(long)wordIndex);
  44.            
  45.             System.out.println("*** Linear ***");
  46.             System.out.println("Avg. time: "+totalLinearResults[0]/(long)wordIndex);
  47.             System.out.println("Avg. comp: "+totalLinearResults[2]/(long)wordIndex);
  48.         } catch (Exception e) {
  49.             e.printStackTrace();
  50.         }
  51.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement