5

Project Euler の質問とループ展開を使用した最適化について質問があります。

問題の説明: 2520 は、1 から 10 までの各数字で割り切れる最小の数字です。1 から 20 までのすべての数で割り切れる最小の正の数は?

解決：

#include <iostream>
#include <limits.h>
#include <stdio.h>
#include <time.h>

using namespace std;

int main() {

    clock_t startTime = clock();

    for (int i = 1; i < INT_MAX; i++)
    {
        bool isDivisible = true;

        //CODE BLOCK #1
        /*for (int j = 2; j <= 20; j++)
        {
                if ( i % j != 0)
                {
                        isDivisible = false;
                        break;
                {
        }*/

        //CODE BLOCK #2
        /*if (i % 2 != 0 || i % 3 != 0 ||
                i % 4 != 0 || i % 5 != 0 ||
                i % 6 != 0 || i % 7 != 0 ||
                i % 8 != 0 || i % 9 != 0 ||
                i % 10 != 0 || i % 11 != 0 ||
                i % 12 != 0 || i % 13 != 0 ||
                i % 14 != 0 || i % 15 != 0 ||
                i % 16 != 0 || i % 17 != 0 ||
                i % 18 != 0 || i % 19 != 0 ||
                i % 20 != 0 )
                isDivisible = false;*/

        if (isDivisible)
        {
                cout << "smallest: " << i << endl;

                cout << "Ran in: " << clock() -  startTime  << " cycles" << endl;
                break;
        }
    }

return 0;
}

ここで、CODE BLOCK #1 または CODE BLOCK #2 のいずれかをコメントアウトすると、正しい答え (232792560) が得られます。ただし、CODE BLOCK #2 は CODE BLOCK #1 よりもはるかに高速です。

コード ブロック #1: 3,580,000 サイクル (コード ブロック #1 にブレークを追加したところ、はるかに高速に実行されます。ただし、複合 IF ステートメントよりも大幅に低速です。)

コードブロック #2: 970,000 サイクル

この大きなパフォーマンスの違いが発生する理由を知っている人はいますか?

4

2 に答える 2

7

||1 つが真になるとすぐに、残りの条件は計算されないという手段を使用します。これは次のループと同等です。

    for (int j = 2; j <= 20; j++)
    {
        if ( i % j != 0){
            isDivisible = false;
            break;
        }
    }

これを試してみると、実行時間の差が縮まっていることに気付くかもしれません。他の違いはループ オーバーヘッドに起因する可能性がありますが、コンパイラで最適化がオンになっていると、同じ速度で実行されると思います (少なくとも、はるかに似た時間になります)。

EDIT 新しいパフォーマンスの違いについて:
定数による数値の割り切れる可能性をチェックする最適化された方法は多数ありNます。 コンパイラはこれらの小さなトリックをたくさん知っており、2 番目のコード ブロックではおそらくそれらの割り切れるチェックのすべてではないにしても、ほとんどを最適化できます (それらはユーザーによって直接書き出されるため)。一方、最初のコード ブロックでは、最初にループしてから、さまざまなチェックについて推論する前に、ループ変数を定数に置き換えます。 この違いにより、ブロック 1 よりもブロック 2 のコードが最適化されている可能性があります。i % N != 0i & (N-1)

于 2013-11-08T19:27:29.510 に答える