c# - 通用线性分段查找表

Question

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

显然这并不难写，但考虑到它对许多昂贵的函数(三角函数、 yield 、距离)很有用，我认为通用函数可能已经存在。请告诉我。

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

Answer 1

我不相信 .NET 类库中直接存在任何东西。第三方库 ( like C5 perhaps ) 中可能存在某些内容。

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

// generic linear lookup class, supports any comparable type T
public class LinearLookup<T>  where T : IComparable<T>
{
    private readonly List<T> m_DomainValues = new List<T>();

    public LinearLookup( Func<T,T> domainFunc, Func<T,T> rangeFunc, 
          T lowerBound, T upperBound )
    {
        m_DomainValues = Range( domainFunc, rangeFunc, 
                                lowerBound, upperBound )
                           .ToList();
    }

    public T Lookup( T rangeValue )
    {
        // this could be improved for numeric types
        var index = m_DomainValues.BinarySearch( rangeValue );
        if( index < 0 )
            index = (-index)-1;
        return m_DomainValues[index];
    }

    private static IEnumerable<T> Range( Func<T,T> domainFunc, 
         Func<T,T> rangeFunc, T lower, T upper )
    {
        var rangeVal = lower;
        do
        {
            yield return domainFunc( rangeVal );

            rangeVal = rangeFunc( rangeVal );

        } while( rangeVal.CompareTo( upper ) < 0 );
    }
}

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

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