【Python基礎】再帰処理の回数を大幅に減らす方法

  • URLをコピーしました!
目次

再帰処理

前回、Pythonで再帰処理を使って面積を指定したガウス分布を作成する方法を紹介しました。

今回は前回の再帰処理を使って、再帰処理の回数を大幅に減らす方法を紹介します。

ちなみに前回の再帰処理のプログラムを少し変えて、経過を表示するようにしたプログラムがこちらです。

import numpy as np
import matplotlib.pyplot as plt

x_list = range(0, 1000)
y_param = [10, 500, 100]

n = 10000
target = 500
delta = 0.01

def gauss(x_list, a=1, m=0, s=1):
    y_list = [a * np.exp(-(x - m)**2 / (2*s**2)) for x in x_list]
    return y_list


def target_area(n, x_list, a, m, s, target, delta, i=0):
    y_list = gauss(x_list, a, m, s)
    y_area = sum(y_list)
    print(i, a, y_area)
    if n == 0:
        return "no answer..."
    elif y_area <= target:
        return a
    
    new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
    return new_a

new_a = target_area(n, x_list, y_param[0], y_param[1], y_param[2], target, delta)

original_y_list = gauss(x_list, y_param[0], y_param[1], y_param[2])
new_y_list = gauss(x_list, new_a, y_param[1], y_param[2])

y_area = sum(new_y_list)

fig = plt.figure()
plt.clf()

plt.plot(x_list, original_y_list)
plt.plot(x_list, new_y_list)

plt.show()

実行結果
0 10 2506.6268372625827
1 9.99 2504.1202104253234
2 9.98 2501.613583588058
3 9.97 2499.1069567507966
4 9.96 2496.600329913535
5 9.950000000000001 2494.0937030762716
(中略)
797 2.03000000000017 508.8452479643479
798 2.02000000000017 506.3386211270855
799 2.0100000000001703 503.8319942898231
800 2.0000000000001705 501.32536745256067
801 1.9900000000001705 498.818740615298

deltaを0.01としたときは約800回程度の再帰処理が行われて答えが出ています。

さらにdeltaを0.001とすると再帰処理の上限を超えてしまい、処理が強制終了されてしまいます。

import numpy as np
import matplotlib.pyplot as plt

x_list = range(0, 1000)
y_param = [10, 500, 100]

n = 10000
target = 500
delta = 0.001

def gauss(x_list, a=1, m=0, s=1):
    y_list = [a * np.exp(-(x - m)**2 / (2*s**2)) for x in x_list]
    return y_list


def target_area(n, x_list, a, m, s, target, delta, i=0):
    y_list = gauss(x_list, a, m, s)
    y_area = sum(y_list)
    print(i, a, y_area)
    if n == 0:
        return "no answer..."
    elif y_area <= target:
        return a
    
    new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
    return new_a

new_a = target_area(n, x_list, y_param[0], y_param[1], y_param[2], target, delta)

original_y_list = gauss(x_list, y_param[0], y_param[1], y_param[2])
new_y_list = gauss(x_list, new_a, y_param[1], y_param[2])

y_area = sum(new_y_list)

fig = plt.figure()
plt.clf()

plt.plot(x_list, original_y_list)
plt.plot(x_list, new_y_list)

plt.show()

実行結果
0 10 2506.6268372625827
1 9.999 2506.3761745788643
2 9.998000000000001 2506.125511895136
(中略)
2966 7.034000000000786 1763.161317330699
2967 7.0330000000007855 1762.9106546469782
2968 7.032000000000785 1762.6599919632508
---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[10], line 28
     25     new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
     26     return new_a
---> 28 new_a = target_area(n, x_list, y_param[0], y_param[1], y_param[2], target, delta)
     30 original_y_list = gauss(x_list, y_param[0], y_param[1], y_param[2])
     31 new_y_list = gauss(x_list, new_a, y_param[1], y_param[2])

Cell In[10], line 25, in target_area(n, x_list, a, m, s, target, delta, i)
     22 elif y_area <= target:
     23     return a
---> 25 new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
     26 return new_a

Cell In[10], line 25, in target_area(n, x_list, a, m, s, target, delta, i)
     22 elif y_area <= target:
     23     return a
---> 25 new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
     26 return new_a

    [... skipping similar frames: target_area at line 25 (2966 times)]

Cell In[10], line 25, in target_area(n, x_list, a, m, s, target, delta, i)
     22 elif y_area <= target:
     23     return a
---> 25 new_a = target_area(n-1, x_list, a-delta, m, s, target, delta, i=i+1)
     26 return new_a

Cell In[10], line 19, in target_area(n, x_list, a, m, s, target, delta, i)
     17 y_list = gauss(x_list, a, m, s)
     18 y_area = sum(y_list)
---> 19 print(i, a, y_area)
     20 if n == 0:
     21     return "no answer..."

File /Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/iostream.py:635, in OutStream.write(self, string)
    633     raise ValueError(msg)
    634 else:
--> 635     is_child = not self._is_master_process()
    636     # only touch the buffer in the IO thread to avoid races
    637     with self._buffer_lock:

File /Library/Frameworks/Python.framework/Versions/3.10/lib/python3.10/site-packages/ipykernel/iostream.py:506, in OutStream._is_master_process(self)
    505 def _is_master_process(self):
--> 506     return os.getpid() == self._master_pid

RecursionError: maximum recursion depth exceeded while calling a 
Python object

この様な場合、再帰処理の上限回数を上げるというのが一つの手で、その方法は前に紹介していますので、よかったらこちらの記事をどうぞ。

ただし再帰処理の上限回数を上げるということは力技でコストを掛けて解を見つけるということであまりCPUに優しい方法ではありません。

そこで今回の様に目標となる値がある場合、再帰処理の回数を減らす様なプログラムにするのが良いと考えられます。

ということで今回はその方法を紹介します。

それでは始めていきましょう。

再帰処理の回数を減らす方法

再帰処理の回数を減らすにはどういう処理をしたいかによって方針が異なると思いますが、今回の場合、再帰処理のたびに変数「delta」の分だけパラメータが減らされていって、指定した面積を下回るかを検討します。

つまりdeltaが小さければ小さいほど、再帰処理の回数が多くなるというわけです。

しかしながら最初の方は小さなdeltaで削っていっても、指定した面積にたどり着くことがないので、処理としてはほぼ無駄なわけです。

ということでdeltaを変動性にして、まずは大きなdeltaを使ってざっくりと値を削っていく、そして指定した面積を下回ったところで値を一度戻して、再度少し小さくしたdeltaで値を削っていくを繰り返します。

これにより無駄なところでちまちまとパラメータを減らしていく無駄が大幅に削減されます。

作成したプログラムはこんな感じです。

import numpy as np
import matplotlib.pyplot as plt

x_list = range(0, 1000)
y_param = [10, 500, 100]

n = 10000
target = 500
target_limit = 0.001
delta = [0.5, 0.1, 0.01, 0.001, 0.0001, 0.00001]

def gauss(x_list, a=1, m=0, s=1):
    y_list = [a * np.exp(-(x - m)**2 / (2*s**2)) for x in x_list]
    return y_list


def target_area(n, x_list, a, m, s, target, delta, delta_index=0, i=0):
    if n == 0:
        return "no answer..."
    elif delta_index >= len(delta):
        return "need more steps"
    
    delta_val = delta[delta_index]
    y_list = gauss(x_list, a, m, s)
    y_area = sum(y_list)
    print(i, a, y_area)
    
    if target - target_limit <= y_area <= target + target_limit:
        return a
    
    if y_area <= target:
        new_a = target_area(n-1, x_list, a+delta_val, m, s, target, delta, delta_index+1, i=i+1)
        return new_a
    
    new_a = target_area(n-1, x_list, a-delta_val, m, s, target, delta, delta_index, i=i+1)
    
    return new_a

new_a = target_area(n, x_list, y_param[0], y_param[1], y_param[2], target, delta)

original_y_list = gauss(x_list, y_param[0], y_param[1], y_param[2])
new_y_list = gauss(x_list, new_a, y_param[1], y_param[2])

y_area = sum(new_y_list)

fig = plt.figure()
plt.clf()

plt.plot(x_list, original_y_list)
plt.plot(x_list, new_y_list)

plt.show()

変わったところとしては新たに「target_limit」という変数ができたことと、「delta」がリストになったことです。

target_limit = 0.001
delta = [0.5, 0.1, 0.01, 0.001, 0.0001, 0.00001]

target_limitは目標値であるtargetと合わせて「target±target_limit」の値になったときに処理が終了するための条件分岐に使います。

    if target - target_limit <= y_area <= target + target_limit:
        return a

また処理が終了するための条件に引っ掛からず、目標値よりも小さくなった場合、パラメータ「a」の値を戻しつつ、deltaのリストの要素を次の要素(より小さなdelta)へと移動するようにします。

    if y_area <= target:
        new_a = target_area(n-1, x_list, a+delta_val, m, s, target, delta, delta_index+1, i=i+1)
        return new_a

実際使ってみましょう。

import numpy as np
import matplotlib.pyplot as plt

x_list = range(0, 1000)
y_param = [10, 500, 100]

n = 10000
target = 500
target_limit = 0.001
delta = [0.5, 0.1, 0.01, 0.001, 0.0001, 0.00001]

def gauss(x_list, a=1, m=0, s=1):
    y_list = [a * np.exp(-(x - m)**2 / (2*s**2)) for x in x_list]
    return y_list


def target_area(n, x_list, a, m, s, target, delta, delta_index=0, i=0):
    if n == 0:
        return "no answer..."
    elif delta_index >= len(delta):
        return "need more steps"
    
    delta_val = delta[delta_index]
    y_list = gauss(x_list, a, m, s)
    y_area = sum(y_list)
    print(i, a, y_area)
    
    if target - target_limit <= y_area <= target + target_limit:
        return a
    
    if y_area <= target:
        new_a = target_area(n-1, x_list, a+delta_val, m, s, target, delta, delta_index+1, i=i+1)
        return new_a
    
    new_a = target_area(n-1, x_list, a-delta_val, m, s, target, delta, delta_index, i=i+1)
    
    return new_a

new_a = target_area(n, x_list, y_param[0], y_param[1], y_param[2], target, delta)

original_y_list = gauss(x_list, y_param[0], y_param[1], y_param[2])
new_y_list = gauss(x_list, new_a, y_param[1], y_param[2])

y_area = sum(new_y_list)

fig = plt.figure()
plt.clf()

plt.plot(x_list, original_y_list)
plt.plot(x_list, new_y_list)

plt.show()

実行結果
0 10 2506.6268372625827
1 9.5 2381.2954953994563
2 9.0 2255.9641535363276
3 8.5 2130.632811673203
4 8.0 2005.3014698100712
(中略)
38 1.9947500000000002 500.00938836295495
39 1.9947400000000002 500.0068817361169
40 1.9947300000000001 500.00437510928
41 1.99472 500.0018684824427
42 1.99471 499.99936185560557

先ほどはdeltaが0.01で800回ほど繰り返されていた処理が、最小のdeltaが0.00001にもかかわらず40回ほどの処理で済んでいます。

ということでもちろん力技でやるべきところもあるでしょうが、大量の処理をする必要ができた際は一度立ち止まって処理により負荷を低減できないか考えてみることも必要かなと思います。

次回は再帰処理でちょっと楽しみができる金利計算を試してみたのでそのプログラムを紹介します。

ではでは今回はこんな感じで。

よかったらシェアしてね!
  • URLをコピーしました!

コメント

コメントする

目次