3

私は友人から、私が過去に遭遇したことを共有するように求められました. 元の投稿はここから取得されます。問題文はここにあります。基本的にはアルゴリズム競技用のサイトです。

次のコードを使用して解決したアルゴリズムの問​​題に直面しました。

double dp[80002][50];
class FoxListeningToMusic {
public:
    vector <double> getProbabilities(vector <int> length, int T)  {    
        memset(dp, 0, sizeof(dp));
        int n = length.size();
        for(int i = 0; i < n; i++)
            dp[0][i] = 1.0 / (double)n;

        double mul = 1.0 / (double)n;
        int idx ;
        for(int i = 1; i <= T; i++) {
            for(int j = 0; j < n; j++)  {
                idx = i - length[j];
                if(idx >= 0)  {
                    for(int k = 0; k < n; k++)
                        dp[i][k] += mul * dp[idx][k];
                }
                else
                    dp[i][j] += mul;
                }
            }
        }

        vector<double> v(n);
        for(int i = 0; i < n; i++)
            v[i] = dp[T][i];
        return v;
    }

};

少なくともこれから説明することについては、コードが正しい答えで問題を解決しているかどうかは重要ではありません。実際、このコードには時間制限がありました (つまり、一部のテスト ケースでは 2 秒以上実行されました)。ここでの複雑さは O(T * length.size() ^ 2) であるため、問題の制約を考慮に入れると 2 * 10 8になるので、これはどういうわけか予想されました。ただし、興味深いのは、特に時間制限に対してソリューションをテストしたことです。私が使用したケースは、私のソリューションでは「最悪のケース」のようです: 長さ 50 1 で、T = 80000 です。コードは 0.75 秒間実行されました。これは制限時間の 2 秒をかなり下回っています。

実行される命令の数は分岐条件 idx >= 0 のみに依存するため、私が使用したケースは最悪のケースです。これが真の場合、もう 1 つのサイクルが実行されます (サイクルの複雑度は O(n) です)。それ以外の場合、単一の操作 O(1) のみが実行されます。ご覧のとおり、要素の長さが短いほど、これが真になる回数が多くなります。

この理由にもかかわらず、次のケースでテストした後、私の問題は失敗します。

length = {1, 1, 1, 1, 3, 3, 3, 3, 1, 3, 3, 2, 3, 2, 3, 3, 1, 2, 3, 1, 2, 3, 2,
          1, 3, 1, 1, 1, 2, 3, 2, 3, 2, 2, 1, 3, 1, 1, 3, 1, 3, 1, 3, 2, 3, 1,
          1, 3, 2, 76393} T= 77297.
For this case my program runs for 5.204000 seconds.

私の最初の仮定は、ランタイム測定値のこの予期しない比率の理由は (最初のケースで実行されるプロセッサ命令がかなり少ないと予想される限り)、プロセッサが何らかの方法で同様の計算をキャッシュするためであるということでした: 私の例では、計算長さのすべての要素に関して対称であり、本当に賢いプロセッサはこれを使用して、同じ命令シーケンスの繰り返しを省くことができます。そこで、別の例を作成してみました。今回は、長さ配列に異なる値を使用します。

length = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
          21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38,
          39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 77943}
T=80000 runs for  0.813000 seconds.

この例の後、これらの時間測定がどのように行われたかを言うことができなくなりました.2番目の例では、失敗したテストよりも多くのプロセッサ命令が必要なようで、最初の例で起こっていると思っていたキャッシュが許可されていません. 実際、私はこの動作の原因を特定できていませんが、プロセッサ キャッシュまたはコンベヤーのいずれかに関係があるはずだと確信しています。私はこれらの実験が異なるチップセットでどのように動作するか非常に興味があるので、ここに自由にコメントしてください.

また、私よりもハードウェアに詳しい人がいて、この動作を説明できる人がいれば、感謝します。

それまでは、自分自身のために注意しなければならないことがあります。アルゴリズムの複雑さを見積もるときは、プロセッサの最適化を過小評価しないでください。場合によっては、特定の例の償却速度が大幅に減少/増加するように見えることがあります。

4

2 に答える 2

7

この奇妙な動作の理由は、非正規数であることが判明しました。そのような数値を純粋なゼロとして扱うコードを配置すると、そのようなまれなケースでコードが大幅に高速化されました。

ヒント: この場合の非正規数は、かなりゼロに近い数値です (たとえば、浮動小数点数の場合は 10 -38。@PascalCuoq による補正)。このような数値の場合、プロセッサの処理が大幅に遅くなります: (ウィキペディアから取得):

一部のシステムでは、正常値と同じようにハードウェアで非正規値を処理します。他のものは、ハードウェアで正常値とゼロのみを処理し、システム ソフトウェアに非正規値の処理を任せます。ソフトウェアで非正規値を処理すると、常にパフォーマンスが大幅に低下します。

編集また、SOでこの提案を見つけました。数値が異常になったかどうかを確認する方法。

于 2013-10-12T10:17:45.977 に答える