0

我正在努力提高我即将发布的作业的编程技能，它涉及解决问题，同时使其尽可能高效和快速地运行。我知道这是一段相当克制/小段的代码，但如果有什么能让它运行得更快的话。

该方法采用一个包含事务详细信息的数组，用于维护循环的事务数为 100。所以我得到了平均股数，然后返回它。英语不流利，所以希望它有意义，谢谢

double Analyser::averageVolume()
{
    // Your code
    double averageNumShares = 0;
    for(int i = 0; i < nTransactions; i++)
    {
        averageNumShares += tArray[i].numShares;
    }
    averageNumShares = averageNumShares / nTransactions;
    return averageNumShares;
    //return 0
}
4

6 回答 6

4

如果您需要计算 n 个数字的平均值，恐怕您无法将其加速超过示例代码中的线性时间方法。

除非这被用作另一个更复杂的算法的一部分，在这种算法中你可能不必计算平均值或沿着这些线计算，否则取平均值将是一个 O(n) 操作，它基本上涉及对所有数组的元素和一个除以元素的数量。这正是你所拥有的。

于 2013-03-07T15:59:50.887 回答
1

为什么不为该对象设置另外两个值 - 运行总计和项目数？

然后计算平均值可以利用这些数字。快速简单（可能是一个内联函数！）。

于 2013-03-07T16:04:45.090 回答
1

这是另一种方法，类似于Ed Heal建议的方法，它应该对舍入误差不太敏感。平均值的舍入误差随着累积和的大小而增长。这对您来说可能是也可能不是问题，但需要注意。

这是一个迭代算法，可以最小化平均舍入误差，这是我在Ross的旧版本（大约 1998 年）中第一次遇到的：

double Analyser::averageVolume()
{
  double averageNumShares = 0.0;

  for (int i = 0; i < nTransactions; i++)
  {
    double delta = (tArray[i].numShares - averageNumShares) / (i+1);
    averageNumShares += delta;
  }

  return averageNumShares;
}

这是通过推导平均值的递归定义来实现的。也就是说，给定 samples x[1], ..., x[j], ..., x[N]，您可以计算 sample 的第一个M+1样本x[M+1]的平均值和第一个样本的平均值M：

sum(M) = x[1] + x[2] + ... + x[M]
thus avg(M+1) = sum(M+1)/(M+1) and avg(M) = sum(M)/M

avg(M+1) - avg(M) = sum(M+1)/(M+1) - sum(M)/M
    = [ M*sum(M+1) - (M+1)*sum(M) ]/[ M * (M+1) ]
    = [ M*(x[M+1] + sum(M)) - M*sum(M) - sum(M) ] / [ M*(M+1) ]
    = [ M*x[M+1] - sum(M) ] / [ M*(M+1) ]
    = [ x[M+1] - avg(M) ] / (M+1)
thus: avg(M+1) = avg(M) + [ x[M+1] - avg(M) ]/(M+1)

要了解这两种方法的舍入误差，请尝试计算 10^7 个样本的平均值，每个样本等于 1035.41。您最初的方法返回（在我的硬件上），平均为 1035.40999988683。上面的迭代方法返回 1035.41 的精确平均值。

不幸的是，两者在某些时候都是 O(N)。你原来的方案有 N 个加法和一个除法。迭代方案有 N 个加法、减法和除法，因此您为准确性付出了更多。

于 2013-03-07T17:16:59.453 回答
0

如果您使用 gcc 更改优化级别。

于 2013-03-07T16:00:52.020 回答
0

简短的回答：这段代码在速度方面是最好的。你可以调整的是你如何编译它。或者显然，如果可以的话，在汇编中重写它。

“延伸”答案：现在......如果您真的想尝试获得更好的性能，已经尝试使用所有可用的编译器优化标志和优化，并且您准备好牺牲代码可读性以获得更快的速度，您可以考虑重写：

for(int i = 0; i < nTransactions; i++)
    {
        averageNumShares += tArray[i].numShares;
    }

作为

pointerValue = &(tArray[0].numShares);
pointerIncrement = sizeof(tArray[0]);
for(int i = 0; i < nTransactions; i++)
    {
        averageNumShares += *(pointerValue++pointerIncrement);
    }

通过向编译器显示您所做的只是在每次循环迭代时跳过固定偏移量，您可能会获得更好的性能。一个好的编译器应该能够通过您的初始代码看到这一点。新代码可能会让你的表现更差。这实际上取决于您的编译器的具体情况，并且我不推荐这种方法，除非您迫切希望获得比编译器提供的更好的性能，并且不想跳到使用内联汇编或内在函数（如果任何可用的）。

于 2013-03-07T16:02:07.163 回答
0 
int i= nTransactions;
while(i--){// test for 0 is faster
    averageNumShares += (q++)->numShares;// increment pointer is faster than offset
}
于 2013-03-07T16:24:30.593 回答