6

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

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

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

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

  4. 请仅提供免费代码。

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

当JDK、Apache Commons或其他标准库中可能已经有这样的东西时，我试图避免花费大量时间来推出我自己的解决方案。坦率地说，这正是让这个遗留代码进入它现在所处的情况的方法......

在免费提供的图书馆中有这样的东西吗？

4

5 回答 5

4

允许double值作为索引是一个相当大的变化ArrayList。

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

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

就我个人而言，我会将这样的数据结构实现为带有适当插值的元组的跳过列表（或类似的快速搜索数据结构） 。(index, value)

编辑：实际上后端存储有一个很好的匹配（即除了插值之外的所有内容）：只需使用 aNavigableMap来TreeMap存储从索引到值的映射。

有了它，您可以轻松地使用ceilingEntry()and （如有必要）higherEntry()获得最接近您需要的索引的值，然后从中进行插值。

于 2010-04-20T14:35:39.093 回答
3

如果您当前的实现具有用于插值的复杂度 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，我的单元测试没有发现它们。现在我扩展了测试并相应地修复了代码。

于 2010-10-17T09:04:55.030 回答
1

在Apache commons-math library中，如果您实现UnivariateRealInterpolator及其类型为UnivariateRealFunction的 interpolate 方法的返回值，那么您将大部分时间在那里。

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

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

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

于 2010-09-29T20:13:16.863 回答
0

您对它应该“像 ArrayList”的描述具有误导性，因为您所描述的是一维插值器，与 ArrayList 基本上没有任何共同之处。这就是为什么您会收到有关 IMO 将您送入错误路径的其他数据结构的建议。

我不知道 Java 中有任何可用的东西（并且无法轻易找到一个 google），但我认为您应该看看GSL - GNU Scientific Library其中包括一个spline interpolator。由于它是一个二维插值器，因此对于您要查找的内容可能有点沉重，但是您似乎应该寻找类似的东西而不是类似 ArrayList 的东西。

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

于 2010-04-20T14:59:01.060 回答
0

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

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

于 2010-04-20T14:37:46.873 回答