c++ - C++：检查所有数组元素是否相等的最快方法

Question

检查数组（首选整数数组）的所有元素是否相等的最快方法是什么。到目前为止，我一直在使用以下代码：

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;
}

Answer 1

int check(const int a[], int n)
{   
    while(--n>0 && a[n]==a[0]);
    return n!=0;
}

Answer 2

这是一个有效的 C++11 的可靠解决方案。优点是您不需要手动使用索引或迭代器。这是一个最佳实践

喜欢算法调用而不是手写循环 [Herb Sutter - C++ 编码标准]

我认为这与 Paul R 的解决方案同样有效。

bool check(const int a[], int n)
{
      return !std::all_of(a, a+n, [a](int x){ return x==a[0]; });
}

Answer 3

一旦你找到了一个不匹配的元素，你就可以跳出循环：

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;
}

Answer 4

将数组重新转换为更大的数据类型。例如，对 64 位整数进行操作，或使用 SSE 或 AVX 内在函数进行 128 位或 256 位操作。例如，SSE2 内在函数是 _mm_cmpeq_epi32，您将使用 _mm_or_si128 的结果。重复应用 _mm_srli_si128 和 _mm_cvtsi128_si32 检查结果。每隔几百次迭代检查一次结果，以便提前退出​​。

确保对对齐的内存进行操作，将未对齐的开始和结束检查为整数，并检查第一个打包元素本身。

Answer 5

return false;我们将它基本上是一个 O(n) 操作，所以除了放弃标志并且仅在第一次失败和return true;迭代之后，你不能做得比你所拥有的更好。

Answer 6

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;
}

Answer 7

在您的平台上找到一个支持线程或并行 for 循环的库，并将计算分开，以便不同的内核测试不同范围的数组。

这里列出了一些可用的库：

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

或者，您可以利用许多 GPU 提供的并行性。

Answer 8

理论上，我会提出这个建议：

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)。

Answer 9

为了程序员的效率，您可以在一行中尝试以下所有操作。

vector<int> v{1, 1, 1, 1};
all_of(v.cbegin(), v.cend(), [&r=v[0]](int value){ return value == r; }->bool);

我没有测试运行这段代码，如果有语法错误请告诉我。

Answer 10

快速哈希映射技术：

bool areSame(int a[],int n)
{
    unordered_map<int,int> m; //hash map to store the frequency od every

    for(int i=0;i<n;i++)
       m[a[i]]++;
      
    if(m.size()==1)
       return true;
    else
       return false;
}

Answer 11

我认为以下内容比评分最高的答案更具可读性，我也会打赌更有效率（但尚未进行基准测试）

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

    return true;    //change to false for the OPs logic.  I prefer logical true here
}

Answer 12

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]);

}