Python中大小值的高效算术平均计算

Question

这不是一个如何在Python中计算平均值的问题，而是一个在比较两个数字列表的平均值时如何平衡精度和速度的问题。你知道吗

这个问题是根据学生的成绩来设计的，所以要比较的“典型”输入是[98, 34, 80]和[87, 65, 90, 87]。然而，我遇到的测试用例显然涉及大量的数据，因为我有时会得到OverflowError。你知道吗

有如下测试用例，使用float()返回错误答案：

x = [9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,
     9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,
     9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999]
y = [9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,
     9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999,
     9999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999998]

x和y的平均值非常接近，但不相等。据我所知，得到正确答案的唯一方法是使用Decimal或Fraction，但这些方法比较慢。你知道吗

---

下面是一个快速的性能分析。你知道吗

def mean_fractions(nums):
    return Fraction(sum(nums), max(len(nums), 1))

def mean_builtins(nums):
    return sum(nums) / float(max(len(nums), 1))

def mean_decimal(nums):
    return Decimal(sum(nums)) / max(len(nums), 1)

# test runner
@timeit
def do_itt(func, input, times):
    for i in range(times):
        func(input)

do_ittt(mean_builtins, y, 1000000) # took: 0.9550 sec
do_ittt(mean_decimal, y, 1000000) # took: 3.0867 sec
do_ittt(mean_fractions, y, 1000000) # took: 3.2718 sec

do_ittt(mean_builtins, [96, 43, 88], 1000000) #  took: 0.7679 sec
do_ittt(mean_decimal, [96, 43, 88], 1000000) # took: 1.4871 sec
do_ittt(mean_fractions, [96, 43, 88], 1000000) # took: 2.6341 sec

我们可以看到，使用内置程序提供了显著的加速，甚至忽略了如果希望最终结果是float，则需要转换Decimal和Fraction对象。你知道吗

问题

所以我的问题是，考虑到这些速度差异，有没有一个好的方法来知道builtins方法何时能满足某些列表a和b的要求，以及它何时能提供错误的答案？上面的x和y表示它们相等，这是错误的，但在[96, 43, 88]和[87, 50]上，效果很好。你知道吗

Answer 1

假设原始分数总是整数。Pythonfloat是一个64位ieee754浮点数。它可以表示以10为基数的15位或更少数字的任何整数，或者more precisely，它可以表示高达9007199254740993的任何整数。你知道吗

因此，如果你的分数总和超过这个数，你很可能会在使用float时遇到问题。你知道吗

正如Stefan Pochmann在下面的评论中指出的那样，如果你的金额很大，但不是很大，你也可能会有问题：

6755399441055745.0 / 3 == 6755399441055746.0 / 3 # True

所以除法的结果也需要保持在15位有效数字的限制之下。如果你把一个15位数的数字除以3，你就“失去”了一位数，因为除法可能不会使整数部分的位数减少，而小数部分需要一个额外的位数。这可能意味着一个“备用”有效数字就足够了，但即使这样也可能不够（我还没有测试过）。但当然，如果分数总和是1万亿或更高，您会希望使用更高精度的类型。你知道吗