Jim Driscoll's Blog

Notes on Technology and the Web

Archive for the ‘Java 8’ Category

Java 8 features recap

leave a comment »

Just a quick post to recap the series of posts I just did on using Java 8 to handle some sample interview questions.

To learn the Java 8 API’s, I relied on Cay Horstman‘s just released book, Java SE 8 for the Really Impatient, and I can’t recommend it enough. It’s quite good.

The topics I covered were:

See the individual posts for more.

Written by jamesgdriscoll

January 20, 2014 at 8:57 AM

Bacon Numbers with Java 8, part 4

leave a comment »

This fourth part of the series of posts on getting a Bacon Number with Java 8 will probably be a bit of an anticlimax. As a reminder, we’re covering:

Given a large hash table whose keys are movie names and whose values 
are a list of actors in those movies, write a function to determine 
the Bacon Number of a particular actor.

We created sample data with Stream.generate, we also created a micro benchmark with functional interfaces, to measure how we were doing. And last post, we modified the data to be easier to search.

As the last step, we actually need to search that modified data. Since we only want to find the closest relationship, a Breadth First Search is certainly the way to go.

Set<Integer> visited = new HashSet<>();
Integer result = null;
Set<Integer> degreelist = actors.get(firstactor);
if (degreelist == null || actors.get(secondactor) == null) {   //short circuit
    result = -1;
} else {
    int degree = 1;
    while (result == null) {
        if (degreelist.contains(secondactor)) {
            result = degree;
            break;
        }
        degree++;
        if (degree > DEEPESTSEARCH) {
            result = DEEPESTSEARCH;
            break;
        }
        visited.addAll(degreelist);
        Set<Integer> nextDegreelist = new HashSet<>();
        degreelist.stream().forEach((i) -> {
            nextDegreelist.addAll(actors.get(i));
        });
        nextDegreelist.removeAll(visited);
        if (nextDegreelist.isEmpty()) {
            result = -1;
            break;
        }
        degreelist = nextDegreelist;
    }
}

Assuming we’re starting with a Map called actors, and two ints for the first and second actors to find. Create a Set of all visited actors (starting at the first one), and then just start iterating through each level, looking for the second one. When we find it, we’re done. Note that I use a forEach on the Stream from each degree to build the Set that I search. But we can do better:

        Set<Integer> visited = new HashSet<>();
        Integer result = null;
        Set<Integer> degreelist = actors.get(firstactor);
        if (degreelist == null || actors.get(secondactor) == null) {   //short circuit
            result = -1;
        } else {
            int degree = 1;
            while (result == null) {
                if (degreelist.contains(secondactor)) {
                    result = degree;
                    break;
                }
                degree++;
                if (degree > DEEPESTSEARCH) {
                    result = DEEPESTSEARCH;
                    break;
                }
                visited.addAll(degreelist);
                Set<Integer> nextDegreelist = degreelist.parallelStream().unordered()
                        .flatMap((i) -> actors.get(i).stream())
                        .collect(Collectors.toSet());
                nextDegreelist.removeAll(visited);
                if (nextDegreelist.isEmpty()) {
                    result = -1;
                    break;
                }
                degreelist = nextDegreelist;
            }
        }

Here, I build the Set I’m going to search through using a unordered parallelStream. I collapse the results of that Stream using flatMap into a Stream of Integers, then collect it at the end into a Set. All this is much more efficient, and results in a clock time savings of about 50% on an 8 core machine.

A word about what map and flatMap do, since I haven’t mentioned flatMap before: map will take a result on your Stream, and map it to a different value, applying the function you supply to each element of the Stream. Similarly, flatMap does the same thing, but it’s built to work with Streams as the returned object, and will unpack them from a Stream of Streams (of some Class) into a single continuous Stream of the Class. So this mapping function is taking a Stream of Integers, using them to look up a Set of Integers, and then unpacking that into individual Integers that it then returns as a Stream. All in one concise function.

At the end of that flatMap process, I bundle that Stream back up into a Set via the call to collect, and that’s what’s used for the next search.

And there you have it: We’ve not just found the Bacon Number as specified, we’ve enabled discovering any relationship degree at all.

All the source code for this and the previous 3 posts can be found in the gist. I’d love to know what you thought.

Written by jamesgdriscoll

January 11, 2014 at 3:52 PM

Bacon Numbers with Java 8, part 3

leave a comment »

Continuing the work of my previous post, we’re examining the following question:

Given a large hash table whose keys are movie names and whose values 
are a list of actors in those movies, write a function to determine 
the Bacon Number of a particular actor.

We created sample data with Stream.generate, we also created a micro benchmark with functional interfaces, to measure how we were doing. Now, let’s massage the data to get it into a form we can easily search.

As I mentioned in the first post, the main problem here is that the form of the data is completely inappropriate for the kind of search we wish to perform.

Movie 1 --
  -- Actor 1
  -- Actor 2
Movie 2 --
  -- Actor 2
  -- Actor 3

Far better would be to associate the actors with each other, so we could readily relate them.

Actor 1 --
  -- Actor 2
  -- Actor 3
Actor 2 -- 
  -- Actor 1
  -- Actor 3
Actor 3 --
  -- Actor 2

Performing this transformation is a relatively simple task.

Map<Integer, Set<Integer>> actorRelations = new HashMap<>();
// get all the list of actors for each movie
for (List<Integer> movie : set) {
    // for each actor in a movie
    for (Integer actor : movie) {
        // get the list of actors
        Set<Integer> coactors = new HashSet(movie);
        // remove self
        coactors.remove(actor);
        // add to the list of relations
        actorRelations.merge(actor, coactors,
            (existing, update) -> {
                existing.addAll(update);
                    return existing;
        });
    }
}

We’re going to create a Map, with the id of the actor as a key, and containing a Set of all the actors they have shared a movie with. Nothing new or interesting here, except one thing – the Map.merge method, which takes three parameters. The first is the key to operate on, the second, the value we wish to place into the Map. The third is a Function interface, called if the value is already set, and passed the existing value along with the new one. In our case, we wish to merge the two Sets, and we do so in the usual way.

We can do much the same thing with a Stream implementation, and I think it’s rather easier to read:

Map<Integer, Set<Integer>> actorRelations = new HashMap<>();
set.stream().forEach((movie) -> {
        movie.stream().forEach((actor) -> {
            Set<Integer> coactors = new HashSet(movie);
            coactors.remove(actor);
            actorRelations.merge(actor, coactors,
                    (existing, update) -> {
                        existing.addAll(update);
                        return existing;});
        });
    });

This operates slightly faster than the previous implementation, but only by a little.

To go through this — take the Set that contains the movies, and create a Stream. For each element in the Stream (and remember, that element is a List), create another Stream. For each element on that Stream, create a Set of all actors in that film (self excluded) and add that to the Map of relationships, merging if necessary.

Of course, one of the best things that you get when using Stream is the ability to change it to parallel processing with only a couple of extra method calls:

Map<Integer, Set<Integer>> actorRelations = new ConcurrentHashMap<>();
set.parallelStream().unordered().forEach((movie) -> {
    movie.stream().forEach((actor) -> {
        Set<Integer> coactors = new HashSet(movie);
        coactors.remove(actor);
        actorRelations.merge(actor, coactors,
            (existing, update) -> {
                existing.addAll(update);
                return existing;
            });
    });
});

This is the same as above, with two changes – instead of a HashMap, use a ConcurrentHashMap, and just add .parrallel().unsorted() to the Stream code. With that simple change, the clock time for this drops by over half (on an 8 core machine).

Next up, we’ll finish working on this problem by actually running the search.

Written by jamesgdriscoll

January 11, 2014 at 3:07 PM

Bacon Numbers with Java 8, part 2

leave a comment »

In my previous post, I started working on the following problem:

Given a large hash table whose keys are movie names and whose values 
are a list of actors in those movies, write a function to determine 
the Bacon Number of a particular actor.

So far, we’ve used Stream.generate, working with Random.nextGaussian to create a sample dataset, in the format Set<List<Integer>> – we’re using a Set since we (conveniently) don’t need to pay attention to the Movie Names.

Now that we have the data, we’re going to want to search it. But before we do, it’d be nice to be able to get a feel for the performance of the different algorithms we’re going to write. That means writing something that’s a useful micro benchmark tester. By functional interfaces in JDK 8, and providing lambdas, it’s pretty easy.

First, since we’ll be producing a summary of runtimes, create a function that prints out LongSummaryStatistics:

private void printStats(String name, String append, LongSummaryStatistics stats) {
    System.out.println(name + " Num Runs: " + stats.getCount());
    System.out.println(name + " Sum      " + append + ": " + stats.getSum());
    System.out.println(name + " Average  " + append + ": " + stats.getAverage());
    System.out.println(name + " Min      " + append + ": " + stats.getMin());
    System.out.println(name + " Max      " + append + ": " + stats.getMax());
}

These five method calls print out all the basics. It’d be nice if it also offered stats like the median and the mode, but we could always extend LongSummaryStatistics if we felt ambitious.

With that display out of the way, let’s take a first stab at creating a benchmark method:

private void benchmark(String name, Supplier supplier) throws Exception {
    // first run, warmup
    supplier.get();
    List timings = new ArrayList(NUMRUNS);
    for (int i = 0; i  name + " incremental time: " + (Duration.between(start, end).toMillis()));
    }
    printStats(name, "run time", timings.stream().mapToLong((l) -> (long) l).summaryStatistics());
}

This method takes a Supplier as a parameter. Then, it runs it once (to warm up any underlying JDK structures), and then runs it NUMRUNS times, saving the timings in a List. Running the supplied function is as simple as calling Supplier.get. To get those timings, we’re using the new Date/Time API in JDK 8, calling Instant.now, and getting the difference via Duration.between and Duration.toMillis. Though those calls are probably new to you, I bet you know what they do without explanation (I like the new Date/Time API for that very reason). There’s also a call to Logger.getGlobal in there, so we can examine intermediate results by turning logging on to the INFO level – and it takes a Supplier function as well, so we no longer have to provide a if/then for the logger – sweet!

A really good micro benchmark method would also strip the lowest and highest values, but I was interested in making this easy to understand, so I’ve left it out – but you could do that by taking the Stream of Long values and running a reduce operation on them.

To use this method with the method we’ve already developed to generate a list of Movies, we could just call it like so: benchmark("createMovies", this::createMovies); – this passes in a method reference. Since we’re not passing any arguments to create the movies (the values that we use for tuning are all set via statics), we don’t even need to create a lambda.

So, that covers the case for testing creating the movies. In fact, by using it, we can find out that creating a Gaussian distribution for our dataset takes about twice as long as a flat dataset, and trying to run it in parallel makes it slower (since Stream.generate doesn’t have a corresponding ParallelStream.generate, the parallelization happens in the wrong place, you’d need to use Futures instead).

What about testing the graph transform we’re about to write? We could just do something like this:

final Set<List> movies = createDistMovies();
benchmark("transformGraph constant data", () -> transformGraph(movies));

That will work – but will only execute the transform on the same data, over and over. Suppose you’d like to create a new dataset for each run – this would work:

benchmark("transformGraph constant data", () -> transformGraph(createDistMovies()));

But then you’d be measuring the wrong thing – you’d include the creation of the dataset as part of the measure, and that’s not right. No, instead we should do a something like this:

private <T, S> void benchmark(String name, Supplier<T> source, Function<T, S> sink) throws Exception {
    // first run, warmup
    sink.apply(source.get());
    List timings = new ArrayList(NUMRUNS);
    for (int i = 0; i  name + " incremental time: " + (Duration.between(start, end).toMillis()));
    }
    printStats(name, "run time", timings.stream().mapToLong((l) -> (long) l).summaryStatistics());
}

So, now we’re providing a Supplier to generate our data by calling Supplier.get (returning type T), and providing a Function which takes that data (also of type T), and transforms it by running Function.apply (returning type S). Neat, right? Otherwise, it’s pretty much doing the same thing as the previous version.

To use it, we would say:

benchmark("transformGraph dist data", this::createDistMovies, this::transformGraph);

Let’s expand on that, and think one more step ahead. After we have the transformed data, we’re going to want to run the actual search algorithm on it. Additionally, since we’re going to pick the start and end points at random, we might want to screen out values where the the two aren’t actually connected, or are connected in the first run – that means we’ll want to add a test to check for that. It’s actually pretty easy to do all that:

private <T, U> void benchmark(String name, 
                              Supplier<T> source, 
                              Function<T, U> sink, 
                              Predicate<U> ignoreresultif) throws Exception {
    // first run, warmup
    sink.apply(source.get());
    List<Long> timings = new ArrayList(NUMRUNS);
    List<U> results = new ArrayList(NUMRUNS);
    U result = null;
    Instant start, end;
    for (int i = 0; i < NUMRUNS; i++) {
        do {
            T t = source.get();
            rest();
            start = Instant.now();
            result = sink.apply(t);
            end = Instant.now();
            //log result, if appropriate
            final U res = result;
            Logger.getGlobal().info(() -> name + " incremental result: " + res);
            Instant s = start;
            Instant e = end;
            Logger.getGlobal().info(() -> name + " incremental time: " + 
                                       (Duration.between(s, e).toMillis()));
        } while (ignoreresultif.test(result));
        timings.add(Duration.between(start, end).toMillis());
        results.add(result);
    }
    if (result instanceof Integer) {
        printStats(name, "results", results.stream().mapToLong((num) -> ((Integer) num).intValue()).summaryStatistics());
    }
    printStats(name, "run time", timings.stream().mapToLong((l) -> (long) l).summaryStatistics());
}

So, same concept – we’ve got a Supplier as the source of data, there’s a Function which does something to that data, and returns a result, same as in the previous example. This time, though, we have a test, defined by the Predicate, which will ignore the result if the Predicate.test method returns true. Also, because we’re using the result, start and end values outside of the loop, the JDK doesn’t consider those ‘effectively final’ – so using them in the logging lambdas requires us to save them to another value before the log message (which is actually kind of a drag).

Now you can use this method to do some pretty sophisticated calls for running rough benchmarking on what’s going to be our finished product:

benchmark("breadthfirst variable data", () -> {
        Set<List> m = createDistMovies();
        return transformGraphWithParallelStreams(m);
    }, this::breadthFirst, (result) -> result < 1);

The Supplier is a lambda which creates the sample data, transforms it, and returns it, the next Function is our search function, which will (implicitly) be fed that result (how convenient is that!), and then will have it's result tested with the Predicate lambda – it'll ignore the result if it ended up being too easy of a search.

Next up, we'll transform the data to get it ready to search, including using a parallel stream.

Written by jamesgdriscoll

January 11, 2014 at 12:06 PM

Bacon Numbers with Java 8, part 1

leave a comment »

This is the fourth, and in all likelihood last, interview question that I’ll be using to explore JDK 8. It’s fun to look at new tech, but it’ll probably be years before I get to use JDK 8 at my current job. In case you’ve missed them, so far I’ve covered:

For my fourth question, I’m going to cover the following sample interview question: “Given a large hash table whose keys are movie names and whose values are a list of actors in those movies, write a function to determine the Bacon Number of a particular actor.”

If you’re unfamiliar with what a Bacon Number is, the internet is full of pretty good write-ups – I found a nice one with just a few clicks. Suffice it to say that it’s a pretty standard social graph problem.

Now, the question itself is the kind of “incorrectly-structured Graph” question that’s always given me problems during actual interviews – mostly because I pretty much never need to do anything like this at work. One of the nice things about working on generalized framework code is that you tend to have much better control of the inputs than someone working closer to the final problem to be solved. But I think I’ve found a way (for me, at least) to think about these things that makes more intuitive sense – as data structure problems.

As presented, this data structure is pretty classical unnormalized data – the Strings representing the Actors names are repeated everywhere, and there’s no link between the actors in any way that you could easily search.

Also, the question specifically doesn’t ask for the full answer to the “Six Degrees Of Kevin Bacon” party game – the questioner doesn’t care at all about the movie titles. So, one obvious answer would be to “normalize” the data down to a series of integers, each one acting as an ID to the actor, and then build a relationship table. Let’s do that – and after that, we should be able to dispatch this with a fairly simple breadth first function.

First, we can use the new JDK 8 Stream code to fairly easily produce a list of “movies”. We can use that for all our subsequent functional and performance testing.

Random random = new Random(System.currentTimeMillis());
int spread = MAXNUMACTORSPERMOVIE - MINNUMACTORSPERMOVIE + 1;

Set<List<Integer>> movies =  Collections.unmodifiableSet(
    Stream.generate(
        // make a stream of ramdom numbers, arranged evenly between 1-NUMACTORS
        () -> random.ints(1, NUMACTORS + 1)
        .distinct()
        // the stream should be MINNUMACTORSPERMOVIE - MAXNUMACTORSPERMOVIE in length
        .limit(random.nextInt(spread) + MINNUMACTORSPERMOVIE)
        // turn the stream into a List of Integers
        .boxed().collect(Collectors.toList()))
    // only create NUMMOVIES Lists 
    .limit(NUMMOVIES)
    // put those lists in a set
    .collect(Collectors.toSet())
);

If you’ve been reading my previous blogs, there’s not much new here: Create a new Stream, make that Stream consist of another Stream (generated by random.ints) which will be numbers between 1 and NUMACTORS, have no duplicates (distant), and be the correct length (limit). Box that Stream of int into Stream<Integer>, and collect it into a List. That means that the original (outer) Stream is actually a Stream<List> – which in turn we limit to the appropriate amount, and bundle up into a Set.

Creating a list of 300k ‘movies’ takes less than a second, and I regard that as plenty fast. To see the size of the Collection it produces, by the way, you could execute this:

movies.parallelStream().unordered().mapToLong((l) -> (long) l.size()).summaryStatistics()

On the aforementioned set of 300k movies, that takes about 40ms to run, and will let you know that those 300k movies contain 3.8 million “roles”.

You can also print out the data using a Stream, with a StringBuffer:

private void printMovieActors(Set<List<Integer>> set) {
    StringBuilder sb = new StringBuilder("Movies: ");
    set.stream().limit(MAXPRINT).forEach((l) -> {
        sb.append("\nMovie: \n");
        l.stream().forEach((s) -> sb.append(s).append(", "));
    });
    System.out.println(sb.toString());
}

That’s alright for sample data, but we could do a bit better: By using a simple random number generator, we created a flat distribution – there are some actors with a large number of roles, but not many.

One way to deal with that is to use a Gaussian distribution for the random numbers. That’s generated this way:

Random random = new Random(System.currentTimeMillis());
long midpoint = NUMACTORS / 2;
int spread = MAXNUMACTORSPERMOVIE - MINNUMACTORSPERMOVIE + 1;

Set<List<Integer>> movies = Collections.unmodifiableSet(
    Stream.generate(
        // make a stream of random numbers, distributed in a curve, between 1-NUMACTORS
        () -> Stream.generate(() -> Math.round(random.nextGaussian() * ONESIGMA + midpoint))
            .map((l) -> l.intValue())
            // remove any unsuitable values, both dups and out of range
            .filter((i) -> i > 0 && i <= NUMACTORS).distinct()
            // the stream should be MINNUMACTORSPERMOVIE - MAXNUMACTORSPERMOVIE in length
            .limit(random.nextInt(spread) + MINNUMACTORSPERMOVIE)
            // turn the stream into a List of Integers
            .collect(Collectors.toList()))
        // only create NUMMOVIES Lists 
        .limit(NUMMOVIES)
        // put those lists in a set
        .collect(Collectors.toSet())
    );

This is approximately the same code as before – instead of producing a an IntStream via Random.ints, we use a second Stream.generate – this calls a function which gets numbers that are more common in the middle than on the ends – random.nextGaussian returns a number which is going to land between -1 and +1 67% of the time. The rest of the time, it will land further and further away from zero, with decreasing probability.

So, by picking the value of ONESIGMA in the code above, we can control how big a group of “power players” we have in our simulated data set. (Actually, they’re called “super connectors” in social graph theory. Same thing.) The rest of the code consists of a filter to guard against values that are outside our allowable range (the Guassian number generator can generate pretty much any number), and a map to change the returned value from a long to an int (we could have done that in the generated code, but I wanted to show one use for a map transform).

In my sample code, I have a value for ONESIGMA of 10% of the total actors:

private final int ONESIGMA = NUMACTORS / 10; // 10% of actors get 67% of work

But that’s probably overly generous – from what I’ve heard, the number prolific actors is actually far, far smaller, and almost everyone in SAAG has only worked a handful of paying gigs.

Now that we have our data, we should use it! But this is already long, and so I’ll examine using this newly created sample data next time.

Written by jamesgdriscoll

January 9, 2014 at 6:17 PM

Using JDK 8 to get a sum of a list

with one comment

Another interview question, another chance to play with Java 8: “Given an array of integers (positive or negative) find the sub-array with the largest sum”.

Because arrays are a drag, let’s do this with a List. And note that the there’s no indication of whether the integers are bounded in size in any way. But again, because BigInteger is a bit a bit annoying to work with, I’m going to sidestep that as well (but JDK 8 provides a way to do that safely, as I’ll show in a second.)

First, we need to create that list of random numbers. In JDK 8 – it’s trivial:

List random
    = Collections.unmodifiableList(
        new Random()
        .ints(-100, 101)
        .limit(2500)
        .boxed()
        .collect(Collectors.toList())
    );

This is so easy I hesitate to even go through it, but… Random has a new function, ints, which returns a Stream of random int values, between the given numbers (with end number exclusive). So, get a Stream of numbers from -100 to 100. limit stops the stream after it generates 2500 values. boxed changes the IntStream returned by ints into Stream. Lastly, convert it into a List, and make that list unmodifiable.

And as a reminder, if you want to dump out the values of this list to standard out, it’s as simple as:

    random.stream().forEach(System.out::println); 

We’ll also need a List summing function. The obvious way to do it is:

    public long sum(List<Integer> l) {
        long ret = 0;
        for (int i: l) {
            ret += i;
        }
        return ret;
    }

But Netbeans helpfully suggests that it can be converted into a functional method – which, after a bit of massaging, looks like this:

    public long sum(List<Integer> list) {
        return list.stream()
                .map((i) -> (long) i)
                .reduce(0L, (accumulator, _item)
                        -> accumulator + _item); 
    }

Which is kinda neat – though it’s neither more readable (in my opinion) nor is it more performant (though it can be converted to parallel processing trivially, which is nice). Create a Stream, use a map method to cast each value to long, then reduce by adding all the values, returning that value.

But if the inputs are too large, it will return an incorrect value. In JDK 8, that’s easy to fix:

    public long sum(List<Integer> list) {
        return list.stream()
                .map((i) -> (long) i)
                .reduce(0L, (accumulator, _item)
                        -> Math.addExact(accumulator, _item)); 
    }

The new Math.addExact method is a convenience method with a check for overflow – if the value overflows, an ArithmeticException is thrown (without a check, if the value overflows, you’ll get a freakish looking result, since 2’s complement is not how we’re used to thinking of numbers).

Our program will still fail if the numbers get too large (that’s the price of not using BigInteger), but at least now, it’ll tell us, instead of silently spitting out bad data.

On to solving the problem. Remember: “First, make it work. Then, make it work fast.” The naive solution is pretty simple, just a couple loops:

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;
        }
    }
}

But this solution is pretty slow. The numTries variable increases at a frightening pace as the size of the dataset examined goes up. If you remember back to your CompSci homework assignments, it’s Triangular Number (which is essentially like a factorial, except using the sum instead of the product). That’s still O(n2) in Big O. We’re certainly going to want to make it faster. (On my machine, a list of 2500 random numbers takes a glacial 25 seconds to complete.)

Well, I’ve got 8 cores and I’m not afraid to use them. Let’s do parallel processing. At first, I looked into doing something with Streams. While I think it’d be possible to do this, I don’t think it’s advised – that doesn’t look like what Streams were meant to do. If I was writing some sort of framework code, it might be something to look into, but for now, just using Futures will probably do:

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  {
        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();
}

All right, there’s a few late-model JDK things going on in there, so let’s unpack them. The ArrayList declaration uses the diamond operator from JDK 7. The LongAdder class is new in JDK 8, and it’s pretty easy to understand what it does. It’s a faster alternative for accumulators (counters) in multithreaded environments, since under the hood it might even be several different variables that only collapse into one when you want to see the total value.

ForkJoinPool is a threading pool class from JDK 7 (it implements ExecutorService), and the commonPool method is new in JDK 8: it returns a pre-fab pool of threads for easy use. Just the thing for example programs, or anywhere else where you know your code is the only thing running in the VM. The submit method is the same venerable one from ExecutorService, but as you can see, you can feed it a lambda expression, with is way more convenient than an anonymous inner class (once you get used to them, and they’re starting to grow on me).

Because we’re feeding it a lambda that’s going to reference the start value, we need to fix that value, to promise it won’t change. We could write some extra code to get the lambda to take a parameter, but that’s work, and will decrease readability besides. So we can just fix the value into a new final variable, and access it without issue.

Actually dealing with the futures we’re creating is easy enough – just cycle through them in turn, waiting for them to complete (which is all that the get method is doing). We could return the value found, and get the max after they’re all complete, but I thought it might be more fun to examine another way, with AtomicLong. (Obviously, I’ve got some odd ideas of fun, but I’m an engineer, so that goes without saying.)

AtomicLong has a handful of new, lambda loving functions in JDK 8: I’m using accumulateAndGet, which I use to update the value of the long if the new value is greater than the current value. This will also return the new, updated value, but that’s safely ignored until the end of the process.

When all this is done, I’ve got a considerably faster program (about 7 seconds on my machine), and it’s not much more complicated… I’m loving what they’ve done here with threading.

But 7 seconds is still a pretty long time to search 2500 values. There’s got to be a better way – and of course, there is: interview questions are puzzles, and it’s rare that a detail of a puzzle is just there to mislead you. In this case, the question included that there are negative and positive numbers in the list.

Well, adding a negative number to a sum is never going to help matters, so if we just leave that operation out, we should be able to reduce the total number of searches considerably down from the 3 million or so that you get with 2500 values.

long resultValue = list.stream().max(Integer::compare).get(); // seed value
long numTries = 0;

for (int start = 0; start  0) {
        for (int end = start; end  0) {
                List tester = list.subList(start, end + 1); // sublist uses exclusive end
                long testresult = sum(tester);
                numTries++;
                if (testresult > resultValue) {
                    resultValue = testresult;
                }
            }
        }
    }
}

This is essentially the same program as the first, with a few small changes: We’re changing the seed value to calculate the maximum value (which we need to do to in case all the numbers are negative), and the there are a couple of added checks – if a value is negative or zero, it’s not going to increase the sum, so we can safely skip those computations. Calculating the max first is more inefficient than doing it at the end, but in a O(n2) function (which this still is), that’s more or less noise, and this way increases readability.

That last .get(), by the way, is because the value returned is an Optional (also new in JDK 8) – if the List is empty, there might be nothing to return. This is essentially a way around the “sideband return value” problem – API designers are always needing to come up with a way to indicate “nothing found”. JDK 8 finally offers a standard way to do that. Since we’re in control of inputs, we’re confident that something will be there, so we’re just going to sidestep that for now. (But read on.)

On my machine, that drops the execution time to about 6 seconds. With futures, we can do it even faster. While we’re at it, we’ll use another new JDK 8 feature, CompletableFutures.

List<Future<Long>> futures = new ArrayList<>();
LongAdder numTries = new LongAdder();

for (int start = 0; start  0) {
        futures.add(CompletableFuture.supplyAsync(() -> {
            long maxresult = list.get(s); //seed
            for (int end = s; end  0) {
                    List tester = list.subList(s, end + 1);
                    long testresult = sum(tester);
                    numTries.increment();
                    if (maxresult  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());

OK, that's a big lump of code. Let's break it down:

We're creating a List of Futures which return Long – that means that instead of just having the futures update a shared variable, they'll produce individual results. We'll instead process the values at the end.

You'll note that the explicit reference to ForkJoinPool is gone, but it's still in use – it's implicit in the call to CompletableFuture.supplyAsync (and you can instead specify a different ExecutorService, if you need one). supplyAsync takes a Supplier lambda, which is just a fancy way of saying "give it a no-args function that returns a value". In this case, we're returning a long, which fits our declaration that it's a Future, and the compiler will helpfully kvetch at us if it isn't.

The CompletableFuture has lots of methods for chaining, which is where it really shines. In our case, we want to intercept things if there's an exception, and override the result if it's an overflow. Here, we use the handle method do that. For our contrived example, if there's an overflow, we'll just stub in the maximum Long value – in a "real" program, maybe you'd even do the work to drop back to using BigInteger, or you could update a shared error value. Completable futures also let you chain things with methods like andThen, which executes a further task on the returned result, or andThenAsync, which lets you do the same thing, except by spawning yet another threaded task. It's a pretty nifty little class, and it's not hard to see it making parallel programming much, much easier.

I found a particularly excellent writeup on Completable Futures by Tomasz Nurkiewicz, or you could just go ahead and get Cay’s book, Java 8 For the Really Impatient, which as I’ve mentioned before is really awesome.

Other changes in the body of the program are primarily around restricting calls away from non-positive integers, and computing seed values.

The last part of the program is just another Stream reader to compute the maximum value – with a twist at the end. As the interim step, we read all the futures via Future.get(), and we need to check for the checked exceptions that throws – note the JDK 7 multi-catch. Then we compute the maximum value returned, and we’re done – almost.

If all the values are negative, there won’t be anything returned in the Stream, since our incredibly efficient program will ignore all of those values. What do do? Since the returned value from the stream is an Optional, we can write a small function (as a lambda) that will compute the maximum value of all those negative numbers, and that becomes our answer.

And what does all this get us? A much faster program: about 2 seconds on my (admittedly butch) machine, though I also get an additional 300 millseconds or so in savings if the thread pool is already warmed up.

All this code is up on a gist, if you want to read it in it’s entirety and try it out for yourself.

Written by jamesgdriscoll

January 4, 2014 at 11:46 AM

Combining two sorted lists

leave a comment »

As another interview question, let’s tackle the idea of sorting two sorted lists. While we’re at it, let’s discuss a few factors outside of the basic question being asked.

The question is: “Given two sorted lists, combine them into one sorted list”

Now, of course, that’s really easy in Java:

    private static List naiveListSort(List first, List second) {
        List combinedList = new ArrayList(first.size() + second.size());
        combinedList.addAll(first);
        combinedList.addAll(second);
        return Collections.sort(combinedList);
    }

…but that’s probably not what your interviewer had in mind. They’d like it to be faster. (This will sort two 20 million item lists in 2.5 seconds, but hey, always room for improvement.)

OK, let’s use Streams:

    private static void sortStreams(List first, List second) {
        Stream random1 = first.stream();
        Stream random2 = second.stream();
        Stream combined = Stream.concat(random1, random2).sorted();
        return combined.collect(Collectors.toList());
    }

That returns two 20 million item lists in 2.3 seconds. Still want it faster?

Well, depending on what you’re doing, you can just return a Stream instead of a List, that shaves off a pretty big chunk of time – it’s about 1 millisecond or so, since the sorting is done lazily. Running an operation like .count() on it works in 1.9 seconds. But that’s probably not what’s meant either. What they really mean is they want you to do it the hard way – take advantage of the fact that the two lists are already sorted, and use that to eke out a little more speed:

List combinedList = new ArrayList(first.size() + second.size());

int i = 0; // first index
int j = 0; // second index
int firstsize = first.size();
int secondsize = second.size();
while (i = second.get(j)) {
        combinedList.add(second.get(j++));
        if (j >= secondsize) {
            break;
        }
    }
    combinedList.add(first.get(i));
    if (j >= second.size()) {
        break;
    }
    i++;
}
if (j < second.size()) {  // add remaining
    combinedList.addAll(second.subList(j, secondsize));
} else if (i < first.size()) {
    combinedList.addAll(first.subList(i+1, firstsize));
}

That delivers results in 1.7 seconds. Total savings over the Stream version, .6 seconds! That's a savings of about 25%!

This is also the best case scenario for the naive functions – the comparison operation can literally fit into a single assembly instruction, and thus executes lightning fast. As the complexity of the comparison goes up, the difference in execution times does too. So, the improvement for other sorts (such as on String alphanumeric order) will be even larger.

But look what you gave up by doing this the fastest way:

  • It's now more fragile – if you pass it unsorted data, it will pass back even more unsorted data. A single out of place value causes a severe failure.
  • It's harder to read and maintain, meaning that at some point, it will cost precious manpower if you need to modify it in any way. And it will need to be tested – it's all too easy for a small bug to make it's way in.
  • Also, if you want the result to be a Stream, you have to convert it back (and from what I've seen so far of Streams, their use is going to become extremely common). But that last point is prehaps a bit unfair.

Still, the likelihood of needing the last method is somewhat remote, unless you're writing framework software or a database. The likelihood of needing one of the preceding methods is pretty good. (As a framework developer, I still write more code that looks like the first version than the last. It's all about the critical path.)

So, if you're interviewing a candidate, I'd suggest that the answer you're looking for is probably one of the first ones, rather than the last one. While your candidate should certainly be able to program the last one, they should also have to wisdom to know that it's almost never necessary – and why. Good answers would include such phrases as: "Is this in the critical path?", "What's the user expectation for response time?", and "How robust does this have to be? Can I trust the inputs?"

If you're interested in the complete code (including the surrounding code which tests performance, in a fairly primitive manner), see the gist.

Written by jamesgdriscoll

January 2, 2014 at 5:39 PM