5

Edit3: 配列の初期化を奇数のみに制限することで最適化されています。ありがとう@ロニー！

Edit2: ありがとうございます。これ以上私にできることはないようです。

編集：PythonとHaskellが他の言語で実装されており、多かれ少なかれ同じ操作を実行すること、およびコンパイルされたCコードがいつでもそれらを打ち負かすことを知っています。標準 C (または任意のライブラリ) に、これをより高速に実行するための組み込み関数があるかどうか疑問に思っています。

Eratosthenes のアルゴリズムを使用して C で素数ふるいを実装しており、任意のサイズnの整数配列を0 からnまで初期化する必要があります。私はPythonであなたができることを知っています：

integer_array = range(n)

以上です。またはHaskellで：

integer_array = [1..n]

しかし、C で実装された類似のメソッドを見つけることができないようです。私が思いついた解決策は、配列を初期化し、それを反復処理して、その時点で各値をインデックスに割り当てますが、信じられないほど非効率的です。

int init_array()
{
    /* 
    * assigning upper_limit manually in function for now, will expand to take value for
    * upper_limit from the command line later.
    */
    int upper_limit = 100000000;
    int size = floor(upper_limit / 2) + 1;

    int *int_array = malloc(sizeof(int) * size);
    // debug macro, basically replaces assert(), disregard.    
    check(int_array != NULL, "Memory allocation error");

    int_array[0] = 0;
    int_array[1] = 2;

    int i;

    for(i = 2; i < size; i++) {
        int_array[i] = (i * 2) - 1;
    }

    // checking some arbitrary point in the array to make sure it assigned properly.
    // the value at any index 'i' should equal (i * 2) - 1 for i >= 2
    printf("%d\n", int_array[1000]);  // should equal 1999
    printf("%d\n", int_array[size-1]);  // should equal 99999999

    free(int_array);

    return 0;

error:
    return -1;
}

これを行うより良い方法はありますか？（いいえ、明らかにありません！）

4

2 に答える 2

10

私が思いついた解決策は、配列を初期化してから反復処理し、その時点で各値をインデックスに割り当てますが、非常に非効率的です。

コードの行数を減らすことはできるかもしれませんが、これは「効率」とは関係ないと思います。

Haskell と Python のコードは 1 行しかありませんが、内部で行われることは C コードと同じです (最良の場合でも、実装方法によってはパフォーマンスが大幅に低下する可能性があります)。

配列を定数値で埋めるための標準ライブラリ関数があります (そして、私はそれに賭けませんが、おそらくパフォーマンスが向上する可能性があります) が、これはここでは当てはまりません。

于 2013-07-23T02:21:16.020 に答える
9

ここでは、割り当てを最適化するという点で、より良いアルゴリズムがおそらくより良い賭けです:-

  1. ふるいの奇数をテストするだけでよいという事実を利用して、サイズ int_array_ptr を半分にします。
  2. これを数値 3、5、7 のホイール因数分解で実行して、その後の比較を 70% 以上削減します。

それは物事をスピードアップするはずです。

于 2013-07-23T02:30:46.003 に答える