java - 线性 "smoothed"函数使用查找表

Question

如果我想编写一个函数(可能也是一个类)，它从不可变的查找表(调用构造函数时固定)返回线性“平滑”数据，如下所示:

例如func(5.0) == 0.5。

---

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

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

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

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

3. (Minor) 这种函数/类/数据结构/算法应该叫什么？这在计算机科学中有正式名称吗？

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

Answer 1

看起来您正在尝试对一组点进行线性插值。我会使用 java.util.NavigableMap。它提供了higherEntry(K key)和lowerEntry(K key)等函数，方便获取相邻点。

您将 (x,y) 放入 map 中。当查询 f(x_i) 时，您首先要检查映射是否包含在您的 map 中，如果是，则返回它。如果不是，您将调用 higherKey(x_i) 和 lowerKey(x_i) 来查找相邻的两个点。然后使用公式对这两点进行插值(参见 Wikipedia's Linear Interpolation Page ).

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