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 检查结果。每几百次迭代检查一次结果以便提前退出​​。

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