我正在编写一本关于C的编程书A Book 。 练习建议找到一组数字的平均值,算法:
avg += (x - avg) / i;
比以下更好:
sum += x; avg = sum / i;
‘x’是用于存储输入数字的变量。 它还建议除了防止溢出之外,第一个算法确实比第二个algorthim有其他一些好处,任何人都可以帮助我吗? 谢谢!
我假设我们在这里谈论浮点运算(否则“更好”的平均值将是可怕的)。
在第二种方法中,中间结果( sum
)将趋于无限制地增长,这意味着您最终将失去低端精度。 在第一种方法中,中间结果应保持与输入数据大致相似的幅度(假设您的输入没有巨大的动态范围)。 这意味着它将更好地保持精度。
但是 ,我可以想象,随着i
越来越大, (x - avg) / i
将变得越来越不准确(相对)。 所以它也有它的缺点。
从某种意义上来说,它更好地计算出一个运行平均值,即你不需要提前拥有所有数字。 您可以随时计算,也可以在数字可用时计算。
后一种算法比前者快,因为你必须执行n次操作(实际上,后者需要执行2 * n次操作)。 但确实第一个防止溢出。 例如,如果您有这组1000个数字:4000000 * 250,1500000 * 500,2000000 * 500,则所有整数的总和将为2’750.000.000,但是c ++ int数据类型的上限是2,147,483,647。 所以,我们正在处理这种情况下的溢出问题。 但是,如果您执行第一个算法,那么您就可以处理这个问题。
所以我建议您使用第一个算法,如果它可能发生溢出,否则它只会添加额外的操作。 如果您决定使用第一个,那么我建议您使用范围更大的类型。
好吧,答案不在于溢出总和(因为这被排除在外),而是正如Oli在“失去低端精度”中所说的那样。 如果您求和的数字的平均值远大于每个数字与平均值的距离,则第二种方法将丢失尾数位。 由于第一种方法只关注相对值,因此不会遇到这个问题。
因此,任何大于,例如,6000万(对于单精度浮点)的数字列表,但值的变化不会超过10左右,应该显示行为。
如果使用双精度浮点数,则平均值应该更高。 或者三角洲低得多。
我喜欢第二种方法(在循环中求和并在末尾划分)更好,并且可以比第一种方法更快地识别第二种方法。
如果有的话,性能差异是无关紧要的。
并且,如果值的总和溢出足够大的数据类型,则可能比计算平均值有更多问题。
sum += x; avg = sum / i;
在上面的代码中假设我们的数字为10000,20000,…是包含大量数字的数字,那么总和中的值可能会超过其MAX值,而在总和中,总和除以存储在其中的元素。
虽然由于编程语言中存在大量数据类型,但这可能不是问题。那是什么呢
专家说“根据您的应用和要求使用数据类型”。
如果这样计算,假设int是在一个数组中?:
sum += x[i] / N; rem += x[i] % N; avg = sum + rem/N;
如果N
很大(0xFFFFF)并且x[i]
都很小,那么rem
加起来为0xFFFF(最大的int),则可能发生溢出。
需要了解更多c/c++开发分享找到平均值的更好算法,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
以上就是c/c++开发分享找到平均值的更好算法相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/980457.html