-1

ソートされたマップから、指定された値 vの前にm個のエントリを開始して、 n個のエントリのサブセットを取得したいと思います。たとえば、キーセット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の間隔よりもはるかに小さくなっています。そこで、マップからエントリの範囲を取得し、それらを使用して高価な準備計算を実行し（たとえば、多項式の係数を計算し）、その範囲内の別の値をすばやく補間できます（その値で多項式を評価することにより）。

しかし、なぜvの前にm個のエントリが必要なのですか？kの値は通常等間隔であり、補間間隔の終わりでの高振動のルンゲ現象を回避するために、単純にそれらを切り取ります。つまり、補間の実際の有効な間隔の前にいくつかのノードが必要です。

それは理にかなっていますか？あなたの提案は何ですか？

（java.util.TreeMap.ceilingEntry（）のようなメソッドがイテレーターを返し、それを使用して2回戻ることができれば楽しいでしょう。）

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（）を取得し、それらを反復処理するために2つのルックアップを実行する必要があります。

于 2011-07-25T09:07:38.070 に答える