是否有一个Java数据结构是一个有效的具有双索引和内置插值的ArrayList?

允许 double 相当大的变化 ArrayList 做。

原因是 因为根据定义,指数几乎是 sparse array ,这意味着它对几乎所有可能的索引都没有值(或者取决于您的定义:一个固定的已知值),只有有限数量的索引有显式的值集。

我个人会实现这样一个数据结构 skip-list (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 library ,如果您实现 UnivariateRealInterpolator 以及它的插值方法的返回值 UnivariateRealFunction 你会一直到那里。

如果它不能提供类似ArrayList的体验,那么它就能够向范围和域添加更多的值,就像 List

这和ArrayList有很大的不同。

与上面Joachim的响应相同,但我可能会将其实现为一个二叉树,当我没有找到要查找的内容时,将下一个最小值和最大值的值取平均值,这应该很快就能遍历到。

你对它应该是“像ArrayList”的描述是误导性的,因为你所描述的是一维插值器,与ArrayList没有本质上的共同点。这就是为什么你得到了其他数据结构的建议,而IMO却把你送上了错误的道路。

我不知道Java中有什么可用的(也不容易在google中找到),但是我认为您应该看看 GSL - GNU Scientific Library 其中包括 spline interpolator

如果您想让它“看起来像一个ArrayList”,那么您可以将它包装在一个Java类中,该类具有类似于List接口的访问方法。但是,您将无法实际实现接口,因为这些方法被声明为采用整数索引。