使用查找表线性"平滑"功能

Question

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

例如func(5.0) == 0.5.

---

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

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

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

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

3. (次要)人们会称这种函数/类/数据结构/算法是什么？计算机科学中是否有正式名称？

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

Answer 1

看起来你正试图线性插值一组点.我用了 java.util.NavigableMap.它提供的功能,如higherEntry(K key)和lowerEntry(K key)这有利于获得邻近点.

你把地图放进了地图(x,y).查询时f(x_i),首先检查地图中是否包含映射,如果是,则返回.如果不是,你打电话higherKey(x_i),lowerKey(x_i)找到邻近的两点.然后使用公式来插入这两个点(参见 维基百科的线性插值页面).

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