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

- Harish Vishwakarma

---

在循环中直接返回false，在循环下方返回true，这样就不需要使用flag了。否则我认为这已经是最有效率的写法了。 - Ivaylo Strandjev

为什么要将“1”和“0”分配给布尔值(bool)？ - Christian Rau

@ChristianRau：人们就是这样有趣，他们看到像C++这样的弱类型语言就会疯狂。有些人甚至会将0和1赋值给long，依赖于隐式转换！ - Steve Jessop

@NoSenseEtAl 你是指用 memcmp 来比较两个 int 吗？我不这么认为。只是为了确认，你不是那些认为他想要比较两个范围的人之一吧？ - Christian Rau

Answer 1

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

- CubeSchrauber

---

所以针对他错误使用bool类型的做法，你只是将返回类型改为int，以确保安全？;) - Christian Rau

好的，在这种情况下，这将与实际问题无关，不是吗？不过，我还是点了赞 ;) - Christian Rau

如果您觉得使用递减的索引很吸引人，我建议不要将a[0]作为常量。您开始比较位于数组两端的a[0]和a[length-1]，这需要进行两次RAM往返（对于长度超过64个字节的数组），才能开始比较。 - Matthieu M.

优秀的代码。我会将 n!=0 改为 n>0，以处理 n=0 的情况。 - Aleksandr Dubinsky

我们能否得到一些性能比较，与Paul R的答案相比？ - Aleksandr Dubinsky

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

- Gabor Marton

---

凭借我在Core i5上粗略的单元测量技能，这个实现似乎以每个元素约0.7纳秒的速率进行检查，这相当快但可信。你试过像Paul R那样将a [0]提升出循环吗？当我这样做时，它下降到每个元素6.4e-10纳秒，这让我感到难以置信。我认为我犯了一个错误，并且我的粗略测量不再捕捉第二种情况中的计算。还有其他人有测量结果吗？ - Jeremy W. Murphy

Herb Sutter真的说过“算法调用”吗？还是类似于“标准库调用”？有引用吗？ - user207421

Herb Sutter, Andrei Alexandrescu - C++ 编码标准：101 条规则、指南和最佳实践， 出版商：Addison-Wesley Professional；第 1 版（2004 年 11 月 4 日）， ISBN-10：9780321113580， 第 162 至 164 页。 - Gabor Marton

这也适用于数组为空的情况（即当 n 为零时）。 - JFMR

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

- Paul R

---

是的，那肯定会让它更快。谢谢，我下次发布时会注意代码格式。 - Harish Vishwakarma

使用一个常量元素（通常是第一个元素）来将所有其他元素与其进行比较，可以让编译器在循环外提前加载该元素。不过不确定会有多大的影响。 - Matthieu M.

Answer 4

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

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

- Aleksandr Dubinsky

---

也许我们可以重用glibc的memcmp（已经进行汇编优化），具体如下：1）将数组分成两个大小相等的部分。2）比较它们3）如果不同，则返回false。否则，取第一半，忽略第二半4）将第一半分成两半5）...这样只需要进行N次比较。 - Ciro Santilli OurBigBook.com

Answer 5

为了提高程序员的效率，您可以尝试以下一行代码。

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

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

- Kemin Zhou

Answer 6

我认为以下代码比最高评分的答案更易读，而且我敢打赌它也更有效率（但我还没有进行基准测试）

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
}

- James

---

绝对相反是正确的，我敢打赌更加高效。 - B001ᛦ

Answer 7

理论上，我会提出这个：

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

- Matthieu M.

---

如果任意两个元素相等，则返回“true”。也许您想要将相等检查变为不等检查？ - xtofl

你更倾向于单状态布尔值吗？ - xtofl

@xtofl：没错！完全正确！:D - Matthieu M.

Answer 8

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

- Narendra

---

这是错误的。它只比较数组的第一个和第二个元素，然后立即退出。 - Gorpik

如果按照这种方式操作，应该是for(int i=1;i<n;i++)，而else会导致中断。return 1应该出现在循环外部，并且1/0需要反转，当不相等时应该返回1，如果全部相等则返回0。 - Gary.S

还是有问题 - 提示：一个return语句放错了位置。 - Paul R

应该返回 true/false 而不是 0/1，注意返回类型是 bool。 - billz

最终，这根本不会减少迭代次数。表面上看，与第一个元素进行比较可能会减少内存访问，但最终array[i-1]应该已经在缓存中了（如果编译器还没有进行一些优化的话）。 - Christian Rau

Answer 9

基本上这是一个O(n)操作，所以除了放弃标志并在第一次失败时return false;，在迭代后return true;，你不能做得更好。

- Anders R. Bystrup

---

仅仅因为它是O(n)并不意味着它不能被优化。说这种话太无意义了。 - Aleksandr Dubinsky

请解释一下我说的“无意义的事情”。运行时间的上限始终为O(n)，我的建议是在第一个不匹配时立即失败，这是一个相当不错的优化！（缺乏更多细节） - Anders R. Bystrup

“它是O(n)，所以你做不得更好”这种说法是毫无意义的。它展示了过度学校化，使人们的思维变得僵化。例如，在我的硬盘上访问数据是O(n)的。这是否意味着我使用固态硬盘就不能做得更好了？为了举例而言，通过在更大的字（使用SSE）上操作可以加速此算法。这难道不算做更好吗？秩序是秩序，但系数也非常重要。 - Aleksandr Dubinsky

请正确引用我的话。我写道“...不能做得更好...”。也许我应该更明确地写成“...无法做到数量级的改进...”，但我认为像您这样受过良好教育的人会能够推断出来。我同意你可以优化原始代码，并引入各种特定于处理器的技巧，但事实仍然是它仍然是线性操作。 - Anders R. Bystrup

你仍然错误，一个O(n)操作可以通过数倍的优化。无论是从CPU到GPU，HD到SSD，解释型语言到编译型语言，特殊CPU指令，算法合理重写，甚至是针对特定问题的巧妙优化（例如，在这种情况下，数组元素通常非常不同，但有时全部相同。那么，尽早退出将带来数倍的速度提升）。 - Aleksandr Dubinsky

Answer 10

寻找适用于您平台的支持线程或并行for循环的库，并将计算拆分，以便不同核心测试数组的不同范围。

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

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

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

- Scott Langham

---

这不是一个适合并行处理的问题，因为这里的大问题将是内存带宽，所以不是一个线程等待 RAM 访问，现在你有多个线程更长时间地等待 RAM 访问。IA32 架构意味着由于硬件内存流，单个线程最好。 - Skizz

是的。如果数组很小，它们将保留在一个处理器的缓存中。 - Aleksandr Dubinsky

我同意收益取决于系统架构和所分析数据的性质。如果目标是找到最快的方法，我相信有些情况下并行处理会比串行处理更快。 - Scott Langham