C中的循环优化

Question

我的任务是优化C中的特定for循环.这是循环:

#define ARRAY_SIZE 10000
#define N_TIMES    600000

for (i = 0; i < N_TIMES; i++)
{
    int j;

    for (j = 0; j < ARRAY_SIZE; j++)
    {
        sum += array[j];
    }
}

我应该使用循环展开,循环拆分和指针来加速它,但每次我尝试实现某些东西时,程序都不会返回.这是我到目前为止所尝试的:

for (i = 0; i < N_TIMES; i++) 
{
    int j,k;

    for (j = 0; j < ARRAY_SIZE; j++) 
    {    
        for (k = 0; k < 100; k += 2) 
        {
            sum += array[k];
            sum += array[k + 1];
        }
    } 
}

我不明白为什么程序现在甚至没有返回.任何帮助,将不胜感激.

Answer 1

第二段代码既低效又错误,因为它增加了比原始代码更多的值.

循环展开(或者在这种情况下减少,因为你可能不想展开一万次迭代循环)将是:

// Ensure ARRAY_SIZE is a multiple of two before trying this.
for (int i = 0; i < N_TIMES; i++)
    for (int j = 0; j < ARRAY_SIZE; j += 2)
        sum += array[j] + array[j+1];

但是,说实话,愚蠢的编译器的时代早已过去.您通常应将此级别的微优化保留在编译器中,而您则专注于更高级别的内容,如数据结构,算法和人工分析.

最后一个是相当重要的.由于您将相同的数组添加到累计和中的次数相同,因此您只需要一次数组的总和,然后您可以根据需要多次添加该部分和:

int temp = 0;
for (int i = 0; i < ARRAY_SIZE; i++)
    temp += array[i];
sum += temp * N_TIMES;

它仍然O(n)是一个更低的乘数n(一个而不是六十万).这可能是海湾合作委员会的疯狂优化级别-O3可以工作了这一点,但我对此表示怀疑.在很多领域,人类大脑仍然可以超越计算机.

现在,无论如何:-)