-2

私はアルゴリズムに取り組んでおり、コードをより効率的にしたいと考えています.私のコードは単純な算術演算と比較ステートメントを使用しています.ただし、時間がかかる可能性があるため、ifステートメントを置き換えたいと考えています.このコードは100万回以上実行されます.わずかな改善でも大歓迎です。答えてください!コードは次のとおりです- 

int_1024 sqcalc(int_1024 s,int_1024 f){
    f=f*20;
    s=s-81;
    s=s-(f*9);
    if(s>=0){
        return 9;
    }
    s=s+f;
    s=s+17;
    if(s>=0){
        return 8;
    }
    s=s+f;
    s=s+15;
    if(s>=0){
        return 7;
    }
    s=s+f;
    s=s+13;
    if(s>=0){
        return 6;
    }
    s=s+f;
    s=s+11;
    if(s>=0){
        return 5;
    }
    s=s+f;
    s=s+9;
    if(s>=0){
        return 4;
    }
    s=s+f;
    s=s+7;
    if(s>=0){
        return 3;
    }
    s=s+f;
    s=s+5;
    if(s>=0){
        return 2;
    }
    s=s+f;
    s=s+3;
    if(s>=0){
        return 1;
    }
    s=s+f;
    s=s+1;
    if(s>=0){
        return 0;
    }
}

if チェックを置き換えたいのは、アルゴリズムが遅くなると「思う」からです。何か提案はありますか?int_1024 は 1000 のビットを持つ ttmath 変数なので、それを節約することは良いオプションかもしれません?そのような大きな数の除算または乗算は遅いので足し算でやってみましたがだめでした。助けてください。

4

4 に答える 4

7

より速いかどうかはわかりませんが、かなり短くなっています (そして分析しやすくなっています)。

int k[] = { 17, 15, 13, 11, 9, 7, 5, 3, 1 };
int r = 0;
f *= 20;
s -= 81;
s -= f * 9;
while (s < 0) {
    s += f;
    s += k[r];
    if (++r == 9) break;
}
if (s >= 0) return 9-r;

編集:k実際、元の投稿者は、配列内の定数の合計を事前に計算し、sそれらを に段階的に追加するのではなく、合計と比較すること により、このループを最適化する巧妙な方法を思いつきましたs。

編集: Moonshadow の分析手法に従いましたが、別の方程式にたどり着きました。元の TeX フォーマットは ASCII アートに置き換えられました (MathJax に TeX をレンダリングさせようとしましたが、うまくいきませんでした):

S[0] = s                      >= 0 => 9 - 0
S[1] = S[0]   + f + 19 - 2*1  >= 0 => 9 - 1
S[2] = S[1]   + f + 19 - 2*2  >= 0 => 9 - 2
...
S[i] = S[i-1] + f + 19 - 2*i  >= 0 => 9 - i

計算するにはS[n]：

    S[n] = S[n-1] + f + 19 - 2n
               .-- n
=>  S[n] = s +  >      (f + 19 - 2*i)
               `-- i=1       .-- n
=>  S[n] = s + n(f + 19) - 2  >      i
                             `-- i=1
=>  S[n] = s + n(f + 19) - n(n+1)
                            2
=>  S[n] = s + n(f + 18) - n

したがって、不等式S[n] >= 0は の二次方程式ですn。と仮定すると、二次方程式の解の上限にs < 0なりたいと思います。n

    +--                         --+
    |               _____________ |
    |             /        2      |
    | f + 18 - . / (f + 18) + 4s  |
    |           `                 |
n = | --------------------------- |
    |             2               |

したがって、ルーチンは次のようになります。

f *= 180;
s -= 81;
s -= f;
if (s >= 0) return 9;
f /= 9;
f += 18;
s *= 4;
int1024_t ff = f;
ff *= f;
ff += s;
ff = ff.Sqrt();
f -= ff;
f += f.Mod2();
return 9 - f/2;

ただし、大きな整数オブジェクトに対してこれらの操作を実行する費用が、上記の単純なループを置き換えるために実装する価値があるかどうかはわかりません。(関数を拡張する予定があり、はるかに長いループが必要な場合を除きます。)

ループよりも高速にするには、大整数の平方根の実装は常に 4 回の反復以内に収束して、既存の while ループの予想平均 4.5 回の反復を上回る必要があります。ただし、ttmath実装は整数の平方根を計算していないようです。浮動小数点の平方根を計算してから結果を丸めているようですが、これはループよりもはるかに遅いと思います。

于 2012-06-08T16:15:42.203 に答える
6

まず、final の条件if()が false の場合、戻り値は未定義であることに注意してください。おそらくそれを修正したいでしょう。

さて、関数はで始まります

f=f*20;
s=s-81;
s=s-(f*9);
if(s>=0){
    return 9;
}

残りは信じられないほど反復的に見えます。その繰り返しが使えるか見てみましょう。不等式の表を作成しましょう - s の値と最終的な結果:

s + (f+17) >= 0: 8
s + (f+17) + (f+15) >= 0: 7
s + (f+17) + (f+15) + (f+13) >= 0: 6
.
.
s + (f+17) + (f+15) + (f+13) + ... + (f+1) >= 0: 0

したがって、各行は、s + f の倍数 + 定数が 0 より大きいかどうかをテストします。返される値、定数と f の倍数はすべて関連しているように見えます。関係を表現してみましょう。

(s + ((9-n)*f) + (2*n)-1 >= 0)

n が片側になるように並べ替えてみましょう。

(s + (9*f) - (n*f) + (2*n)-1 >= 0)

(s + (9*f) +1 >= (n*f) - (2*n))

(s + (9*f) +1 >= n*(f - 2))

n <= ((s + (9*f) +1) / (f - 2)

現在、この関数には、さまざまな入力に対する戻り値の範囲があります。実際、n0..8 の範囲の値に関心があります。提供される関数は、出力される入力に対して定義されていませんn < 0(上記を参照)。プリアンブルにより、生成される入力が表示されないことが保証されn > 8ます。だから私たちはただ言うことができます

int_1024 sqcalc(int_1024 s,int_1024 f){
    f=f*20;
    s=s-81;
    s=s-(f*9);
    if(s>=0){
        return 9;
    }
    return (s + (9*f) +1) / (f - 2);
}

結果が未定義ではないすべてのケースで、動作は古いバージョンと同じである必要があり、大量の条件やループは必要ありません。

精度のデモはhttp://ideone.com/UzMZsにあります。

于 2012-06-08T16:33:24.563 に答える
0

OPのコメントによると、関数は不等式を満たすすべての値を見つけようとしています: 

N * ((20 * F) + N) <= S

すべての N に対して、F と S が与えられます。

代数を使用すると、次のようになります。 

1) N^2 + 20Fn - S <= 0  (where N^2 is N*N or sqr(N))

OPは、FとNにいくつかの定数を使用し、代数的に解く（sp？）か、Webで「C ++ find root quadratic equation」を検索する必要があります。

関数を 1 つ選択し、関数をプロファイリングして、必要に応じて最適化します。

于 2012-06-09T18:52:21.740 に答える
0

私は二次方程式を解こうとしましたが、数字が大きいほど関数が遅くなります.@ user315052の回答に従って、このコードを作成しました。

    int_1024 sqcalc(int_1024 s,int_1024 f){
int k[] = { 0, 17, 32, 45, 56, 65, 72, 77, 80, 81 };
f=f*20;
s=((f*9)+81)-s;
int i=0;
while(s>k[i]){
s-=f;
i++;
}
return 9-i;
}

このコードでは、数値を減算してからゼロと比較する代わりに、数値と直接比較します。これにより、最速の結果が得られます。ただし、バイナリ検索を実行できます....

于 2012-06-10T16:50:52.823 に答える