Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
JDK 8 CompletableFuture and Stream example to get the largest subarray sum.
package testlargestarray;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
/*
Problem: Given a list of random numbers, both positive and negative, find the
largest sum of a sublist.
Sample output - Late 2013 8-core MacBook Pro
Finding largest Array value Naively
Total execution time: 25599
Largest Sum: 3327
Number of searches 3126250
Finding largest Array value Naively via Futures
Total execution time: 7297
Largest Sum: 3327
Number of searches 3126250
Finding largest Array value
Total execution time: 6389
Largest Sum: 3327
Number of searches 764466
Finding largest Array value via Futures
Total execution time: 1805
Largest Sum: 3327
Number of searches 764466
*/
public class TestLargestArray {
public static void main(String[] args) throws Exception {
List<Integer> random
= Collections.unmodifiableList(
new Random()
.ints(-100, 101)
.limit(2500)
.boxed()
.collect(Collectors.toList())
);
rest();
findLargestNaive(random);
rest();
findLargestFutureNaive(random);
rest();
findLargest(random);
rest();
findLargestFuture(random);
}
private static long sum(List<Integer> list) {
return list.stream()
.map((i) -> (long) i)
.reduce(0L, (accumulator, _item)
-> Math.addExact(accumulator, _item));
}
private static void findLargestNaive(List<Integer> list) {
System.out.println("Finding largest Array value Naively");
long starttime = System.currentTimeMillis();
long resultValue = list.get(0); // seed value
long numTries = 0;
for (int start = 0; start < list.size(); start++) {
for (int end = start; end < list.size(); end++) {
List<Integer> tester = list.subList(start, end + 1);
long testresult = sum(tester);
numTries++;
if (testresult > resultValue) {
resultValue = testresult;
}
}
}
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
System.out.println("Largest Sum: " + resultValue);
System.out.println("Number of searches " + numTries);
}
private static void findLargestFutureNaive(List<Integer> list) throws Exception {
System.out.println("Finding largest Array value Naively via Futures");
long starttime = System.currentTimeMillis();
ForkJoinPool pool = ForkJoinPool.commonPool();
List<Future> futures = new ArrayList<>();
AtomicLong resultValue = new AtomicLong(list.get(0)); // seed value
LongAdder numTries = new LongAdder();
for (int start = 0; start < list.size(); start++) {
final int s = start;
futures.add(pool.submit(() -> {
for (int end = s; end < list.size(); end++) {
List<Integer> tester = list.subList(s, end + 1);
long testresult = sum(tester);
numTries.increment();
resultValue.accumulateAndGet(testresult, (x, y) -> {
return (x > y) ? x : y;
});
}
}));
}
for (Future f : futures) {
f.get();
}
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
System.out.println("Largest Sum: " + resultValue);
System.out.println("Number of searches " + numTries);
}
private static void findLargest(List<Integer> list) {
System.out.println("Finding largest Array value");
long starttime = System.currentTimeMillis();
long resultValue = list.stream().max(Integer::compare).get(); // seed value
long numTries = 0;
for (int start = 0; start < list.size(); start++) {
if (list.get(start) > 0) {
for (int end = start; end < list.size(); end++) {
if (list.get(end) > 0) {
List<Integer> tester = list.subList(start, end + 1); // sublist uses exclusive end
long testresult = sum(tester);
numTries++;
if (testresult > resultValue) {
resultValue = testresult;
}
}
}
}
}
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
System.out.println("Largest Sum: " + resultValue);
System.out.println("Number of searches " + numTries);
}
private static void findLargestFuture(List<Integer> list) throws Exception {
System.out.println("Finding largest Array value via Futures");
long starttime = System.currentTimeMillis();
List<Future<Long>> futures = new ArrayList<>();
LongAdder numTries = new LongAdder();
for (int start = 0; start < list.size(); start++) {
final int s = start;
if (list.get(s) > 0) {
futures.add(CompletableFuture.supplyAsync(() -> {
long maxresult = list.get(s); //seed
for (int end = s; end < list.size(); end++) {
long testvalue = list.get(end);
if (testvalue > 0) {
List<Integer> tester = list.subList(s, end + 1);
long testresult = sum(tester);
numTries.increment();
if (maxresult < testresult) {
maxresult = testresult;
}
} else if (testvalue > maxresult) {
maxresult = testvalue;
}
}
return maxresult;
}).exceptionally(ex -> {
if (ex.getCause() instanceof ArithmeticException) {
return Long.MAX_VALUE;
} else {
throw (RuntimeException) ex;
}
}));
}
}
long result = futures.stream()
.map(f -> {
try {
return f.get();
} catch (InterruptedException | ExecutionException e) {
throw new RuntimeException(e);
}
}).max(Long::compare)
// if all values are negative, get the biggest one
.orElseGet(() ->(long)list.stream().max(Integer::compare).get());
System.out.println("Total execution time: " + (System.currentTimeMillis() - starttime));
System.out.println("Largest Sum: " + result);
System.out.println("Number of searches " + numTries);
}
private static void rest() throws Exception {
System.gc();
Thread.sleep(5000);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.