3

私は、2 の 4,500,000 乗程度の非常に大きな数で動作するアルゴリズムを持っています。これらの数値を処理するには、.NET 4 の BigInteger クラスを使用します。

このアルゴリズムは非常に単純で、あらかじめ定義された基準に基づいて大きな初期数を減らす単一のループです。反復ごとに、数値は約 10 の指数で減少するため、4,500,000 は次の反復で 4,499,990 になります。

現在、1 秒あたり 5.16 回の反復、または 1 回の反復あたり 0.193798 秒を取得しています。それに基づいて、アルゴリズムの合計時間は、指数値を 0 にするのに約 22 時間かかるはずです。

問題は、数値が減少するにつれて、メモリ内の数値を処理するのに必要な時間も減少することです。さらに、指数が 200,000 の範囲に減少すると、1 秒あたりの反復回数が膨大になり、反復ごとの減少も指数関数的に増加します。

アルゴを 1 日実行する代わりに、最初の開始数と 1 秒あたりの反復回数に基づいてどれくらいの時間を計算するかを計算する数学的な方法はありますか?

最適化の試みの改善をすばやく測定できるため、これは非常に役立ちます。

次の疑似コードを検討してください。

double e = 4500000; // 4,500,000.
Random r = new Random();
while (e > 0)
{
    BigInteger b = BigInteger.Power(2, e);
    double log = BigInteger.Log(b, 10);
    e -= Math.Abs(log * r.Next(1, 10));
}
4

2 に答える 2

1

最初の書き換え

double log = BigInteger.Log(b, 10);

なので

double log = log(2)/log(10) * e; // approx 0.3 * e

次に、アルゴリズムが O(1) 回の反復後に終了することに気付きます (各反復で約 70% の終了確率)。おそらく、最初の反復以外のすべてのコストを無視できます。

アルゴリズムの総コストはMath.Pow(2, e)、初期指数の約 1 ～ 2 倍eです。base=2 の場合、これは自明なビットシフトです。それ以外の場合は、2 乗と乗算が必要になります。

于 2013-02-13T12:06:28.540 に答える
-1

ランダムを使用しているため、未知の時間を推定する方法はありません!

于 2013-02-13T11:50:23.583 に答える