4

阅读为什么处理排序数组比处理未排序数组更快？，我在主循环中添加了一个额外的测试。似乎这个额外的测试使程序更快。

int main()
{
    // Generate data
    const unsigned arraySize = 32768;
    int data[arraySize];

    for (unsigned c = 0; c < arraySize; ++c)
         data[c] = std::rand() % 256;

    //Don't sort the array
    //std::sort(data, data + arraySize);

    // Test
    clock_t start = clock();
    long long sum = 0;

    for (unsigned i = 0; i < 100000; ++i)
    {
        // Primary loop
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];

            //With this additional test, execution becomes faster
            if (data[c] < 128)
                sum += data[c];
        }
    }

    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;

    std::cout << elapsedTime << std::endl;
    std::cout << "sum = " << sum << std::endl;
}

我得到大约 4.2 秒的附加测试和 18 秒没有附加测试。额外的测试不应该让程序变慢而不是让它变快吗？

4

1 回答 1

7

由于那个特殊的附加测试，这个等效的代码：

for (unsigned i = 0; i < 100000; ++i)
{
    // Primary loop
    for (unsigned c = 0; c < arraySize; ++c)
    {
       if (data[c] >= 128)
            sum += data[c];

        //With this additional test, execution becomes faster
        if (data[c] < 128)
            sum += data[c];
     }
}

变成这样：

for (unsigned i = 0; i < 100000; ++i)
{
  // Primary loop
  for (unsigned c = 0; c < arraySize; ++c)
  {
    sum += data[c];//because exactly one condition is guaranteed to be
                   //true in each iteration (in your code)!
                   //the equivalent is as if there is no condition at all!
  }
}

这就是它变得更快的原因。

正是由于不寻常的附加测试和相同的主体，编译器能够优化代码，去除if条件。当你有一个if时，编译器就无法做到这一点。

试着写这个：

sum -= data[c]; //the body is not identical anymore!

在其中一种if情况下。我确信编译器将无法优化代码。它现在应该发出较慢的机器代码。

请注意，外部循环可以完全省略，尽管它不太依赖于附加测试::

// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
    sum += 100000 * data[c];
}

或这个：

// Primary loop
for (unsigned c = 0; c < arraySize; ++c)
{
    sum += data[c];
} 
sum = 100000 * sum; //multiple once!
于 2012-12-01T20:32:24.573 回答