http://d.hatena.ne.jp/sesejun/20070502/p1
上記HP内の分散計算のメソッドを別のものに置換えにて高速化する方法はありますでしょうか?その場合には上記HPのプログラムの実行時間を100%とすると80%になるなど、効果もお教えください。演算の精度は下がるが高速化可能等のアルゴリズムであれば、演算精度の低下の程度もお教えください。
実行環境はubuntuです。このメソッドのみバイナリコードに置き換え(呼出し?)しての高速化なども可能性があるのでしょうか?
なお、すべてC言語等で記述しなおすなどの回答は無しでお願いします。
var メソッドを、以下のようにしてみたらどうでしょう。
def var s = 0.0 s2 = 0.0 n = 0 self.each do |v| next if v.nil? x = v.to_f s += x s2 += x * x n += 1 end a = s / n.to_f s2 / n.to_f - a * a end
ループ中の、かけ算&割り算の回数が減ってるので、速くなると思うんですけど。
手元の環境で試してみたら、5~10% くらい実行時間が減っている感じです。
def var3 s, n = self.sum_with_number mean = s / n s2 = 0.0 n = 0 self.each do |v| next if v.nil? x = v.to_f x = x - mean s2 += x * x n += 1 end s2 / n end
以下、それぞれの実装と Process.times で得られる時間です。
データは、質問のリンク先にあった以下のデータの繰り返しで N=6000 くらいのデータで試してます。
分散の値 | utime | stime | |
---|---|---|---|
質問の実装 | 3.78512396694216 | 0.14 | 0.0 |
ループを一回 | 3.78512396694202 | 0.09 | 0.0 |
定義通りの実装 | 3.78512396694224 | 0.11 | 0.01 |
元々の実装、よくできてますね。
丸めによる誤差を無くそうとすると、多倍長演算を使うことになると思うのですが、肝心の速度はがた落ちでしょう。
多少の誤差に目をつぶって、速度を取るか、速度を多少犠牲にして、制度を取るか、というトレードオフになるかと。
因みに、質問で上げられているダイアリーの実装だと、var は丸め誤差を慎重に扱ってますけど、avg の方の実装は普通に丸め誤差を含んでますね。
var メソッドを、以下のようにしてみたらどうでしょう。
def var s = 0.0 s2 = 0.0 n = 0 self.each do |v| next if v.nil? x = v.to_f s += x s2 += x * x n += 1 end a = s / n.to_f s2 / n.to_f - a * a end
ループ中の、かけ算&割り算の回数が減ってるので、速くなると思うんですけど。
手元の環境で試してみたら、5~10% くらい実行時間が減っている感じです。
def var3 s, n = self.sum_with_number mean = s / n s2 = 0.0 n = 0 self.each do |v| next if v.nil? x = v.to_f x = x - mean s2 += x * x n += 1 end s2 / n end
以下、それぞれの実装と Process.times で得られる時間です。
データは、質問のリンク先にあった以下のデータの繰り返しで N=6000 くらいのデータで試してます。
分散の値 | utime | stime | |
---|---|---|---|
質問の実装 | 3.78512396694216 | 0.14 | 0.0 |
ループを一回 | 3.78512396694202 | 0.09 | 0.0 |
定義通りの実装 | 3.78512396694224 | 0.11 | 0.01 |
元々の実装、よくできてますね。
丸めによる誤差を無くそうとすると、多倍長演算を使うことになると思うのですが、肝心の速度はがた落ちでしょう。
多少の誤差に目をつぶって、速度を取るか、速度を多少犠牲にして、制度を取るか、というトレードオフになるかと。
因みに、質問で上げられているダイアリーの実装だと、var は丸め誤差を慎重に扱ってますけど、avg の方の実装は普通に丸め誤差を含んでますね。
比較、ありがとうございます!
「多少の誤差に目をつぶって、速度を取る」ということにします。
たいへん勉強になりました。
#バージョンによって、結果が異なるのは不明ですが。
#あとは、同じプログラムでRuby1.9化してみると高速化するのか等、追加で実験してみます。
標本数が大きくなると、積み残しの誤差が無視できなくなるかもしれませんが、そこだけ注意しておけば大丈夫じゃないか、と。
ちょっと気になって ruby のソースを見てみたんですが、1.6.7 も 1.8.7 も Float クラスの数値の実体は double で、掛け算の処理も double どうしの掛け算でした。
むー (´・ω・`)
早速のご回答、ありがとうございます。
まずはすぐに差し替えして実行してみたのですが、このプログラムでは分散の値が負の数を出力することがあるようです。
すみません、中身をきちんと考えれていないのですが、まずは連絡まで。
比較、ありがとうございます!
2012/11/27 21:12:13「多少の誤差に目をつぶって、速度を取る」ということにします。
たいへん勉強になりました。
#バージョンによって、結果が異なるのは不明ですが。
#あとは、同じプログラムでRuby1.9化してみると高速化するのか等、追加で実験してみます。
標本数が大きくなると、積み残しの誤差が無視できなくなるかもしれませんが、そこだけ注意しておけば大丈夫じゃないか、と。
2012/11/27 22:08:48ちょっと気になって ruby のソースを見てみたんですが、1.6.7 も 1.8.7 も Float クラスの数値の実体は double で、掛け算の処理も double どうしの掛け算でした。
むー (´・ω・`)