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

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

新規登録して質問してみよう
ただいま回答率
85.50%
Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

Q&A

解決済

3回答

609閲覧

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

huyusyougun1224

総合スコア1

Ruby

Rubyはプログラミング言語のひとつで、オープンソース、オブジェクト指向のプログラミング開発に対応しています。

0グッド

1クリップ

投稿2020/05/19 16:06

前提・実現したいこと

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

該当のソースコード

ruby

1@memo = {} 2 3def sum(wer) 4 return @memo[[wer]] if @memo[[wer]] 5 total = 0 6 n = 0 7 while total < wer do 8 rat = [] 9 n = n + 1 10 denomi = 1..n 11 denomi.each do |den| 12 r = Rational(1, den) 13 rat << r 14 end 15 total = rat.sum 16 @memo[[wer]] = total 17 end 18 rat.inspect 19 rat.last 20end 21 22puts sum(15)

ruby

1require 'memoist' 2 class Person 3 extend Memoist 4 def sum(wer) 5 n = 0 6 i = 0 7 while i < wer 8 n += 1 9 i = i + Rational(1, n) 10 end 11 puts n 12 end 13 memoize :sum 14 end 15 16 person = Person.new 17 person.sum(15)

試したこと

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

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

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

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

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

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

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

ozwk

2020/05/20 07:06

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

2020/05/20 07:32

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

回答3

0

ベストアンサー

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

Ruby

1MAX = ARGV[0].to_i 2RAT_NUM = 1070 3 4puts "float simple addition" 5sum = 0.0 6wer = 1 7n = 0 8stime = Time.now 9while wer <= MAX do 10 n += 1 11 sum += 1.0/n 12 if sum > wer then 13 printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum, Time.now-stime) 14 wer += 1 15 end 16end 17 18puts "rational nume/deno addition" 19deno = 1 20nume = 0 21wer = 1 22n = 0 23stime = Time.now 24while wer <= MAX do 25 n += 1 26 nume = nume * n + deno 27 deno *= n 28 if nume > wer * deno then 29 sum = Rational(nume, deno) 30 printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime) 31 wer += 1 32 nume = sum.numerator 33 deno = sum.denominator 34 elsif n % RAT_NUM == 0 then 35 sum = Rational(nume, deno) 36 nume = sum.numerator 37 deno = sum.denominator 38 end 39end 40 41puts "rational simple addition" 42sum = Rational(0) 43wer = 1 44n = 0 45stime = Time.now 46while wer <= MAX do 47 n += 1 48 sum += Rational(1,n) 49 if sum > wer then 50 printf("wer=%2d, n=%10d, sum=%.15e, elapse=%f\n", wer, n, sum.to_f, Time.now-stime) 51 wer += 1 52 end 53end 54 55float simple addition 56wer= 1, n= 2, sum=1.500000000000000e+00, elapse=0.000000 57wer= 2, n= 4, sum=2.083333333333333e+00, elapse=0.001000 58wer= 3, n= 11, sum=3.019877344877345e+00, elapse=0.001000 59wer= 4, n= 31, sum=4.027245195436520e+00, elapse=0.002002 60wer= 5, n= 83, sum=5.002068272680166e+00, elapse=0.002002 61wer= 6, n= 227, sum=6.004366708345567e+00, elapse=0.003019 62wer= 7, n= 616, sum=7.001274097134162e+00, elapse=0.003019 63wer= 8, n= 1674, sum=8.000485571995782e+00, elapse=0.003993 64wer= 9, n= 4550, sum=9.000208062931115e+00, elapse=0.003993 65wer=10, n= 12367, sum=1.000004300827578e+01, elapse=0.004990 66wer=11, n= 33617, sum=1.100001770863642e+01, elapse=0.006985 67wer=12, n= 91380, sum=1.200000305166562e+01, elapse=0.012998 68wer=13, n= 248397, sum=1.300000122948093e+01, elapse=0.027957 69rational nume/deno addition 70wer= 1, n= 2, sum=1.500000000000000e+00, elapse=0.000000 71wer= 2, n= 4, sum=2.083333333333333e+00, elapse=0.000000 72wer= 3, n= 11, sum=3.019877344877345e+00, elapse=0.001030 73wer= 4, n= 31, sum=4.027245195436520e+00, elapse=0.001998 74wer= 5, n= 83, sum=5.002068272680166e+00, elapse=0.001998 75wer= 6, n= 227, sum=6.004366708345566e+00, elapse=0.003051 76wer= 7, n= 616, sum=7.001274097134161e+00, elapse=0.005050 77wer= 8, n= 1674, sum=8.000485571995780e+00, elapse=0.009068 78wer= 9, n= 4550, sum=9.000208062931140e+00, elapse=0.030012 79wer=10, n= 12367, sum=1.000004300827581e+01, elapse=0.096833 80wer=11, n= 33617, sum=1.100001770863643e+01, elapse=0.440332 81wer=12, n= 91380, sum=1.200000305166563e+01, elapse=2.853218 82wer=13, n= 248397, sum=1.300000122948078e+01, elapse=19.173152 83rational simple addition 84wer= 1, n= 2, sum=1.500000000000000e+00, elapse=0.000000 85wer= 2, n= 4, sum=2.083333333333333e+00, elapse=0.000997 86wer= 3, n= 11, sum=3.019877344877345e+00, elapse=0.000997 87wer= 4, n= 31, sum=4.027245195436520e+00, elapse=0.001996 88wer= 5, n= 83, sum=5.002068272680166e+00, elapse=0.002991 89wer= 6, n= 227, sum=6.004366708345566e+00, elapse=0.003988 90wer= 7, n= 616, sum=7.001274097134161e+00, elapse=0.019946 91wer= 8, n= 1674, sum=8.000485571995780e+00, elapse=0.030916 92wer= 9, n= 4550, sum=9.000208062931140e+00, elapse=0.061500 93wer=10, n= 12367, sum=1.000004300827581e+01, elapse=0.295848 94wer=11, n= 33617, sum=1.100001770863643e+01, elapse=1.830510 95wer=12, n= 91380, sum=1.200000305166563e+01, elapse=12.718921 96wer=13, n= 248397, sum=1.300000122948078e+01, elapse=97.580847

投稿2020/05/23 07:44

etsuhisa

総合スコア416

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

huyusyougun1224

2020/05/24 01:12

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

0

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

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 10:22

編集2020/05/20 10:23
etsuhisa

総合スコア416

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

etsuhisa

2020/05/20 11:48

速くないので忘れてください。
huyusyougun1224

2020/05/20 14:23

回答ありがとうございます。 判定を割り算でなく掛け算で行う事は目から鱗でした。上記のコードを参考に少しロジックを変えて試してみようと思います。
etsuhisa

2020/05/20 14:57

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

2020/05/20 15:05

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

2020/05/21 01:22

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

0

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

投稿2020/05/19 20:50

winterboum

総合スコア23284

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

huyusyougun1224

2020/05/20 01:24

回答ありがとうございます。 はい、加算は 1 + 1/2 + 1/3 + 1/4 + ... で行っています。 毎回計算式が変わるのでメモ化は出来ないのですね。 メモ化以外の方法で計算速度をあげる事は可能なのでしょうか?
winterboum

2020/05/20 02:03

この数列では、私には思いつきません。 漸化式があればそれを使うのが(精度の吟味は必要ですが)高速化の手ですが、この数列では無いですよね?
huyusyougun1224

2020/05/20 06:17

漸化式であれば 、 a (n+1) = 1 / "a(n+1)" となりそうですが、 ” ” で囲む部分が分母に当たるので、漸化式として成立するのか解らないです。 計算を行うロジックを考え直した方がいいのでしょうか?
winterboum

2020/05/20 06:31

ごめん、漸化式ではない、なんと言うのかな、この場合 Σ1/n を求める式はないので、概算というか近似式というか。 ロジックですが、 werを越えるのが n だとすると 1/i をn回、+を n回 行うのを減らすロジックを考えないとならないですが、可能?
huyusyougun1224

2020/05/20 07:31

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

2020/05/20 07:52

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

2020/05/20 08:45

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

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

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

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問