-1

从排序的地图中，我想检索n个条目的子集，从指定值 v之前的m个条目开始。例如，对于键集k = {0.2, 0.3, 0.4, 0.6, 0.8, 0.9, 1.0}，n = 5, m =2, v =0.5 的查询将返回 {0.3, 0.4, 0.6, 0.8 , 0.9}。Java 中是否有数据结构的实现支持这样的查询，而不必遍历整个（大）集合？

我需要这个做什么？插值。我想根据地图中的值在v处进行插值。但是，我有很多v。它们已排序，并且它们之间的间距比k中的间距小得多。因此，我从地图中获取一系列条目，对它们进行一些昂贵的准备计算（例如计算多项式的系数），然后可以快速插入该范围内的另一个值（通过使用该值评估多项式）。

但是为什么我需要m之前的条目v？k中的值通常是等间距的，为了避免插值区间末端出现高震荡的龙格现象，我简单地把它们剪掉了，这意味着在插值的实际有效区间之前我需要一些节点。

那有意义吗？你有什么建议？

（如果像 java.util.TreeMap.ceilingEntry() 这样的方法会返回一个迭代器，那会很有趣，我可以用它后退两次。）

4

3 回答 3

1

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.

于 2011-07-25T17:21:17.430 回答
1

这比这简单得多：

  1. 使用二分搜索来获取 v 将被插入到列表中的位置，以便它保持排序。
  2. 向左移动 m 个位置

  3. 取右边的前 n 个元素。

    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));
于 2011-07-25T09:05:28.503 回答
0

您可以将条目放在排序数组中并使用 Arrays.binarySearch()。

但是，如果您必须拥有像 TreeMap 这样的 NavigableMap，则需要进行两次查找以获取 headMap() 和 tailMap() 并遍历它们。

于 2011-07-25T09:07:38.070 回答