c++ - 有条件的大型平面数组遍历和令人惊讶的短循环执行时间

Question

我需要对我通过经验发现的一些东西进行解释。我有一个非常大的 char 类型平面数组。该数组的总长度为 500x500x500 = 125E+6 字节。在单元格内，我保留了 0 到 255 之间的数字。但幸运的是，在遍历数组时，我只对具有非零值的单元格感兴趣!

现在问题来了。我通过实验发现，在遍历整个零和非零数组时，即使对单元格执行最小的操作也会花费大量时间，而如果我使用类似于下面的条件，

while( index < 125000000 )
{
    if( array[ index ] > 0 )
    {
        // Do some stuff
    }

    index++;
}

执行时间大大缩短。事实上，我可以在几秒钟内遍历整个数组并对非零单元执行操作，而不是无条件地执行该方法的半小时。

我需要的是解释为什么它有效!我需要在我的论文报告中解释这一现象，如果我能与科学论文或类似论文联系起来那就最好了。

提前谢谢您!

最诚挚的问候， 奥米德·阿里扬

Answer 1

您可能希望您的 char 是无符号的，因此能够保存 [0,255] 范围内的值，但实际上它是有符号的，保存 [-128, 127](假设二进制补码)。因此 array[ index ] > 0 的情况数量比您预期的要少得多，因为所有分配值大于 127 的元素都将具有负值。

请注意，您声称要检查非零值，但实际上是在检查正值。

您可以检查您平台上char的范围:

#include <limits>
#include <iostream>

int main()
{
  std::cout << static_cast<int>(std::numeric_limits<char>::min()) << std::endl;
  std::cout << static_cast<int>(std::numeric_limits<char>::max()) << std::endl;

  char c = 234;
  std::cout << static_cast<int>(c) << std::endl; // 234 if unsigned, -22 if signed
}