Profiling Search Algorithms

Introduction

Your goal in this lab is to learn about the linear and binary search algorithms and profile these algorithms to measure their cost. You will do this by writing a utility that counts the number of comparisons made by both search algorithms and produces a report of their best, worst, and average cases.

SearchResult

In the context of this activity, a search result is a tuple of three values: an item being searched for, a boolean indicating whether the item was found, and a number of comparisons that the search needed to determine its answer. Your first task is to make a class that encapsulates this 3-tuple. It has no setters, only getters. Such a class can be cranked out in moments using an IDE like IntelliJ or Eclipse:

• Create a new class named SearchResult that takes a type parameter T. Use the extends keyword to ensure that the type argument will implement the Comparable interface.
• Declare three instance variables. Name them item, isFound, and comparisonCount. The item variable should be of type T.
• If using Eclipse
  • Under the Source menu, select Generate Constructor Using Fields…. Click Generate.
  • Under the Source menu, select Generate Getters and Setters…. Click Select Getters, then Generate.
• If using IntelliJ
  • Click Code / Generate and select Constructor. Autogenerate a constructor that initializes the instance variables.
  • Click Code / Generate and select Getters. Autogenerate getters for the instance variables.
• Your resulting getters should be named getItem, isFound and getComparisonCount.
• Write a toString method that returns a space-separated concatenation of the three instance variables. For example: benzene false 62.

That’s all there is to this class. Most of the work will be done in SearchProfiler.

SearchProfiler

The SearchProfiler class must have a type parameter T. Again, use the extends keyword to ensure that the type argument will implement the Comparable interface.

SearchProfiler must have the following public interface. As you implement this class test each method before moving on the the next one.

• A constructor that accepts an array of T. Do not modify the array. Assume it is in an appropriate order for the searching that will be profiled.
• linearSearch – This method accepts an item of type T. It performs a linear search and returns a SearchResult whose three fields are set accordingly. For the comparison count, count only the number of times equals or compareTo is called. Don’t call these methods any more than necessary. Test that this method works using your own main method before moving on.
• binarySearch – This method accepts an item of type T. It behaves just like linearSearch, but it performs a binary search. Test using your own main.
• profileAllLinear – This method linear-searches for every element in the array and returns an ArrayList of the elements’ search results. Test!
• profileAllBinary – This method binary-searches for every element in the array and returns an ArrayList of the elements’ search results. Test!

• printSummary – This static method accepts an ArrayList of search results and prints out a report in this format:

  Worst: 8
  Best: 1
  Average: 4.5

  This particular report was generated by profiling the linear search of the array {10, 17, 20, 25, 99, 108, 213, 252}. Output the average number of comparisons with 1 digit after the decimal point. End each of the three lines with a linebreak, but do so in platform-independent way. Don’t hardcode \n or \r\n. This can be accomplished by using println or by using %n in a format string. Test!

  Remember that static methods don’t see the generic type of a class:

  public class Effect<T> {
    // This method fails to compile. T isn't visible to static methods.
    public static void fade(T option) { /* ... */ }
  }

  Instead, a static method is given its own generic type through this different syntax:

  public class Effect<T> {
    public static <T> void fade(T option) { /* ... */ }
  }

  The second T is technically independent of the first one and could have been named something else, like U.

Your instructors are not providing the source code for JUnit tests in this lab. When your instructors provide tests, students often do not test code themselves and enter a frustrating game of trying to satisfy the grading machine. Please don’t do that. Test your code locally. Reason about its correctness. You should only submit to Gradescope after you are reasonably confident that your implementation is correct.

Experimentation

Once you are confident that your implementation is correct, add the following method to your SearchProfiler class or to a separate driver class:

  /**
   * Profile linear and binary search on large integer arrays.
   *
   * @param size Input size to test
   */
  public static void profileBoth(int size) {
    Integer[] numbers = new Integer[size];

    for (int i = 0; i < numbers.length; i++) {
      numbers[i] = i * 2;
    }

    SearchProfiler<Integer> sp = new SearchProfiler<>(numbers);

    System.out.printf("Results for Linear Search of %d items: %n", size);
    SearchProfiler.printSummary(sp.profileAllLinear());

    System.out.printf("%nResults for Binary Search of %d items: %n", size);
    SearchProfiler.printSummary(sp.profileAllBinary());
  }

BEFORE you run anything, take a minute to think about what you expect to see when this method is called as follows:

• profileBoth(1000);

Write your predictions in a file named experiments.txt, then run the test. Update the experiments.txt with the actual output as well as a sentence or two explaining the results.

Repeat this process for the following call:

• profileBoth(100000);

Predict the results, find the actual results, and explain any discrepancies.

Submission

Submit SearchResult.java, SearchProfiler.java and experiments.txt through GradeScope.

Acknowledgments

The original version of this lab was developed by Chris Johnson.