I’m trying to implement a method of searching trough a large amount of 2D points for those that match a certain range. I’m thinking of creating HashMaps for <X, Point> and <Y, Point> but I’m wondering is HashMap good for doing this, because I will be taking points in a range, based on values from x_min to x_max and y_min to y_max.
So I will basically take all points from <X,Point> searching from x_min to x_max and compare them to points taken from <Y,Point> from y_min to y_max…
HashMap<Integer,Point> x_coordinates = new HashMap<Integer,Point>();
for(int i=x_min;i<=x_max;i++){
if(x_coordinates.containsKey(i))
x_coordinates.get(i);
}
HashMap<Integer,Point> y_coordinates = new HashMap<Integer,Point>();
for(int i=y_min;i<=y_max;i++){
if(y_coordinates.containsKey(i))
y_coordinates.get(i);
}
Is there a faster way to get a range of values from a HashMap, or some other type of data structure?
For example, if range = 200, select all points that match the range from x-200 to x+200 and from y-200 to y+200
I’m trying to avoid iteration through all of the points, but also I want to avoid making a huge 2D matrix, because the points in question are scattered around a large area.
After some testing and based on MichaelT’s answer, I’ve written this code:
TreeMap<Integer, TreeMap<Integer, Integer>> values;
for (int x : values.subMap(x_min, x_max).keySet()) {
for (int y : values.get(x).subMap(y_min, y_max).values()) {
// y here, represents the values of points in range...
}
}
2
What you are describing is a sparse matrix upon which you wish to do a range select.
I’m going to start out with no, neither a HashMap nor a LinkedHashMap will do what you want optimally. The reason for this to find the elements in a range HashMap is effectively walking an unordered list – O(n). The LinkedHashMap may be slightly more optimal than awful if the elements are put into the LinkedHashMap in sorted order and no new ones are added afterwards. Its still not an optimal approach because instead of O(n) you’re getting O(n/m) (because you stop walking the list once you get past the range) which is still effectively O(n). You can’t do a binary search on the LinkedHashMap list.
So, lets look at some other structures. What you are really after is the SortedMap interface. It allows you to quickly pull out the sub map from one key to another with SortedMap subMap(K fromKey, K toKey) which is what you want to do. Pick one of those classes and you will have what you are after.
You could then get the values for each of the submaps and do a boolean retainAll(Collection c) of one set to the other.
That’s the easy answer. It is effectively the lists of lists approach for the sparse matrix. You could, however encode the matrix instead in some other format that gives you a more direct sub range option. This isn’t something that is part of the Java standard library and you may find yourself going down this path for writing your own implementation in that case.
If you see the possibility in the future that this may be the case, you should consider writing your own interface for the sparse matrix and then implement a class behind it that does the lookups that you want. This way if you later decide that you need to change the implementation for some reason, its a matter of changing the implementation (a new class that wraps something else) rather than changing all the code to handle a different structure.
6
While your solution based on a treemap of treemaps will work, and is much better than the hashmap solution you started with, you may want to look into the possibility of using a QuadTree, which is a structure similar to a TreeMap but with a pair of coordinates as the key rather than just one. This makes selecting rectangular ranges from them particularly efficient. There are many implementations available for Java that can be found with a quick google.
1
You definitively should have a look at the k-d tree. This structure is typically used to answer questions such as “Does this point exist?”, “Where is the nearest post office?”, or “Who are the employees between 30 and 40 years old, and paid between 2K and 3K?”
So, your problem is a typical range search problem for which this structure is particularly well suited. According to Wikipedia, the worst case time for your problem, with this structure, is O(k.N^(1-(1/k)), where k is the number of dimensions (2, in your case) and N is the number of nodes in the tree.
Some limitations, however:
- Building a k-d tree is time consuming, because you have to determine the “median” point in order get a balanced tree. That means that you have to order your points… You can decide to not use the median point as a basis for your splitting planes, but you could get an unbalanced tree, which will be less efficient. As a tradeoff, you can choose the median point among a subset of your point, to avoid a very bad selection.
- If you have to add or to remove points, it can be done in log n time. But these operations are likely to unbalance the tree, so your performances will decrease over time, unless you spend extra time for re-balancing it. If you have to frequently add/remove points, and if your dimensions have fixed sizes, you could consider quadtrees as an alternative.
I have never used it, but apparently Java ML has a decent implementation of k-d trees.
Instead of two hash of coordinates, you may use a list of Point2D and iterate through it.
And extract a filtered List than you can
That way, only one loop is done.
int distance = 200;
Point2D.Double refPoint = new Point2D.Double(0,0);
List<Point2D.Double> pointstoSearch = new ArrayList<Point2D.Double>();
List<Point2D.Double> filtered = new ArrayList<Point2D.Double>();
List<Point2D.Double> POIs = new ArrayList<Point2D.Double>();
POIs.add(new Point2D.Double(99d,100d));
POIs.add(new Point2D.Double(101.8, 202.3));
POIs.add(new Point2D.Double(-50, -98));
//filtering
for (Point2D.Double point : POIs) {
if (point.distance(refPoint)<= distance) filtered.add(point);
}
//now search only the matching points//filtering
for (Point2D.Double poi : filtered) {
for (Point2D.Double point : pointstoSearch) {
if (poi.equals(point)) //match
}
}
For maximum efficiency, and if the map of searched coordinates (POI in my sample) is ~constant, you should consider using a quadtree structure.
1