21

配列（望ましい整数配列）のすべての要素が等しいかどうかを確認する最速の方法は何ですか。これまで、次のコードを使用してきました。

bool check(int array[], int n)
{   
    bool flag = 0;

    for(int i = 0; i < n - 1; i++)      
    {         
        if(array[i] != array[i + 1])
            flag = 1;
    }

    return flag;
}
4

12 に答える 12

28 
int check(const int a[], int n)
{   
    while(--n>0 && a[n]==a[0]);
    return n!=0;
}
于 2013-01-02T10:34:50.190 に答える
13

一致しない要素を見つけたら、ループから抜け出すことができます。

bool check(const int array[], int n)
{   
    for (int i = 0; i < n - 1; i++)      
    {         
        if (array[i] != array[i + 1])
            return true;
    }
    return false;
}

これがパフォーマンスにとって重要な場合は、次のようにさらに最適化できます。

bool check(const int array[], int n)
{   
    const int a0 = array[0];

    for (int i = 1; i < n; i++)      
    {         
        if (array[i] != a0)
            return true;
    }
    return false;
}
于 2013-01-02T10:26:02.220 に答える
4

配列をより大きなデータ型に再キャストします。たとえば、64ビット整数で動作するか、128ビットまたは256ビット演算にSSEまたはAVX組み込み関数を使用します。たとえば、SSE2組み込み関数は_mm_cmpeq_epi32であり、その結果は_mm_or_si128で使用します。_mm_srli_si128と_mm_cvtsi128_si32を繰り返し適用して結果を確認します。早期終了のために、数百回の反復ごとに結果を確認してください。

必ず整列されたメモリを操作し、整列されていない開始と終了をintとしてチェックし、最初にパックされた要素をそれ自体でチェックしてください。

于 2013-01-02T11:24:03.893 に答える
0

return false;これは基本的に O(n) 操作であるため、フラグを省略し、最初の失敗時とreturn true;反復後に行う以外に、これ以上のことはできません。

于 2013-01-02T10:28:04.077 に答える
0

理論的には、私はこれを提案します：

bool check_single(const int a[], int n)
{
    for (int i = 1; i < n; ++i) {
        if (a[0] != a[n]) { return false; }
    }
    return true;
}

他の (既に提案されている) バージョンとの比較:

  • a[0]コンパイラによってループの外に持ち上げられます。つまり、ループ内の単一の配列アクセスを意味します
  • 0 から n までループします。これは、ロードa[0]してからループするよりも (アクセスに関して) 優れています。a[n]

明らかに、それでも N 個の要素をチェックするため、O(N) です。

于 2013-01-02T13:30:39.853 に答える
0 
bool check(int array[],int n)
{       
  // here 1st element is checked with others. This decreases the number of iteration by 1.
  // also it returns immediately. 
  // The requirement is to check if all the elements are equal. 
  // So if 1st element is equal to others then all elements are equal. 
  // Otherwise the  elements are not equal.
  for(int i=1;i<n;i++)      
  {         
    if(array[0]!=array[i])
      return false;
  }        
  return true;
}
于 2013-01-02T10:28:37.447 に答える
0

スレッド化または並列 for ループをサポートするプラットフォームで利用可能なライブラリを見つけ、異なるコアが配列の異なる範囲をテストするように計算を分割します。

利用可能なライブラリの一部を次に示します。

http://parallel-for.sourceforge.net/parallelfor.html

あるいは、多くの GPU が提供する並列処理を利用することもできます。

于 2013-01-02T10:36:25.973 に答える
-2 
bool check_identity (int a[], int b[], const int size)
{
    int i;
    i = 0;
    while ((i < size-1) && (a[i] == b[i]))   i++;

    return (a[i] == b[i]);

}
于 2015-12-19T00:22:57.203 に答える