質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

89.25%

rubyで繰り返しの計算処理を高速化させたい。

解決済

回答 3

投稿

  • 評価
  • クリップ 1
  • VIEW 154

前提・実現したいこと

初めまして、現在 ruby で一定の整数nを超えるまで規則的に加算を続ける処理を記述しております。
nが2や3など加算の回数が少ない場合は問題ありませんが、12・13となるととても時間がかかる為、
計算を高速に出来ないかメモ化や’Memoist’を試してみましたが上手く出来ませんでした。
何か良い方法があればご教授いただけると幸いです。

該当のソースコード

@memo = {}

def sum(wer)
  return @memo[[wer]] if @memo[[wer]]
    total = 0
    n = 0
  while total < wer do
    rat = []
      n = n + 1
      denomi = 1..n
      denomi.each do |den|
        r = Rational(1, den)
        rat << r
      end
      total = rat.sum
      @memo[[wer]] = total
  end
    rat.inspect
    rat.last
end

puts sum(15)


require 'memoist'
  class Person
    extend Memoist
    def sum(wer)
      n = 0
      i = 0
      while  i < wer
        n += 1
        i = i + Rational(1, n)
      end
      puts n
    end
    memoize :sum
  end

  person = Person.new
  person.sum(15)

試したこと

①では @memo{} を使いメモ化をしようとしました。
@memo[[wer]] = total や、 return @memo[[wer]] if @memo[[wer]] の位置を試したみたものの変化は感じられませんでした。
②では Memoist を導入試しました。

補足情報(FW/ツールのバージョンなど)

ruby 2.5.1 
一応整数nは20ほどを想定しています。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • ozwk

    2020/05/20 16:06

    S(n)=1+1/2+1/3+...+1/nと整数werに対して
    S(n)≧werとなる最小のnを求めたい
    みたいな感じで良いんですよね?

    キャンセル

  • huyusyougun1224

    2020/05/20 16:32

    回答ありがとうございます。
    その考え方で合っております。

    キャンセル

回答 3

checkベストアンサー

+1

分母と分子を別計算にしながら、途中でRationalを使って桁数を抑えることで単純な加算より時間は短くなりました。
参考まで。

MAX = ARGV[0].to_i
RAT_NUM = 1070

puts "float simple addition"
sum = 0.0
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  sum += 1.0/n
  if sum > wer then
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum, Time.now-stime)
    wer += 1
  end
end

puts "rational nume/deno addition"
deno = 1
nume = 0
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  nume = nume * n + deno
  deno *= n
  if nume > wer * deno then
    sum = Rational(nume, deno)
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime)
    wer += 1
    nume = sum.numerator
    deno = sum.denominator
  elsif n % RAT_NUM == 0 then
    sum = Rational(nume, deno)
    nume = sum.numerator
    deno = sum.denominator
  end
end

puts "rational simple addition"
sum = Rational(0)
wer = 1
n = 0
stime = Time.now
while wer <= MAX do
  n += 1
  sum += Rational(1,n)
  if sum > wer then
    printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime)
    wer += 1
  end
end

float simple addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.001000
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.001000
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.002002
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.002002
wer= 6, n=       227, sum=6.004366708345567e+00, elapse=0.003019
wer= 7, n=       616, sum=7.001274097134162e+00, elapse=0.003019
wer= 8, n=      1674, sum=8.000485571995782e+00, elapse=0.003993
wer= 9, n=      4550, sum=9.000208062931115e+00, elapse=0.003993
wer=10, n=     12367, sum=1.000004300827578e+01, elapse=0.004990
wer=11, n=     33617, sum=1.100001770863642e+01, elapse=0.006985
wer=12, n=     91380, sum=1.200000305166562e+01, elapse=0.012998
wer=13, n=    248397, sum=1.300000122948093e+01, elapse=0.027957
rational nume/deno addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.000000
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.001030
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.001998
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.001998
wer= 6, n=       227, sum=6.004366708345566e+00, elapse=0.003051
wer= 7, n=       616, sum=7.001274097134161e+00, elapse=0.005050
wer= 8, n=      1674, sum=8.000485571995780e+00, elapse=0.009068
wer= 9, n=      4550, sum=9.000208062931140e+00, elapse=0.030012
wer=10, n=     12367, sum=1.000004300827581e+01, elapse=0.096833
wer=11, n=     33617, sum=1.100001770863643e+01, elapse=0.440332
wer=12, n=     91380, sum=1.200000305166563e+01, elapse=2.853218
wer=13, n=    248397, sum=1.300000122948078e+01, elapse=19.173152
rational simple addition
wer= 1, n=         2, sum=1.500000000000000e+00, elapse=0.000000
wer= 2, n=         4, sum=2.083333333333333e+00, elapse=0.000997
wer= 3, n=        11, sum=3.019877344877345e+00, elapse=0.000997
wer= 4, n=        31, sum=4.027245195436520e+00, elapse=0.001996
wer= 5, n=        83, sum=5.002068272680166e+00, elapse=0.002991
wer= 6, n=       227, sum=6.004366708345566e+00, elapse=0.003988
wer= 7, n=       616, sum=7.001274097134161e+00, elapse=0.019946
wer= 8, n=      1674, sum=8.000485571995780e+00, elapse=0.030916
wer= 9, n=      4550, sum=9.000208062931140e+00, elapse=0.061500
wer=10, n=     12367, sum=1.000004300827581e+01, elapse=0.295848
wer=11, n=     33617, sum=1.100001770863643e+01, elapse=1.830510
wer=12, n=     91380, sum=1.200000305166563e+01, elapse=12.718921
wer=13, n=    248397, sum=1.300000122948078e+01, elapse=97.580847

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/23 17:33

    頑張りましたね

    キャンセル

  • 2020/05/24 10:12

    回答ありがとうございます。
    コードを参考にさせていただいたところかなり速くなったと思います。

    重ねてありがとうございました。

    キャンセル

+1

規則的に加算 とは
1 + 1/2 + 1/3 + 1/4 + .....
でしょうか。
これですとメモ化はできません。
メモ化は同じ計算を何度も繰り返す場合に有効ですが、この式の場合は「ある計算を繰り返す」って無いですから。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/20 16:31

    ロジックはお答え頂いた 1/i をn回、+を n回 行うのを減らす をすぐに思いつくのは難しそうです。

    キャンセル

  • 2020/05/20 16:52

    フィールズ賞ものでしょう

    キャンセル

  • 2020/05/20 17:45

    そうですよね、森重文先生レベルにはなれないと思うので、少し別の方法や前提条件の見直しをしてみようと思います。

    キャンセル

+1

ちゃんと検証していないのですが、整数のみの演算にすれば多少は速くなるかもしれません。
(式をミスっていたらごめんなさい)

1 + 1/2 = 1 + 1/2
1 + 1/2 + 1/3 = 1 + (3+2)/(2*3)
1 + 1/2 + 1/3 + 1/4 = 1 + ((3+2)*4+(2*3))/(2*3*4)
1 + 1/2 + 1/3 + 1/4 + 1/5 = 1 + (((3*+2)*4+(2*3))*5)+(2*3*4))/(2*3*4*5)
:
1 + 1/2 + 1/3 + ... + 1/n = 1 + ((A*n)+(n-1)!)/(n!)
1 + 1/2 + 1/3 + ... + 1/(n+1) = 1 + ((B*(n+1))+(n)!)/((n+1)!)
  • 次の式の分子のn!は直前の式の分母を使う。
  • Bは直前の式の分子((A*n)+(n-1)!)になる。
  • 判定は割り算ではなくかけ算(分子 < 分母 × wer)を使う。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2020/05/20 23:57

    恥ずかしい回答にも関わらずコメントありがとうございます。
    rationalの方が自前計算より桁数が抑えられるので速かったです。
    あと、werが20以下の整数のみであれば、予め計算した値を配列で持っておくのが一番高速だと思いました。

    キャンセル

  • 2020/05/21 00:05

    もう一点、rationalを使うなら、1/werで始めて、1/(n×wer)を足し込み、分子が分母以上で判定する方法もあると思います。

    キャンセル

  • 2020/05/21 10:22

    まだ上手くできてないですが、予め計算した値を配列で持っておくやり方の計算速度は早くなった体感があります。
    もう少し頑張ってみます!

    キャンセル

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 89.25%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる