Solution for Programming Exercise 12.4
This page contains a sample solution to one of the exercises from Introduction to Programming Using Java.
Exercise 12.4:
In previous exercise, you used a thread pool and a queue of tasks to find the integer in the range 1 to 100000 that has the largest number of divisors. Subsection 12.3.4 discusses a higher-level approach that uses an ExecutorService. Write one more program to solve the problem, this time using an ExecutorService and Futures. The program should still break up the computation into a fairly large number of fairly small tasks, and it should still print out the largest number of divisors and the integer that has that number of divisors.
(There is yet another way to solve the same problem: the stream API from Section 10.6. My solution using the stream API, however, uses an aspect of the stream API that I did not cover: the interface Optional<T>. My solution of this exercise also discusses how to use streams to solve the problem.)
My solution to Exercise 12.3 used nested classes Task and Result to represent one of the subtasks in the problem and the result from a subclass. For this problem, we want to submit the tasks to an ExecutorService, so we need tasks that implement the Callable interface. The tasks compute outputs of type Result, so in fact, Task implements Callable<Result>. Here are the two classes, with changes to Task shown in red:
/**
* A class to represent the result from one task. The
* result consists of the maximum number of divisors in
* the range of integers assigned to that task, and the
* integer in the range that gave the maximum number of
* divisors.
*/
private static class Result {
int maxDivisorFromTask; // Maximum number of divisors found.
int intWithMaxFromTask; // Which integer gave that maximum number.
Result(int maxDivisors, int whichInt) {
maxDivisorFromTask = maxDivisors;
intWithMaxFromTask = whichInt;
}
}
/**
* A class to represent the task of finding the number in
* a given range of integers that has the largest number of
* divisors. The range is specified in the constructor.
* The task is executed when the call() method is
* called. At the end of the call() method, a Result
* object is created to represent the results from this
* task, and the result object is returned as the value
* of call().
*/
private static class Task implements Callable<Result>{
int min, max; // Start and end of the range of integers for this task.
Task(int min, int max) {
this.min = min;
this.max = max;
}
public Result call() {
int maxDivisors = 0;
int whichInt = 0;
for (int i = min; i < max; i++) {
int divisors = countDivisors(i);
if (divisors > maxDivisors) {
maxDivisors = divisors;
whichInt = i;
}
}
return new Result(maxDivisors,whichInt);
}
}
Following the example of ThreadTest4.java, we can perform the computation by creating an ExecutorService and submitting the tasks to it. When a task it submitted, an object of type Future<Result> is returned, representing the future result of the computation. The program needs to save those Futures in a list:
ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads);
ArrayList<Future<Result>> results = new ArrayList<>();
int numberOfTasks = (MAX + 999) / 1000;
for (int i = 0; i < numberOfTasks; i++) {
int start = i*1000 + 1;
int end = (i+1)*1000;
if (end > MAX)
end = MAX;
//System.out.println(start + " " + end); // for testing
Future<Result> res = executor.submit( new Task(start,end) );
results.add(res);
}
After submitting all the tasks, the program can get the results from the Futures. Note that calling a Future's get() method will block until the result is actually available (or an error occurs):
int maxDivisorCount = 0; // Over maximum found by any task.
int intWithMaxDivisorCount = 0; // Which integer gave that maximum?
for (Future<Result> res : results) {
try {
Result result = res.get();
if (result.maxDivisorFromTask > maxDivisorCount) { // new maximum.
maxDivisorCount = result.maxDivisorFromTask;
intWithMaxDivisorCount = result.intWithMaxFromTask;
}
}
catch (Exception e) {
System.out.println("An unexpected error occurred! Error:");
System.out.println(e);
System.exit(1);
}
}
In my testing, this version of the solution to the divisors program took about the same amount of time as the solution that implemented thread pools directly.
As a final note, executor.shutdown() needs to be called at some point after all the tasks have been submitted. Otherwise, the program won't actually end when main() finishes, since the non-daemon threads in the executor's thread pool will still exist. Alternatively, System.exit() could be called to definitively end the program.
There is yet another way to solve the "count divisors" problem: using the stream API. The same Task and Result classes that were used in the ExectorService approach can also be used with streams (although Task no longer needs to implement Callable).
The algorithm goes like this: Create an ArrayList<Task> containing all of the tasks that make up the problem. Obtain a parallelStream from that list. Apply a mapping operation to the stream, where each task is mapped to the result that is output from that task. (This is where all of the work of counting is done.) This converts the stream of Tasks into a stream of Results. Finally, we need to find the result with the largest number of divisors. That can be done by applying the max() operator to the stream. The max() operator takes a parameter that is the Comparator that it will use to compare two objects from the stream. So, starting from the ArrayList, tasks, the computation can be done as follows:
tasks.parallelStream()
.map( task -> task.call() )
.max( (r1,r2) -> r1.maxDivisorFromTask - r2.maxDivisorFromTask );
This computation returns the result that contains the largest maxDivisorFromTask. Unfortunately, it returns the answer as a value of type Optional<Result>. An Optional represents a value that might or might not exists. If opt is an Optional, then the boolean-valued function opt.isPresent() is used to test whether the value exists. The actual value can be retrieved by calling opt.get(), which will throw an exception if the value does not exist. The reason max() returns an Optional is that an empty stream does not have a maximum, so no value will be present in that case. For this problem, we know that the maximum exists, so we can call get() without checking whether the value is present. Here is a main() program that uses the stream API to solve the divisors problem:
public static void main(String[] args) {
long startTime = System.currentTimeMillis();
ArrayList<Task> tasks = new ArrayList<>();
int numberOfTasks = (MAX + 999) / 1000;
for (int i = 0; i < numberOfTasks; i++) {
int start = i*1000 + 1;
int end = (i+1)*1000;
if (end > MAX)
end = MAX;
tasks.add( new Task(start,end) );
}
Optional<Result> max;
max = tasks.parallelStream()
.map( task -> task.call() )
.max( (r1,r2) -> r1.maxDivisorFromTask - r2.maxDivisorFromTask);
Result bestRes = max.get();
long elapsedTime = System.currentTimeMillis() - startTime;
System.out.println("\nThe largest number of divisors " +
"for numbers between 1 and " + MAX +
" is " + bestRes.maxDivisorFromTask);
System.out.println("An integer with that many divisors is " +
bestRes.intWithMaxFromTask);
System.out.println("Total elapsed time: " +
(elapsedTime/1000.0) + " seconds.\n");
}
In my testing, this version of the solution took about 12% more time than the ExecutorService solution or the version that implemented a thread pool directly.
Here is a solution, with changes from the solution to the previous exercise shown in red:
import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.Callable; import java.util.concurrent.Future; import java.util.ArrayList; import java.util.Scanner; /** * This program finds the number in the range 1 to some maximum that has the * largest number of divisors. It prints that number and the number of divisors * that it has. Note that there might be several numbers that have the maximum * number of divisors. Only one of them is output. * * The program's work is divided into a large number of tasks that are executed * by an ExecutorService. Each task consists of finding the maximum number of * divisors among a sequence of 1000 integers. */ public class CountDivisorsUsingExecutor { /** * The upper limit of the range of integers that is to be tested. * (This must be a fairly large multiple of 1000 for the thread * pool load-balancing strategy to be effective.) */ private final static int MAX = 100000; /** * A class to represent the result from one task. The * result consists of the maximum number of divisors in * the range of integers assigned to that task, and the * integer in the range that gave the maximum number of * divisors. */ private static class Result { int maxDivisorFromTask; // Maximum number of divisors found. int intWithMaxFromTask; // Which integer gave that maximum number. Result(int maxDivisors, int whichInt) { maxDivisorFromTask = maxDivisors; intWithMaxFromTask = whichInt; } } /** * A class to represent the task of finding the number in * a given range of integers that has the largest number of * divisors. The range is specified in the constructor. * The task is executed when the call() method is * called. At the end of the call() method, a Result * object is created to represent the results from this * task, and the result object is returned as the value * of call(). */ private static class Task implements Callable<Result>{ int min, max; // Start and end of the range of integers for this task. Task(int min, int max) { this.min = min; this.max = max; } public Result call() { int maxDivisors = 0; int whichInt = 0; for (int i = min; i < max; i++) { int divisors = countDivisors(i); if (divisors > maxDivisors) { maxDivisors = divisors; whichInt = i; } } return new Result(maxDivisors,whichInt); } } /** * Finds the number in the range 1 to MAX that has the largest number of * divisors, dividing the work into tasks that will be submitted to an * ExecutorService. The Futures that are returned when the tasks are * submitted are placed into an ArrayList. The results from those Futures * are combined to produce the final output. * @param numberOfThreads the number of threads to be used by the executor */ private static void countDivisorsWithExecutor(int numberOfThreads) { System.out.println("\nCounting divisors using " + numberOfThreads + " threads..."); /* Create the ExecutorService and an ArrayList to hold the Futures. */ long startTime = System.currentTimeMillis(); ExecutorService executor = Executors.newFixedThreadPool(numberOfThreads); ArrayList<Future<Result>> results = new ArrayList<>(); /* Create the tasks and add them to the executor. Each * task consists of a range of 1000 integers, so the number of * tasks is (MAX+999)/1000. (The "+999" gives the correct number * of tasks when MAX is not an exact multiple of 1000. The last * task in that case will consist of the last (MAX%1000)) ints. */ int numberOfTasks = (MAX + 999) / 1000; for (int i = 0; i < numberOfTasks; i++) { int start = i*1000 + 1; int end = (i+1)*1000; if (end > MAX) end = MAX; //System.out.println(start + " " + end); // for testing Future<Result> res = executor.submit( new Task(start,end) ); results.add(res); } /* As the executor executes the tasks, results become available * in the Futures that are stored in the ArrayList. Get the * results and combine them to produce the final output. * Note that each call to res.get() blocks, if necessary, * until the result is available. */ int maxDivisorCount = 0; // Over maximum found by any task. int intWithMaxDivisorCount = 0; // Which integer gave that maximum? for (Future<Result> res : results) { try { Result result = res.get(); if (result.maxDivisorFromTask > maxDivisorCount) { // new maximum. maxDivisorCount = result.maxDivisorFromTask; intWithMaxDivisorCount = result.intWithMaxFromTask; } } catch (Exception e) { System.out.println("An unexpected error occurred! Error:"); System.out.println(e); System.exit(1); } } /* Report the results. */ long elapsedTime = System.currentTimeMillis() - startTime; System.out.println("\nThe largest number of divisors " + "for numbers between 1 and " + MAX + " is " + maxDivisorCount); System.out.println("An integer with that many divisors is " + intWithMaxDivisorCount); System.out.println("Total elapsed time: " + (elapsedTime/1000.0) + " seconds.\n"); executor.shutdown(); // Needed since otherwise the threads in the // ExecutorService will stop the Java Virtual // Machine from shutting down normally. } // end countDivisorsWithExecutor() /** * The main() routine just gets the number of threads from the user and * calls countDivisorsWithThreads() to do the actual work. */ public static void main(String[] args) { Scanner in = new Scanner(System.in); int numberOfThreads = 0; while (numberOfThreads < 1 || numberOfThreads > 10) { System.out.print("How many threads do you want to use (1 to 10) ? "); numberOfThreads = in.nextInt(); if (numberOfThreads < 1 || numberOfThreads > 10) System.out.println("Please enter a number from 1 to 10 !"); } countDivisorsWithExecutor(numberOfThreads); } /** * Finds the number of divisors of the integer N. Note that this method does * the counting in a stupid way, since it tests every integer in the range * 1 to N to see whether it evenly divides N. */ private static int countDivisors(int N) { int count = 0; for (int i = 1; i <= N ; i++) { if ( N % i == 0 ) count ++; } return count; } } // end CountDivisorsUsingExecutor