通用线性分段查找表

Question

我正在寻找一个通用的优化查找对象,它采用函数f(x)并创建一个线性分段近似,其中包含x的范围和总体间隔的可配置参数.

显然这并不难写,但鉴于它对很多昂贵的函数(trig,yield,distance)很有用,我认为通用的函数可能已经存在了.请告诉我.

另一个有用的功能是序列化/反序列化查找表,因为相当精确的100,000点+表可能需要几分钟才能构建.

Answer 1

我不相信 .NET 类库中直接存在任何内容。第三方库中可能存在某些东西（也许是 C5）。

\n\n

在 C# 中创建可以接受范围的函数的通用版本有点棘手，因为没有提供算术运算符的统一类型或接口。然而，只要有一些创造力，就可以制作一些东西：

\n\n

// generic linear lookup class, supports any comparable type T\npublic class LinearLookup<T>  where T : IComparable<T>\n{\n    private readonly List<T> m_DomainValues = new List<T>();\n\n    public LinearLookup( Func<T,T> domainFunc, Func<T,T> rangeFunc, \n          T lowerBound, T upperBound )\n    {\n        m_DomainValues = Range( domainFunc, rangeFunc, \n                                lowerBound, upperBound )\n                           .ToList();\n    }\n\n    public T Lookup( T rangeValue )\n    {\n        // this could be improved for numeric types\n        var index = m_DomainValues.BinarySearch( rangeValue );\n        if( index < 0 )\n            index = (-index)-1;\n        return m_DomainValues[index];\n    }\n\n    private static IEnumerable<T> Range( Func<T,T> domainFunc, \n         Func<T,T> rangeFunc, T lower, T upper )\n    {\n        var rangeVal = lower;\n        do\n        {\n            yield return domainFunc( rangeVal );\n\n            rangeVal = rangeFunc( rangeVal );\n\n        } while( rangeVal.CompareTo( upper ) < 0 );\n    }\n}\n

\n\n

此类将domainFunc在 [lower,upper> 范围内预先计算函数的一组域值。它使用二分搜索进行查找 - 一种允许使用任何可比较类型的折衷方案 - 而不仅仅是内置数字类型。该功能rangeFunc允许通过外部代码控制增量。因此，这里是Math.Sin在 [0,PI/2> 范围内以 0.01 为增量的线性查找：

\n\n

var sinLookup = new LinearLookup( Math.Sin, x => x + 0.01d, 0, Math.PI/2 );\nvar lookupPI4 = sinLookup[Math.PI/4]; // fetch the value sin(\xcf\x80/4)\n

\n