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

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

0 голосов
/ 25 июля 2011

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

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

Имеет ли это смысл?Что вы предлагаете?

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

Ответы [ 3 ]

1 голос
/ 25 июля 2011

Использование 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 есть также преимущество, помимо порядка, что он предотвращает дублирование ключей.

1 голос
/ 25 июля 2011

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

  1. Используйте бинарный поиск, чтобы получить позицию, в которой v будет вставлен в список, чтобы он оставался отсортированным.
  2. Move 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));
0 голосов
/ 25 июля 2011

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

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

...