Find closest entries in a list by comparing with one entry

Question

I have a Unit class which has lots of fields in it as shown below:

public class Unit {
  private final int id;
  private final int beds;
  private final String city;
  private final double lat;
  private final double lon;

  // constructors and getters here
  // toString method

}

I now have a List of Unit which is a List object which contains lots of Units. Now I need to find the nearest Units from List object to Unit x. Cap the results by limit.

  private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {
    List<Unit> output = new ArrayList<>();

    // how do I sort lists object in such a way so that I can get nearest units here to "x"?

    return output;
  }

We have lat/long present in the Unit class so we can use that to calculate euclidean distance and do the comparison. I am confused on how to sort the list of units by shortest distance and get the nearest units. I am working with Java 7 as of now so I can't use Java 8.

1) Create a `Map` with the units as keys and the distances to unit x as value. 2) Use one of the solutions from [this question](https://stackoverflow.com/questions/109383/sort-a-mapkey-value-by-values) to sort the map by value. — Robby Cornelissen, Apr 05 '19 at 04:27

score 2 · Answer 1 · answered Apr 05 '19 at 04:42

// this distance method reference from https://stackoverflow.com/a/16794680/6138660

public static double distance(double lat1, double lat2, double lon1,
        double lon2) {
    final int R = 6371; // Radius of the earth

    double latDistance = Math.toRadians(lat2 - lat1);
    double lonDistance = Math.toRadians(lon2 - lon1);
    double a = Math.sin(latDistance / 2) * Math.sin(latDistance / 2)
            + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2))
            * Math.sin(lonDistance / 2) * Math.sin(lonDistance / 2);
    double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1 - a));
    double distance = R * c * 1000; // convert to meters

    distance = Math.pow(distance, 2);

    return Math.sqrt(distance);
}

private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {


    lists.sort(new Comparator<Unit>() {

        @Override
        public int compare(Unit o1, Unit o2) {

            double flagLat = x.getLat();
            double flagLon = x.getLon();

            double o1DistanceFromFlag = distance(flagLat, o1.getLat(), flagLon, o1.getLon());
            double o2DistanceFromFlag = distance(flagLat, o2.getLat(), flagLon, o2.getLon());

            return Double.compare(o1DistanceFromFlag, o2DistanceFromFlag);
        }
    });

    return lists.subList(0, limit);;
  }

This would work, but it would be faster to create a list of say `UnitDistance { Unit unit; double distance; }` and then sort it by distance: the distance would be computed only once per unit Other option: fill a a `TreeMap`. — Maurice Perry, Apr 05 '19 at 04:52

score 2 · Accepted Answer · answered Apr 05 '19 at 04:50

You said that you know how to calculate the distance, so my code below does not include the calculation so I assume you can implement the calculateDistance() method. I use a TreeMap which automatically sorts entries added to it and class Double implements Comparable so you don't need to handle the sorting. The Iterator will return the keys sorted by the calculated distance.

private List<Unit> nearestUnits(List<Unit> lists, Unit x, int limit) {
    TreeMap<Double, Unit> sorted = new TreeMap<>();
    List<Unit> output = new ArrayList<>();
    for (Unit unit : lists) {
        Double distance = calculateDistance(unit, x);
        sorted.put(distance, unit);
    }
    Set<Double> keys = sorted.keySet();
    Iterator<Double> iter = keys.iterator();
    int count = 0;
    while (iter.hasNext() && count < limit) {
        Double key = iter.next();
        Unit val = sorted.get(key);
        output.add(val);
        count++;
    }
    return output;
}

This is more unreadable and FYI `TreeMap::put` is `O(log n)` (this is not a `HashMap`), so inserting `n` elements would be `O(n log n)`. `ArrayList::sort` is also `O(n log n)` and it is much much better in readability. — Jai, Apr 05 '19 at 05:07
@Jai, Cool, so please provide your own answer and enlighten us all. — Abra, Apr 05 '19 at 05:15

Find closest entries in a list by comparing with one entry

2 Answers2