Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm writing a 2d top down game where I perform a lot of "closest" searches between one point and all the rest of the points.

In this example, "me" wants to search for the closest visible house (Home) that I haven't visited yet, and if it is not found, return null.

protected Home getClosestUnvisitedVisibleHome(Person me, final int VISIBLE_ZONE) {
    List<Home> visitedHomes = me.getVisitedHomes();
    Map<Home, Integer> homeDistances = new HashMap<>();
    List<Home> allHomes = getHomes();
    allHomes.stream().parallel().forEach(home -> homeDistances.put(home, range(me, home)));
    List<Home> unvisitedVisibleHomes = allHomes.stream().parallel().filter(
            home -> !visitedHomes.contains(home) && homeDistances.get(home) <= VISIBLE_ZONE
    ).collect(Collectors.toList());
    unvisitedVisibleHomes.sort((home1, home2) -> homeDistances.get(home1).compareTo(homeDistances.get(home2)));
    try {
        return unvisitedVisibleHomes.get(0);
    } catch (IndexOutOfBoundsException e) {
        return null;
    }
}

protected int range(VisibleEntity visibleEntity, VisibleEntity me) {
    return (int)Math.sqrt(Math.pow((visibleEntity.xy[0] - me.xy[0]), 2) + Math.pow((visibleEntity.xy[1] - me.xy[1]), 2));
}

I'm looking for suggestions on how to optimize this particular function and or any suggestions of its content.

share|improve this question
    
Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. – Vogel612 Feb 2 at 14:41
2  
Note: VISIBLE_ZONE should be visibleZone due to Java naming conventions. – Boris the Spider Feb 2 at 16:13
3  
Given this code context @BoristheSpider is correct. If VISIBLE_ZONE would have been a static final int, it would have been regarded as a constant and VISIBLE_ZONE would have been the correct naming convention. As it is currently a parameter to the method, it should follow the camelCase naming convention. – Simon Forsberg Feb 2 at 21:37
up vote 14 down vote accepted

I don't see why you use a HashMap (or any Map) at all.

What I'd do is:

  • Get all the homes
  • Filter all the homes to only get those which are unvisited
  • Get the home that is closest

The home that you get will either be visible, or it won't be visible. If it is not visible, there won't be any other visible homes either.

Combining this with @Vogel's suggestion of using Set the code would go something like this:

Set<Home> visitedHomes = me.getVisitedHomes();
Set<Home> allHomes = getHomes();
Optional<Home> result = allHomes.stream().parallel()
    .filter(home -> !visitedHomes.contains(home))
    .min(Comparator.comparingInt(home -> range(me, home)))
    .map(result -> range(me, result) <= VISIBLE_ZONE ? result : null);

And then you can choose between either returning the optional:

return result;

or returning null if there is no match:

return result.orElse(null);
share|improve this answer
    
The .min function must be implemented like this .min((home1, home2) -> range(me, home1) - range(me, home2)); – Per Eriksson Feb 2 at 14:04
    
I would avoid all mention of null unless absolutely necessary - you can use Optional.map and Optional.flatMap to process the result in a null safe manner. – Boris the Spider Feb 2 at 16:14
    
@PerEriksson I'd recommend using Comparator.comparingInt instead, see latest edit. – Simon Forsberg Feb 2 at 21:43

The obvious problem that jumps out at me is the mutation of HashMap with parallel streams.

One difficulty in implementing parallelism in applications that use collections is that collections are not thread-safe, which means that multiple threads cannot manipulate a collection without introducing thread interference or memory consistency errors. The Collections Framework provides synchronization wrappers, which add automatic synchronization to an arbitrary collection, making it thread-safe. However, synchronization introduces thread contention. You want to avoid thread contention because it prevents threads from running in parallel. Aggregate operations and parallel streams enable you to implement parallelism with non-thread-safe collections provided that you do not modify the collection while you are operating on it.

Note that parallelism is not automatically faster than performing operations serially, although it can be if you have enough data and processor cores. While aggregate operations enable you to more easily implement parallelism, it is still your responsibility to determine if your application is suitable for parallelism.

So, you have a design decision to make on whether you still want parallelism, and if you do, you have a race condition to fix.

I find it odd that your distance metric involves rounding down the distance to an integer. You could use the square of the Euclidean distance as the comparison metric, thus sparing you the inefficiency of taking the square root and the loss of precision by rounding down.

The range() function doesn't appear to depend on any object state. Making it static should help the JIT with its optimizations.

If you just want the minimum element, don't sort the entire collection. Use Collections.min() instead.

Instead of sometimes returning null, which could trigger a NullPointerException down the line, consider returning an Optional<Home> to make it clear that there might not be a result.

share|improve this answer

Data Structures

Since each Home only exists once, a Set may be a better data-structure to keep houses in.

Instead of using an integer to specify distance you may as well use a double.

Algorithmic improvements

You're calculating the homeDistances for each and every home in allHomes. Then you proceed to ignore a significant portion of the homes and accordingly you waste a significant amount of computation time for something you don't use ...

Sets allow rather fast checks for contains, and as such are well-suited to the "subproblem" of grabbing unvisited homes.
Consider:

Set<Home> visitedHomes = me.getVisitedHomes();
Set<Home> unvisitedHomes = getHomes();

unvisitedHomes.removeAll(visitedHomes);

At this point you did already stream allHomes twice. This should be significantly more effective.

Now the distances get interesting.

Map<Home, Double> homeDistances = new HashMap<>();
homeDistances.putAll(unvisitedHomes.stream()
    .collect(Collectors.groupingBy(Function.identity(), home -> range(me, home)))
);

For the next steps I advise you to read 200_success' answer because that's a really nice way of handling it

share|improve this answer
2  
I spotted problems with the code, but @Simon has the better solution. – 200_success Feb 2 at 10:46

This is my summation of all the advice and what I ended up with. All collections are of type Set:

protected Optional<Home> getClosestUnvisitedVisibleHome(Person me, int visibleZone) {
    return getHomes().parallelStream()
            .filter(home -> !me.getVisitedHomes().contains(home)) //Unvisited
            .min(Comparator.comparingDouble(home -> rangeSimplified(me, home))) //Closest
            .map(result -> range(me, result) <= visibleZone ? result : null); //Visible
}

protected static double range(VisibleEntity entity1, VisibleEntity entity2) {
    return Math.sqrt(Math.pow((entity1.xy[0] - entity2.xy[0]), 2) + Math.pow((entity1.xy[1] - entity2.xy[1]), 2));
}

protected static double rangeSimplified(VisibleEntity entity1, VisibleEntity entity2) {
    return Math.pow((entity1.xy[0] - entity2.xy[0]), 2) + Math.pow((entity1.xy[1] - entity2.xy[1]), 2);
}
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.