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

補間多項式の計算方法がわからない場合は、多項式補間に関するウィキペディアのページを読み始めることをお勧めします。

すべての計算方法が実際の適用に適しているわけではないことに注意してください。これは、数値の問題 (例: ラグランジュ版の除算) のためです。この機能を提供するライブラリを見つけることができると確信しています。構築にも時間がかかることに注意してください。したがって、これは、関数が頻繁に呼び出される場合にのみ意味があります。

整数関数値と整数サポート ポイントは、多項式の整数係数を意味しないことに注意してください。したがって、一般的なケースでは、O(n) 浮動小数点演算が必要になり、最後に最も近い整数への丸めが必要になります。補間法が信頼性が高く、スイッチを使用するアプローチよりも高速であるかどうかは、入力に依存する場合があります。

さらに、nがかなり大きいと仮定して、別の解決策を提案したいと思います。エントリ (たとえば、(10,3)、(37,1)、(96,0)、(104,1) のペア) を serchtree (たとえば、C++ の std::map またはC#)? したがって、クエリのコストは線形から O(log n)! に削減されます。

于 2012-10-03T06:34:33.213 に答える