Существует ли структура данных Java, которая фактически представляет собой ArrayList с двойными индексами и встроенной интерполяцией?

Разрешение значений double в качестве индексов является довольно большим изменением по сравнению с тем, что делает ArrayList.

Причина этого в том, что массив или список с double в качестве индексов почти по определению будет разреженным массивом, что означает, что он не имеет значения (или, в зависимости от вашего определения: фиксированное, известное значение) почти для всех возможных индексов, и только конечное число индексов имеет явно заданное значение.

В Java SE нет готовых классов, поддерживающих все это.

Лично я бы реализовал такую ​​структуру данных, как список пропуска (или аналогичный структура данных с быстрым поиском) из (index, value) кортежей с соответствующей интерполяцией.

Редактировать: На самом деле есть довольно хорошее соответствие для внутреннего хранилища (т. е. всего, кроме интерполяции): просто используйте NavigableMap, например TreeMap, чтобы сохранить сопоставление индекса со значением.

При этом вы можете легко использовать ceilingEntry() и (при необходимости) higherEntry(), чтобы получить ближайшее значение(я) к нужному индексу, а затем интерполировать их.

Если ваша текущая реализация имеет сложность O(log N) для интерполяции значения, реализация, которую я только что сделал, может быть для вас:

package so2675929;

import java.util.Arrays;

public abstract class AbstractInterpolator {
  private double[] keys;
  private double[] values;
  private int size;

  public AbstractInterpolator(int initialCapacity) {
    keys = new double[initialCapacity];
    values = new double[initialCapacity];
  }

  public final void put(double key, double value) {
    int index = indexOf(key);
    if (index >= 0) {
      values[index] = value;
    } else {
      if (size == keys.length) {
        keys = Arrays.copyOf(keys, size + 32);
        values = Arrays.copyOf(values, size + 32);
      }
      int insertionPoint = insertionPointFromIndex(index);
      System.arraycopy(keys, insertionPoint, keys, insertionPoint + 1, size - insertionPoint);
      System.arraycopy(values, insertionPoint, values, insertionPoint + 1, size - insertionPoint);
      keys[insertionPoint] = key;
      values[insertionPoint] = value;
      size++;
    }
  }

  public final boolean containsKey(double key) {
    int index = indexOf(key);
    return index >= 0;
  }

  protected final int indexOf(double key) {
    return Arrays.binarySearch(keys, 0, size, key);
  }

  public final int size() {
    return size;
  }

  protected void ensureValidIndex(int index) {
    if (!(0 <= index && index < size))
      throw new IndexOutOfBoundsException("index=" + index + ", size=" + size);
  }

  protected final double getKeyAt(int index) {
    ensureValidIndex(index);
    return keys[index];
  }

  protected final double getValueAt(int index) {
    ensureValidIndex(index);
    return values[index];
  }

  public abstract double get(double key);

  protected static int insertionPointFromIndex(int index) {
    return -(1 + index);
  }
}

Конкретные интерполяторы должны будут реализовать только функцию get(double).

Например:

package so2675929;

public class LinearInterpolator extends AbstractInterpolator {

  public LinearInterpolator(int initialCapacity) {
    super(initialCapacity);
  }

  @Override
  public double get(double key) {
    final double minKey = getKeyAt(0);
    final double maxKey = getKeyAt(size() - 1);
    if (!(minKey <= key && key <= maxKey))
      throw new IndexOutOfBoundsException("key=" + key + ", min=" + minKey + ", max=" + maxKey);

    int index = indexOf(key);
    if (index >= 0)
      return getValueAt(index);

    index = insertionPointFromIndex(index);
    double lowerKey = getKeyAt(index - 1);
    double lowerValue = getValueAt(index - 1);
    double higherKey = getKeyAt(index);
    double higherValue = getValueAt(index);

    double rate = (higherValue - lowerValue) / (higherKey - lowerKey);
    return lowerValue + (key - lowerKey) * rate;
  }

}

И, наконец, юнит-тест:

package so2675929;

import static org.junit.Assert.*;

import org.junit.Test;

public class LinearInterpolatorTest {

  @Test
  public void simple() {
    LinearInterpolator interp = new LinearInterpolator(2);
    interp.put(0.0, 0.0);
    interp.put(1.0, 1.0);

    assertEquals(0.0, interp.getValueAt(0), 0.0);
    assertEquals(1.0, interp.getValueAt(1), 0.0);
    assertEquals(0.0, interp.get(0.0), 0.0);
    assertEquals(0.1, interp.get(0.1), 0.0);
    assertEquals(0.5, interp.get(0.5), 0.0);
    assertEquals(0.9, interp.get(0.9), 0.0);
    assertEquals(1.0, interp.get(1.0), 0.0);

    interp.put(0.5, 0.0);

    assertEquals(0.0, interp.getValueAt(0), 0.0);
    assertEquals(0.0, interp.getValueAt(1), 0.0);
    assertEquals(1.0, interp.getValueAt(2), 0.0);
    assertEquals(0.0, interp.get(0.0), 0.0);
    assertEquals(0.0, interp.get(0.1), 0.0);
    assertEquals(0.0, interp.get(0.5), 0.0);
    assertEquals(0.75, interp.get(0.875), 0.0);
    assertEquals(1.0, interp.get(1.0), 0.0);
  }

  @Test
  public void largeKeys() {
    LinearInterpolator interp = new LinearInterpolator(10);
    interp.put(100.0, 30.0);
    interp.put(200.0, 40.0);

    assertEquals(30.0, interp.get(100.0), 0.0);
    assertEquals(35.0, interp.get(150.0), 0.0);
    assertEquals(40.0, interp.get(200.0), 0.0);

    try {
      interp.get(99.0);
      fail();
    } catch (IndexOutOfBoundsException e) {
      assertEquals("key=99.0, min=100.0, max=200.0", e.getMessage());
    }
    try {
      interp.get(201.0);
      fail();
    } catch (IndexOutOfBoundsException e) {
      assertEquals("key=201.0, min=100.0, max=200.0", e.getMessage());
    }
  }

  private static final int N = 10 * 1000 * 1000;

  private double measure(int size) {
    LinearInterpolator interp = new LinearInterpolator(size);
    for (int i = 0; i < size; i++)
      interp.put(i, i);
    double max = interp.size() - 1;
    double sum = 0.0;
    for (int i = 0; i < N; i++)
      sum += interp.get(max * i / N);
    return sum;
  }

  @Test
  public void speed10() {
    assertTrue(measure(10) > 0.0);
  }

  @Test
  public void speed10000() {
    assertTrue(measure(10000) > 0.0);
  }

  @Test
  public void speed1000000() {
    assertTrue(measure(1000000) > 0.0);
  }
}

Так что функционал вроде работает. Я измерял скорость только в некоторых простых случаях, и они предполагают, что масштабирование будет лучше, чем линейное.

Обновление (2010-10-17T23:45+0200): я допустил несколько глупых ошибок при проверке аргумента key в LinearInterpolator, и мои модульные тесты не обнаружили их. Теперь я расширил тесты и соответствующим образом исправил код.

В библиотеке Apache commons-math, если вы реализуете UnivariateRealInterpolator и возвращаемое значение его метода интерполяции, которое имеет тип UnivariateRealFunction вы будете наиболее пути туда.

Интерфейс интерполятора принимает два массива, x[] и y[]. Возвращаемая функция имеет метод value(), который принимает значение x' и возвращает интерполированное значение y'.

Где он не может обеспечить возможности, подобные ArrayList, так это в возможности добавлять дополнительные значения в диапазон и домен, как если бы Список растет.

Кроме того, они нуждаются в некоторых дополнительных функциях интерполяции. В библиотеке для стабильной версии всего 4 реализации. Как отметил комментатор, кажется, отсутствует «линейный» или что-то еще более простое, например, ближайший сосед. Может это и не интерполяция...

Это огромное отличие от ArrayList.

То же, что и ответ Иоахима выше, но я, вероятно, реализовал бы это как двоичное дерево, и когда я не нашел то, что искал, усреднил бы значение следующего наименьшего и наибольшего значений, которые должны быть быстрыми для перехода к.

Ваше описание того, что это должно быть «как ArrayList», вводит в заблуждение, поскольку то, что вы описали, является одномерным интерполятором и по существу не имеет ничего общего с ArrayList. Вот почему вы получаете предложения для других структур данных, которые IMO отправляет вас по неправильному пути.

Я не знаю ни одного, доступного на Java (и не смог легко найти его в Google), но я думаю, вам следует взглянуть на GSL — Научная библиотека GNU, которая включает в себя сплайновый интерполятор. Это может быть немного тяжело для того, что вы ищете, поскольку это двумерный интерполятор, но кажется, что вам следует искать что-то подобное, а не что-то вроде ArrayList.

Если вы хотите, чтобы он «выглядел как ArrayList», вы всегда можете обернуть его в класс Java, который имеет методы доступа, аналогичные интерфейсу List. Однако вы не сможете реализовать интерфейс, так как объявлены методы, принимающие целые индексы.