0

让x进{10, 37, 96, 104}组。

让f(x)一个“选择案例”功能：

int f1(int x) {
    switch(x) {
    case 10: return 3;
    case 37: return 1;
    case 96: return 0;
    case 104: return 1;
    }
    assert(...);
}

然后，我们可以避免将条件跳转写成f(x)“整数多项式”，例如

int f2(int x) {
    // P(x) = (x - 70)^2 / 1000
    int q = x - 70;
    return (q * q) >> 10;
}

在某些情况下（仍然包括mul操作）会f2比f1（例如大型条件评估）更好。

有没有办法P(x)从switch注射中找到？

非常感谢！

4

1 回答 1

0

I suggest you start reading the Wikipedia page about Polynomial Interpolation, if you do not know how to calculate the interpolation polynomial.

Note, that not all calculation methods are suitable for practical application, because of numerical issues (e.g. divisions in the Lagrange version). I am confident that you shold be able to find a libary providing this functionality. Note that the construction will take some time too, hence this makes only sence if your function will be called quite frequently.

Be aware that integer function values and integer points of support do not imply integer coefficients for your polynomial! Thus, in the general case, you will require O(n) floating point operations, and finally a round toward the nearest integer. It may depend on your input wether the interpolation method is reliable and faster than the approach using switch.

Further, I want to propose a differnt solution, assuming that n is rather large. Why dont you put your entries (the pairs (10,3), (37,1), (96,0), (104,1) for your example) inside a serchtree (e.g. std::map in C++ or SortedDictionary in C#)? Thus, your query cost would reduce from linear to O(log n)!

于 2012-10-03T06:34:33.213 回答