Re: [請益] 巨大array的運算
※ 引述《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
討論串 (同標題文章)
Perl 近期熱門文章
PTT數位生活區 即時熱門文章
