java - 使用查找表的线性“平滑”函数

Question

如果我想编写一个函数（可能也是一个类），它从一个不可变的查找表（在调用构造函数时修复）返回线性“平滑”数据，如下所示：

例如func(5.0) == 0.5.

---

1. 存储查找表的最佳方式是什么？

   • 我正在考虑使用两个数组。
   • 还有其他更好的方法吗？
      

2. 计算所需值的最佳方法是什么？（就实时效率而言，不包括准备时间）

   • 我正在考虑对查找表进行预排序arg并使用二进制搜索来查找最近的两个点。
   • 或者我应该建立一个二叉树来简化搜索？
   • 或者还有其他更好的方法吗？
      

3. （次要）人们将这种函数/类/数据结构/算法称为什么？在计算机科学中有任何正式的名称吗？

我想我可能需要编写自己的课程。该类充其量应该是不可变的，因为在初始化后无需更改它，并且可能会有多个线程使用它。我可能还需要通过索引获取键和值。

Answer 1

看起来您正在尝试线性插值一组点。我会用 java.util.NavigableMap. 它提供了higherEntry(K key)方便lowerEntry(K key)获取相邻点的功能。

您将您的 s 放入地图(x,y)中。查询时f(x_i)，您首先检查映射是否包含在您的地图中，如果是，则返回它。如果没有，你会打电话higherKey(x_i)并lowerKey(x_i)找到相邻的两个点。然后使用公式对这两点进行插值（参见 维基百科的线性插值页面）。

我还将在不同的类中实现插值逻辑，并将其作为构造函数参数传递给你的function类，以防你以后想使用不同的插值方法（即多项式插值）。