Rubyで統計処理プログラムを組んでおり、下記HPを参考にして分散値(と標準偏差)の計算をしているのですが、当該メソッドの演算に時間がかかっており高速化を図る方法をお教えください。


http://d.hatena.ne.jp/sesejun/20070502/p1

上記HP内の分散計算のメソッドを別のものに置換えにて高速化する方法はありますでしょうか?その場合には上記HPのプログラムの実行時間を100%とすると80%になるなど、効果もお教えください。演算の精度は下がるが高速化可能等のアルゴリズムであれば、演算精度の低下の程度もお教えください。

実行環境はubuntuです。このメソッドのみバイナリコードに置き換え(呼出し?)しての高速化なども可能性があるのでしょうか?

なお、すべてC言語等で記述しなおすなどの回答は無しでお願いします。

回答の条件
  • 1人10回まで
  • 13歳以上
  • 登録:2012/11/24 23:36:27
  • 終了:2012/12/01 23:40:04

ベストアンサー

id:a-kuma3 No.1

a-kuma3回答回数4363ベストアンサー獲得回数18002012/11/25 02:41:10

ポイント300pt

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 くらいのデータで試してます。

 分散の値utimestime
質問の実装 3.785123966942160.140.0
ループを一回 3.785123966942020.090.0
定義通りの実装 3.785123966942240.110.01


元々の実装、よくできてますね。
丸めによる誤差を無くそうとすると、多倍長演算を使うことになると思うのですが、肝心の速度はがた落ちでしょう。
多少の誤差に目をつぶって、速度を取るか、速度を多少犠牲にして、制度を取るか、というトレードオフになるかと。

因みに、質問で上げられているダイアリーの実装だと、var は丸め誤差を慎重に扱ってますけど、avg の方の実装は普通に丸め誤差を含んでますね。

他1件のコメントを見る
id:gentoopenguin

比較、ありがとうございます!
「多少の誤差に目をつぶって、速度を取る」ということにします。
たいへん勉強になりました。

#バージョンによって、結果が異なるのは不明ですが。
#あとは、同じプログラムでRuby1.9化してみると高速化するのか等、追加で実験してみます。

2012/11/27 21:12:13
id:a-kuma3

標本数が大きくなると、積み残しの誤差が無視できなくなるかもしれませんが、そこだけ注意しておけば大丈夫じゃないか、と。

ちょっと気になって ruby のソースを見てみたんですが、1.6.7 も 1.8.7 も Float クラスの数値の実体は double で、掛け算の処理も double どうしの掛け算でした。
むー (´・ω・`)

2012/11/27 22:08:48

その他の回答(0件)

id:a-kuma3 No.1

a-kuma3回答回数4363ベストアンサー獲得回数18002012/11/25 02:41:10ここでベストアンサー

ポイント300pt

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 くらいのデータで試してます。

 分散の値utimestime
質問の実装 3.785123966942160.140.0
ループを一回 3.785123966942020.090.0
定義通りの実装 3.785123966942240.110.01


元々の実装、よくできてますね。
丸めによる誤差を無くそうとすると、多倍長演算を使うことになると思うのですが、肝心の速度はがた落ちでしょう。
多少の誤差に目をつぶって、速度を取るか、速度を多少犠牲にして、制度を取るか、というトレードオフになるかと。

因みに、質問で上げられているダイアリーの実装だと、var は丸め誤差を慎重に扱ってますけど、avg の方の実装は普通に丸め誤差を含んでますね。

他1件のコメントを見る
id:gentoopenguin

比較、ありがとうございます!
「多少の誤差に目をつぶって、速度を取る」ということにします。
たいへん勉強になりました。

#バージョンによって、結果が異なるのは不明ですが。
#あとは、同じプログラムでRuby1.9化してみると高速化するのか等、追加で実験してみます。

2012/11/27 21:12:13
id:a-kuma3

標本数が大きくなると、積み残しの誤差が無視できなくなるかもしれませんが、そこだけ注意しておけば大丈夫じゃないか、と。

ちょっと気になって ruby のソースを見てみたんですが、1.6.7 も 1.8.7 も Float クラスの数値の実体は double で、掛け算の処理も double どうしの掛け算でした。
むー (´・ω・`)

2012/11/27 22:08:48
id:gentoopenguin

早速のご回答、ありがとうございます。

まずはすぐに差し替えして実行してみたのですが、このプログラムでは分散の値が負の数を出力することがあるようです。

すみません、中身をきちんと考えれていないのですが、まずは連絡まで。

  • id:gentoopenguin
    ご連絡ありがとうございます。負の数を出力しているのは引き算にて誤差が生じているためなのでしょうか。

    例えば、99.7を100個並んだ配列を入力とした場合、期待値は0ですが、-1.2732925824821e-11 を出力してます。

    適用いただいた公式は、コンピュータ向きでは無いのでしょうか。
    引き続きよろしくお願いいたします。
  • id:a-kuma3
    >例えば、99.7を100個並んだ配列を入力とした場合、期待値は0ですが、-1.2732925824821e-11 を出力してます。
    元々の var メソッドでも、同じ数値を分散として返します。
  • id:gentoopenguin
    実行環境に依存するのかもしれませんが、元々のvarメソッドでは、期待値である0を出力しているように見えます。大きな勘違いをしておりましたら、すみません。

    ubuntu リリース 12.04 (precise) 32-bit
    カーネル Linux 3.2.0-29-generic-pae
    ruby 1.8.7 (2011-06-30 patchlevel 352) [i686-linux]
  • id:a-kuma3
    >実行環境に依存するのかもしれませんが、元々のvarメソッドでは、期待値である0を出力しているように見えます。大きな勘違いをしておりましたら、すみません。
    いや、勘違いをしているのは、ぼくの方かもしれませんし。

    ぼくが確認したのは、Windows 環境で、Ruby のバージョンは以下の通りです。
    ruby 1.6.7 (2002-04-11) [i386-mingw32]

    ちょっと古めですが、いろいろ都合がありまして (^^ゞ
  • id:gentoopenguin
    すみません。なにか原因を探る方法を連絡いただければ調査等はできるのですが。。。
    なにぶん、理解が及んでおらず。どうしようか手が止まってしまっている状態です。
  • id:a-kuma3
    別のバージョンで試してみました。
    ruby 1.8.7 (2008-08-11 patchlevel 72) [sparc-linux]

    gentoopenguin さんが書かれている通り、質問先にあった実装と、ぼくが回答に書いたメソッドでは、結果に差が出ました。
    メソッドの実装で結果に差が出るのは、実数演算での誤差です。
    いわゆる「積み残し」と言われるやつです。
    # なんで、1.6.7 だと差が出ないんだろう...

    分散の定義通りの実装も比較してみました。
    ソースの記述もあるので、回答に追記しました。

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません