作者frank1983 (What?)
看板Perl
标题Re: [请益] 巨大array的运算
时间Sat Feb 6 02:04:55 2010
※ 引述《heliosy (这一栏是要做啥用的)》之铭言：
: 先说例子
: 我有一个array (1 2 3 4)
: 然後我要对它做运算
: mean(1) + mean(2) + mean(3) + mean(4) = m1 mean: 代表对括号中的值取平均
: mean(1 2) + mean(2 3) + mean(3 4) = m2
: mean(1 2 3) + mean(2 3 4) = m3
: mean(1 2 3 4) = m4
: 最後所求是 mean(m1 m2 m3 m4)
: 有点类似sliding window
: 方法我是已经写完了 所用的就是for 跟 map的组合
: 小阵列ok 但是我的array有时会大到几十万...
: 所以会变的很慢很慢
: 请问有什麽方法可以改善吗
: 谢谢
来试着写看看吧，希望没有写错^^
假设传入的参数为阵列的参照 (reference)
版本一:
sub sliding_mean_1
{
my $array = shift;
my $count = @{$array};
return 0 if $count == 0;
my $mean = 0;
for my $length (1 .. $count) {
my ($sum, $num, $sub_i) = (0, 0, 0);
for my $i (0 .. $#{$array}) {
$sum += $array->[$i];
next if ++$num < $length;
$mean += $sum/$length;
$sum -= $array->[$sub_i++];
}
}
return $mean/$count;
}
complexity: O(n^2), n 为 array 的长度
版本二:
sub sliding_mean_2
{
my $array = shift;
my $count = @{$array};
return 0 if $count == 0;
my $coef = 0;
$coef += 1/$_ for 1 .. $count;
my $add_coef = $coef;
my ($beg, $end) = (0, $#{$array});
my $sum = 0;
while ($beg < $end) {
$sum += ($array->[$beg] + $array->[$end])*$coef;
$coef += ($add_coef -= 1/($beg+1) + 1/($end+1));
++$beg;
--$end;
}
$sum += $array->[$beg]*$coef if $beg == $end;
return $sum/$count;
}
complexity: O(n), n 为 array 的长度
两个函式的结果会因为浮点数的误差而有些许的差异！
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 61.230.179.6