我有一个很大的矩阵,其中的值在数量级上变化很大。为了尽可能准确地计算总和,我的方法是将ndarray重新塑造成一个一维数组,对其进行排序,然后将其相加,从最小的条目开始。有没有更好/更有效的方法来做到这一点?
nwo49xxi1#
我认为,对于浮点精度问题,您的任务最知名的算法是Kahan summation。出于实用目的,Kahan求和的误差范围与被加数无关,而朴素求和的误差范围随被加数线性增长。NumPy不使用Kahan求和,并且没有简单的方法来实现它而不需要很大的性能权衡。但是它使用了下一个最好的东西,pairwise summation,在一些合理的假设下,误差会增长,比如被和数对数的平方根。因此,Numpy很可能已经能够为您的问题提供足够好的精度。为了验证这一点,我实际上会通过Kahan求和运行一些示例案例(上面维基百科链接中的伪代码可以简单地转换为Python),并将其作为黄金,最好的结果,并将其与之进行比较:1.按原样调用矩阵上的np.sum。1.在将矩阵整形为1D后调用np.sum,如果矩阵在内存中不连续,这可能会给予更好的结果。1.在1D数组的排序版本上调用np.sum。在大多数情况下,后三个选项的行为应该类似,但唯一的方法是实际测试它。
np.sum
pepwfjgg2#
我想对numpy sum做一个简单的改进:使用np.float128(四倍精度)作为中间值,然后转换回标准的64位浮点数:
np.float64(np.sum(array, dtype=np.float128))
字符串这会将求和的值转换为四倍精度,显著减少舍入误差。这比64位的numpy.sum慢,但比fsum或先对数组排序快得多。举个例子,我正在计算一个1000x1000的矩阵,它的绝对值来自标准柯西分布matrix = np.abs(np.random.standard_cauchy([1000, 1000]))。128位的结果与fsum相同,排序后的np.sum比没有排序的要好,但精度仍然较低。使用%timeit测量的评估时间:
matrix = np.abs(np.random.standard_cauchy([1000, 1000]))
%timeit
np.sum(matrix): 370 μs np.float64(np.sum(matrix, dtype=np.float128)): 4.3 ms math.fsum(matrix.flatten()): 60 ms np.sum(np.sort(matrix.flatten())): 78 ms
型备注:
2条答案
按热度按时间nwo49xxi1#
我认为,对于浮点精度问题,您的任务最知名的算法是Kahan summation。出于实用目的,Kahan求和的误差范围与被加数无关,而朴素求和的误差范围随被加数线性增长。
NumPy不使用Kahan求和,并且没有简单的方法来实现它而不需要很大的性能权衡。但是它使用了下一个最好的东西,pairwise summation,在一些合理的假设下,误差会增长,比如被和数对数的平方根。
因此,Numpy很可能已经能够为您的问题提供足够好的精度。为了验证这一点,我实际上会通过Kahan求和运行一些示例案例(上面维基百科链接中的伪代码可以简单地转换为Python),并将其作为黄金,最好的结果,并将其与之进行比较:
1.按原样调用矩阵上的
np.sum
。1.在将矩阵整形为1D后调用
np.sum
,如果矩阵在内存中不连续,这可能会给予更好的结果。1.在1D数组的排序版本上调用
np.sum
。在大多数情况下,后三个选项的行为应该类似,但唯一的方法是实际测试它。
pepwfjgg2#
我想对numpy sum做一个简单的改进:使用np.float128(四倍精度)作为中间值,然后转换回标准的64位浮点数:
字符串
这会将求和的值转换为四倍精度,显著减少舍入误差。这比64位的numpy.sum慢,但比fsum或先对数组排序快得多。
举个例子,我正在计算一个1000x1000的矩阵,它的绝对值来自标准柯西分布
matrix = np.abs(np.random.standard_cauchy([1000, 1000]))
。128位的结果与fsum相同,排序后的np.sum比没有排序的要好,但精度仍然较低。使用
%timeit
测量的评估时间:型
备注: