是否有一种 Java 数据结构实际上是具有双索引和内置插值的 ArrayList？

Question

我正在寻找具有以下特征的预构建 Java 数据结构：

1. 它应该看起来像 ArrayList，但应该允许通过双精度而不是整数进行索引。请注意，这意味着您可能会看到与原始数据点不相符的索引（即要求与键“1.5”对应的值）。 编辑：为了清楚起见，根据评论，我不打算更改 ArrayList 实现。我正在寻找类似的界面和开发人员体验。

2. 因此，返回的值可能会被插值。例如，如果键为 1.5，则返回的值可能是键 1.0 处的值和键 2.0 处的值的平均值。

3. 键将被排序，但值不保证单调递增。事实上，无法保证值的一阶导数是连续的（使其不太适合某些类型的样条线）。

4. 仅提供免费代码。

为了清楚起见，我知道如何写这样的东西。事实上，我们已经在遗留代码中实现了这个和一些相关的数据结构，由于一些性能和编码问题，我想替换它们。

我试图避免的是花费大量时间来滚动我自己的解决方案，而 JDK，Apache Commons或另一个标准库。坦率地说，这正是使这些遗留代码陷入现在困境的方法......

免费提供的库中有这样的东西吗？

Answer 1

允许 double 值作为索引是对 ArrayList 所做的相当大的改变。

这样做的原因是，以 double 作为索引的数组或列表几乎根据定义是 稀疏数组，这意味着它对于几乎所有可能的索引没有值（或者取决于您的定义：固定的已知值），并且只有有限数量的索引具有显式值集。

Java SE 中没有预构建的类支持所有这些。

就我个人而言，我会实现这样一个数据结构：skip-list（或类似的具有适当插值的（索引，值）元组的快速搜索数据结构。

编辑：实际上，后端存储有一个非常好的匹配（即除了插值之外的所有内容）：只需使用 < code>NavigableMap 例如 TreeMap 存储从索引到值的映射。

这样您就可以轻松使用 < code>ceilingEntry() 和（如有必要）higherEntry() 获取最接近您需要的索引的值，然后从中进行插值。

Answer 2

如果您当前的实现插入值的复杂度为 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): 我在检查 LinearInterpolator 中的 key 参数时犯了一些愚蠢的错误，我的单元测试没有发现它们。现在我扩展了测试并相应地修复了代码。

Answer 3

在 Apache commons-math 库中，如果您实现 UnivariateRealInterpolator 及其 interpolate 方法的返回值（输入 < a href="http://commons.apache.org/math/api-2.0/org/apache/commons/math/analysis/UnivariateRealFunction.html" rel="nofollow">UnivariateRealFunction 你会最那里的路。

插值器接口采用两个数组：x[] 和 y[]。返回的函数有一个方法 value()，它接受 x' 并返回插值后的 y'。

它无法提供类似 ArrayList 的体验的地方在于能够向范围和域添加更多值，就像 列表 正在增长。

此外，他们似乎需要一些额外的插值函数。稳定版本库中只有 4 个实现。正如评论者指出的那样，它似乎缺少“线性”或更简单的东西，例如最近邻居。也许这不是真正的插值......

Answer 4

这是与 ArrayList 相比的巨大变化。

与上面 Joachim 的响应相同，但我可能会将其实现为二叉树，当我没有找到我正在寻找的东西时，对下一个最小值和最大值的值进行平均，这应该可以快速遍历到。

Answer 5

您关于它应该“像 ArrayList”的描述具有误导性，因为您所描述的是一维插值器，并且本质上与 ArrayList 没有任何共同点。这就是为什么您会收到有关其他数据结构的建议，而 IMO 却将您引向了错误的道路。

我不知道 Java 中有任何可用的（并且无法轻松找到一一谷歌），但我认为您应该看看 GSL - GNU 科学库 其中包括 样条插值器。对于您正在寻找的东西来说，它可能有点重，因为它是一个二维插值器，但似乎您应该寻找这样的东西，而不是像 ArrayList 这样的东西。

如果您希望它“看起来像 ArrayList”，您始终可以将其包装在 Java 类中，该类具有与 List 接口类似的访问方法。但您将无法实际实现该接口，因为这些方法被声明为采用整数索引。