Asymmetric nearest-neighbour in Java
From a sorted map, I want to retrieve a subset of n entries, starting m entries before a specified value v. For example, for the key set k = {0.2, 0.3, 0.4, 0.6, 0.8, 0.9, 1.0}, a query with n=5, m=2, v=0.5, would return {0.3, 0.4, 0.6, 0.8, 0.9}. Is there an implementation of a data structure in Java supporting such a query, without having to iterate over the whole (big) set?
What do I need this for? Interpolation. I want to interpolate at v based on the values in the map. However, I have many v. They are sorted, and have a spacing between them much s开发者_StackOverflowmaller than the ones in k. So, I take a range of entries from the map, do some expensive preparatory calculations with them (for example calculating coefficients of a polynom), and can then quickly interpolate another value in that range (by evaluating the polynom with that value).
But why do I need the m entries before v? The values in k are usually equally spaced, and in order to avoid the Runge phenomenon of high oscillations at the ends of the interpolation interval, I simply cut them off, which means I need some nodes before the actual valid interval of the interpolation.
Does that make sense? What’s your suggestion?
(It would be fun if a method like java.util.TreeMap.ceilingEntry() would return an iterator, with which I could step back twice.)
This is much simpler than that:
- Use binary search to get the position at which v would be inserted in the list so that it will stay sorted.
- Move m positions to the left
Take the first n elements to the right.
double[] k = new double[] {0.2, 0.3, 0.4, 0.6, 0.8, 0.9, 1.0}; int n=5; int m=2; double v=0.5; int pos = Arrays.binarySearch(k, v); if (pos < 0) pos = -pos - 1; while(pos > 0 && k[pos-1]==v) --pos; pos = Math.max(pos-m, 0); double[] result = Arrays.copyOfRange(k, pos, Math.min(pos+n, k.length));
Using headMap()
and tailMap()
is probably the most straightforward solution. If one fears the overhead of making the same search twice, using a list instead of a map is probably the solution. I extended Petar’s suggestion. It can now handle key-value pairs, represented by the small subclass Pair
:
public class DataSet {
// Usage example
public static void main (String [] args) {
DataSet nn = new DataSet ();
nn.add(0.2,1);
nn.add(0.3,2);
nn.add(0.4,3);
nn.add(0.6,4);
nn.add(0.8,5);
nn.add(0.9,6);
nn.add(1.0,7);
int n = 5;
int m = 2;
double v = 0.5;
ListIterator <Pair> it = nn.iterator(v);
for (int i=0; i<m; ++i)
it.previous();
for (int i=0; i<n; ++i)
System.out.append(it.next()+"\n");
}
// Implementation
TreeSet <Pair> set = new TreeSet <Pair> (new PairComparator());
ArrayList <Pair> list = new ArrayList <Pair> ();
boolean listUpToDate = false;
// Add data
boolean add (double x, double y) {
listUpToDate = false;
return set.add(new Pair(x,y));
}
// Get iterator at specified position
ListIterator <Pair> iterator (double v) {
if (!listUpToDate) {
list = new ArrayList (set);
listUpToDate = true;
}
int pos = Collections.binarySearch(list,v);
if (pos < 0)
pos = -pos - 1;
return list.listIterator(pos);
}
// Helper class
static class Pair implements Comparable <Double> {
double x, y;
Pair (double x, double y) {
this.x = x; this.y = y;
}
public int compareTo (Double d) {
return Double.valueOf(x).compareTo(d);
}
public String toString () {
return String.format("[%.1f,%.1f]",x,y);
}
}
// Used for sorting
class PairComparator implements Comparator <Pair> {
public int compare (Pair n0, Pair n1) {
return Double.valueOf(n0.x).compareTo(Double.valueOf(n1.x));
}
}
}
Of course, one could also just use the list, and make sure it is sorted before calling binarySearch()
. But the TreeSet
has also the advantage, besides the ordering, that it prevents duplicate keys.
You can place the entries in a sorted array and use a Arrays.binarySearch().
However if you must have a NavigableMap like TreeMap, you need to do two lookups to get the headMap() and tailMap() and iterate over those.
精彩评论