perl：查找大数的均值和方差而不会溢出
perl: Finding mean and variance of large numbers without overflow
我正在使用子例程 (stats) 来计算数字列表的统计信息。
如果存储为普通 perl 数字，这些数字可能大到足以失去精度。
我收到 JSON formatted strings 这样的数字。
要在不损失精度的情况下解码这些字符串，
我使用激活了 allow_nonref 和 allow_bignum 的 JSON::PP 对象。
我将此类解码数字的列表发送到 stats 子例程
（参见下面显示的代码）。
这个例程计算一些统计数据。
然后将这些统计信息编码为 JSON 并保存到文件中。
大多数时候该过程似乎工作正常，但是
对于某些输入（示例见代码）均值和方差统计的计算值
要么明显错误，要么被编码器编码为 JSON 字符串，或两者兼而有之。
我怀疑这是由于 JSON 解码创建的 Math::BigInt 和 Math::BigFloat 对象的交互，以及 List::Util::sum0.
我正在尝试找出导致这种情况的原因以及 avoid/fix 的方法，
最好不要求助于大的非核心模块。
我愿意接受不精确的均值和方差计算，
但并非完全不准确的结果
或在 JSON.
中编码为字符串的数值结果
演示问题的脚本 (stats.pl):
use strict;
use warnings;
use Data::Dumper;
$Data::Dumper::Varname = "DUMPED_RAWDATA";
use JSON::PP;
use List::Util;
my $JSON = JSON::PP->new->allow_bignum->utf8->pretty->canonical;
sub stats {
#TODO fix bug about negative variance. AVOID OVERFLOW
#TODO use GMP, XS?
# @_ has decoded numbers (called RAWDATA here)
my $n = scalar @_;
my $sum = List::Util::sum0(@_);
my $mean = $sum / $n;
my $var = List::Util::sum0( map { $_**2 } @_ ) / $n - $mean**2;
my $s = {
n => $n,
sum => $sum,
max => List::Util::max(@_),
min => List::Util::min(@_),
mean => $mean,
variance => $var
};
# DUMP STATE IF SOME ERROR OCCURS
print Dumper( \@_ ),
$JSON->encode( { json_encoded_stats => $s, json_encoded_rawdata => \@_ } )
if ( '"' eq substr( $JSON->encode($var), 0, 1 ) #MEAN ENCODED AS STRING
or '"' eq substr( $JSON->encode($mean), 0, 1 ) #VARIANCE ENCODED AS STRING
or $var < 0 ); #VARIANCE IS NEGATIVE!
$s;
}
my @test = (
[
qw( 919300112739897344 919305709216464896 919305709216464896 985592115567603712 959299136196456448)
],
[qw(479655558 429035600 3281034608 3281034608 2606592908 3490045576)],
[ qw(914426431563644928) x 3142 ]
);
for (@test) {
print "---\n";
stats( map { $JSON->decode($_) } @$_ );
}
下面是 perl stats.pl 的缩减输出，问题显示为 <---。
---
$DUMPED_RAWDATA1 = [
'919300112739897344',
'919305709216464896',
'919305709216464896',
'985592115567603712',
'959299136196456448'
];
{
"json_encoded_rawdata" : [
919300112739897344,
919305709216464896,
919305709216464896,
985592115567603712,
959299136196456448
],
"json_encoded_stats" : {
"max" : 985592115567603712,
"mean" : "9.40560556587377e+17", <--- ENCODED AS STRING
"min" : 919300112739897344,
"n" : 5,
"sum" : 4702802782936887296,
"variance" : 7.46903843214008e+32
}
}
---
$DUMPED_RAWDATA1 = [
479655558,
429035600,
3281034608,
3281034608,
2606592908,
3490045576
];
{
"json_encoded_rawdata" : [
479655558,
429035600,
3281034608,
3281034608,
2606592908,
3490045576
],
"json_encoded_stats" : {
"max" : 3490045576,
"mean" : 2261233143,
"min" : 429035600,
"n" : 6,
"sum" : 13567398858,
"variance" : "-1.36775568782523e+18" <--- NEGATIVE VARIANCE, STRING ENCODED
}
}
---
$DUMPED_RAWDATA1 = [
'914426431563644928',
.
.
.
<snip 3140 identical lines>
'914426431563644928'
];
{
"json_encoded_rawdata" : [
914426431563644928,
.
.
.
<snip 3140 identical lines>
914426431563644928
],
"json_encoded_stats" : {
"max" : 914426431563644928,
"mean" : "9.14426431563676e+17", <--- STRING ENCODED
"min" : 914426431563644928,
"n" : 3142,
"sum" : 2.87312784797307e+21,
"variance" : -9.75463826617761e+22 <--- NEGATIVE VARIANCE
}
}
None 的输入大到需要 JSON::PP 在具有 64 位整数的系统上创建 Math::BigInt 对象，所以它不需要。
您可以在子程序的开头执行类似以下操作。
@_ = map { Math::BigInt->new($_) } @_; # Or ::BigFloat?
或者，
my $zero_B = Math::BigInt->new(0);
sub stats {
my $n = @_;
my $sum_B = sum($zero_B, @_);
my $mean_B = $sum_B / $n;
my $var_B = sum( map { Math::BigInt->new($_) ** 2 } @_ ) / $n - $mean_B ** 2;
my ($min, $max) = minmax(@_);
return {
n => $n,
sum => $sum_B,
max => $max,
min => $min,
mean => $mean_B,
variance => $var_B,
};
}
总计：
use strict;
use warnings;
use Data::Dumper qw( Dumper );
use JSON::PP qw( );
use List::MoreUtils qw( minmax );
use List::Util qw( sum );
use Math::BigInt qw( );
my $zero_B = Math::BigInt->new(0);
my $JSON = JSON::PP->new->allow_bignum->utf8->pretty->canonical;
sub stats {
my $n = @_;
my $sum_B = sum($zero_B, @_);
my $mean_B = $sum_B / $n;
my $var_B = sum( map { Math::BigInt->new($_) ** 2 } @_ ) / $n - $mean_B ** 2;
my ($min, $max) = minmax(@_);
return {
n => $n,
sum => $sum_B,
max => $max,
min => $min,
mean => $mean_B,
variance => $var_B,
};
}
my @test = (
[qw( 919300112739897344 919305709216464896 919305709216464896 985592115567603712 959299136196456448 )],
[qw( 479655558 429035600 3281034608 3281034608 2606592908 3490045576 )],
[ qw( 914426431563644928 ) x 3142 ]
);
for (@test) {
print "---\n";
my $s = stats( map { $JSON->decode($_) } @$_ );
if (
$JSON->encode($s->{variance}) =~ /"/ # MEAN ENCODED AS STRING
|| $JSON->encode($s->{mean}) =~ /"/ # VARIANCE ENCODED AS STRING
|| $s->{variance} < 0 # VARIANCE IS NEGATIVE!
) {
local $Data::Dumper::Varname = "DUMPED_RAWDATA";
print Dumper($_);
print $JSON->encode({
json_encoded_rawdata => $_,
json_encoded_stats => $s,
});
} else {
print "ok\n";
}
}
备注：
- 即使对象已经是 Math::* 对象，这两种方法都有效。
- 为了清楚起见，我使用
_B 确定变量保证包含 Math:Big* 对象。
- 我将测试代码移到了测试工具中。
- 我使用
minmax 因为它比分别调用 min 和 max 更有效。
- 我从模块中导入了 subs 以避免使用他们的全名。
- 无需将标量上下文中的某些内容强制转换为标量上下文。
@ikegami 的回答正确
但是这个子程序对我来说太慢了
在我的程序的内部循环中被调用了很多次。
我认为这是确保
所有数字都转换为任意精度的数字。
我最终使用了以下实现
这避免了将所有数字转换为任意数字
精度类型。
sub stats {
my $n = scalar @_;
my $sum = List::Util::sum0(@_);
my $mean = $sum / $n;
my $var = List::Util::sum0( map { ( $_ - $mean )**2 } @_ ) / $n;
$mean += 0;
$var += 0; # TO ENSURE THAT THEY ARE ENCODED AS NUMBERS IN JSON
{
n => $n,
sum => $sum,
max => List::Util::max(@_),
min => List::Util::min(@_),
mean => $mean,
variance => $var,
};
}
我改变了计算方差的方法
确保避免负面结果
（正如@Robert所建议的）。
它可能会牺牲 $sum 中的精度
（以及所有依赖于 $sum 的东西）
由于大整数的浮点加法。
不过，它在可接受的执行时间内完成了作业。
意外 JSON 将数字编码为字符串
在 https://metacpan.org/pod/JSON::PP#simple-scalars 中有解释。
这个问题用方法解决了
建议在那里强制编码为数字。
JSON::PP will encode undefined scalars as JSON null values, scalars
that have last been used in a string context before encoding as JSON
strings, and anything else as number value
You can force the type to be a JSON number by numifying it:
my $x = "3"; # some variable containing a string
$x += 0; # numify it, ensuring it will be dumped as a number
$x *= 1; # same thing, the choice is yours. in to force
我正在使用子例程 (stats) 来计算数字列表的统计信息。
如果存储为普通 perl 数字，这些数字可能大到足以失去精度。
我收到 JSON formatted strings 这样的数字。
要在不损失精度的情况下解码这些字符串，
我使用激活了 allow_nonref 和 allow_bignum 的 JSON::PP 对象。
我将此类解码数字的列表发送到 stats 子例程
（参见下面显示的代码）。
这个例程计算一些统计数据。
然后将这些统计信息编码为 JSON 并保存到文件中。
大多数时候该过程似乎工作正常，但是
对于某些输入（示例见代码）均值和方差统计的计算值
要么明显错误，要么被编码器编码为 JSON 字符串，或两者兼而有之。
我怀疑这是由于 JSON 解码创建的 Math::BigInt 和 Math::BigFloat 对象的交互，以及 List::Util::sum0.
我正在尝试找出导致这种情况的原因以及 avoid/fix 的方法， 最好不要求助于大的非核心模块。 我愿意接受不精确的均值和方差计算， 但并非完全不准确的结果 或在 JSON.
中编码为字符串的数值结果演示问题的脚本 (stats.pl):
use strict;
use warnings;
use Data::Dumper;
$Data::Dumper::Varname = "DUMPED_RAWDATA";
use JSON::PP;
use List::Util;
my $JSON = JSON::PP->new->allow_bignum->utf8->pretty->canonical;
sub stats {
#TODO fix bug about negative variance. AVOID OVERFLOW
#TODO use GMP, XS?
# @_ has decoded numbers (called RAWDATA here)
my $n = scalar @_;
my $sum = List::Util::sum0(@_);
my $mean = $sum / $n;
my $var = List::Util::sum0( map { $_**2 } @_ ) / $n - $mean**2;
my $s = {
n => $n,
sum => $sum,
max => List::Util::max(@_),
min => List::Util::min(@_),
mean => $mean,
variance => $var
};
# DUMP STATE IF SOME ERROR OCCURS
print Dumper( \@_ ),
$JSON->encode( { json_encoded_stats => $s, json_encoded_rawdata => \@_ } )
if ( '"' eq substr( $JSON->encode($var), 0, 1 ) #MEAN ENCODED AS STRING
or '"' eq substr( $JSON->encode($mean), 0, 1 ) #VARIANCE ENCODED AS STRING
or $var < 0 ); #VARIANCE IS NEGATIVE!
$s;
}
my @test = (
[
qw( 919300112739897344 919305709216464896 919305709216464896 985592115567603712 959299136196456448)
],
[qw(479655558 429035600 3281034608 3281034608 2606592908 3490045576)],
[ qw(914426431563644928) x 3142 ]
);
for (@test) {
print "---\n";
stats( map { $JSON->decode($_) } @$_ );
}
下面是 perl stats.pl 的缩减输出，问题显示为 <---。
---
$DUMPED_RAWDATA1 = [
'919300112739897344',
'919305709216464896',
'919305709216464896',
'985592115567603712',
'959299136196456448'
];
{
"json_encoded_rawdata" : [
919300112739897344,
919305709216464896,
919305709216464896,
985592115567603712,
959299136196456448
],
"json_encoded_stats" : {
"max" : 985592115567603712,
"mean" : "9.40560556587377e+17", <--- ENCODED AS STRING
"min" : 919300112739897344,
"n" : 5,
"sum" : 4702802782936887296,
"variance" : 7.46903843214008e+32
}
}
---
$DUMPED_RAWDATA1 = [
479655558,
429035600,
3281034608,
3281034608,
2606592908,
3490045576
];
{
"json_encoded_rawdata" : [
479655558,
429035600,
3281034608,
3281034608,
2606592908,
3490045576
],
"json_encoded_stats" : {
"max" : 3490045576,
"mean" : 2261233143,
"min" : 429035600,
"n" : 6,
"sum" : 13567398858,
"variance" : "-1.36775568782523e+18" <--- NEGATIVE VARIANCE, STRING ENCODED
}
}
---
$DUMPED_RAWDATA1 = [
'914426431563644928',
.
.
.
<snip 3140 identical lines>
'914426431563644928'
];
{
"json_encoded_rawdata" : [
914426431563644928,
.
.
.
<snip 3140 identical lines>
914426431563644928
],
"json_encoded_stats" : {
"max" : 914426431563644928,
"mean" : "9.14426431563676e+17", <--- STRING ENCODED
"min" : 914426431563644928,
"n" : 3142,
"sum" : 2.87312784797307e+21,
"variance" : -9.75463826617761e+22 <--- NEGATIVE VARIANCE
}
}
None 的输入大到需要 JSON::PP 在具有 64 位整数的系统上创建 Math::BigInt 对象，所以它不需要。
您可以在子程序的开头执行类似以下操作。
@_ = map { Math::BigInt->new($_) } @_; # Or ::BigFloat?
或者，
my $zero_B = Math::BigInt->new(0);
sub stats {
my $n = @_;
my $sum_B = sum($zero_B, @_);
my $mean_B = $sum_B / $n;
my $var_B = sum( map { Math::BigInt->new($_) ** 2 } @_ ) / $n - $mean_B ** 2;
my ($min, $max) = minmax(@_);
return {
n => $n,
sum => $sum_B,
max => $max,
min => $min,
mean => $mean_B,
variance => $var_B,
};
}
总计：
use strict;
use warnings;
use Data::Dumper qw( Dumper );
use JSON::PP qw( );
use List::MoreUtils qw( minmax );
use List::Util qw( sum );
use Math::BigInt qw( );
my $zero_B = Math::BigInt->new(0);
my $JSON = JSON::PP->new->allow_bignum->utf8->pretty->canonical;
sub stats {
my $n = @_;
my $sum_B = sum($zero_B, @_);
my $mean_B = $sum_B / $n;
my $var_B = sum( map { Math::BigInt->new($_) ** 2 } @_ ) / $n - $mean_B ** 2;
my ($min, $max) = minmax(@_);
return {
n => $n,
sum => $sum_B,
max => $max,
min => $min,
mean => $mean_B,
variance => $var_B,
};
}
my @test = (
[qw( 919300112739897344 919305709216464896 919305709216464896 985592115567603712 959299136196456448 )],
[qw( 479655558 429035600 3281034608 3281034608 2606592908 3490045576 )],
[ qw( 914426431563644928 ) x 3142 ]
);
for (@test) {
print "---\n";
my $s = stats( map { $JSON->decode($_) } @$_ );
if (
$JSON->encode($s->{variance}) =~ /"/ # MEAN ENCODED AS STRING
|| $JSON->encode($s->{mean}) =~ /"/ # VARIANCE ENCODED AS STRING
|| $s->{variance} < 0 # VARIANCE IS NEGATIVE!
) {
local $Data::Dumper::Varname = "DUMPED_RAWDATA";
print Dumper($_);
print $JSON->encode({
json_encoded_rawdata => $_,
json_encoded_stats => $s,
});
} else {
print "ok\n";
}
}
备注：
- 即使对象已经是 Math::* 对象，这两种方法都有效。
- 为了清楚起见，我使用
_B确定变量保证包含 Math:Big* 对象。 - 我将测试代码移到了测试工具中。
- 我使用
minmax因为它比分别调用min和max更有效。 - 我从模块中导入了 subs 以避免使用他们的全名。
- 无需将标量上下文中的某些内容强制转换为标量上下文。
@ikegami 的回答正确 但是这个子程序对我来说太慢了 在我的程序的内部循环中被调用了很多次。 我认为这是确保 所有数字都转换为任意精度的数字。 我最终使用了以下实现 这避免了将所有数字转换为任意数字 精度类型。
sub stats {
my $n = scalar @_;
my $sum = List::Util::sum0(@_);
my $mean = $sum / $n;
my $var = List::Util::sum0( map { ( $_ - $mean )**2 } @_ ) / $n;
$mean += 0;
$var += 0; # TO ENSURE THAT THEY ARE ENCODED AS NUMBERS IN JSON
{
n => $n,
sum => $sum,
max => List::Util::max(@_),
min => List::Util::min(@_),
mean => $mean,
variance => $var,
};
}
我改变了计算方差的方法
确保避免负面结果
（正如@Robert所建议的）。
它可能会牺牲 $sum 中的精度
（以及所有依赖于 $sum 的东西）
由于大整数的浮点加法。
不过，它在可接受的执行时间内完成了作业。
意外 JSON 将数字编码为字符串 在 https://metacpan.org/pod/JSON::PP#simple-scalars 中有解释。 这个问题用方法解决了 建议在那里强制编码为数字。
JSON::PP will encode undefined scalars as JSON null values, scalars that have last been used in a string context before encoding as JSON strings, and anything else as number value
You can force the type to be a JSON number by numifying it:
my $x = "3"; # some variable containing a string $x += 0; # numify it, ensuring it will be dumped as a number $x *= 1; # same thing, the choice is yours. in to force