Асимметричный ближайший сосед в Java

Question

Из отсортированной карты я хочу получить подмножество из n записей, начиная с m записей до указанного значения v. Например, для набора ключей 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 на основе значений на карте. Тем не менее, у меня есть много против. Они отсортированы, и расстояние между ними намного меньше, чем в k. Итак, я беру ряд записей с карты, делаю с ними дорогостоящие подготовительные вычисления (например, вычисляем коэффициенты полинома) и затем могу быстро интерполировать другое значение в этом диапазоне (оценивая полином с этим значением).

Но зачем мне нужно m записей до v? Значения в k обычно расположены на равном расстоянии друг от друга, и, чтобы избежать явления Рунге высоких колебаний на концах интервала интерполяции, я просто их обрезаю, что означает, что мне нужно несколько узлов до фактического действительного интервала интерполяции.

Имеет ли это смысл? Каково ваше предложение?

(Было бы интересно, если бы такой метод, как java.util.TreeMap.ceilingEntry(), возвращал итератор, с помощью которого я мог бы отступить дважды.)

Answer 1

С помощью headMap() а также tailMap() это, наверное, самое простое решение. Если кто-то боится сделать один и тот же поиск дважды, то, вероятно, решением будет использование списка вместо карты. Я продлил предложение Петра. Теперь он может обрабатывать пары ключ-значение, представленные небольшим подклассом. 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));
    }
  }

}

Конечно, можно также использовать список и убедиться, что он отсортирован перед вызовом binarySearch(), Но TreeSet кроме упорядочения, также имеет то преимущество, что он предотвращает дублирование ключей.

Answer 2

Это намного проще, чем это:

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));
   

Answer 3

Вы можете поместить записи в отсортированный массив и использовать Arrays.binarySearch().

Однако, если у вас должен быть NavigableMap, такой как TreeMap, вам нужно выполнить два поиска, чтобы получить headMap() и tailMap() и выполнить итерацию по ним.