note.nkmk.me

Pythonの再帰回数の上限を確認・変更(sys.setrecursionlimitなど)

Posted: 2019-08-18 / Tags: Python

Pythonでは再帰回数の上限(最大再帰数)が設定されている。呼び出し回数の多い再帰関数を実行するには上限を変更する必要がある。標準ライブラリのsysモジュールの関数を使う。

再帰回数はスタックサイズによっても制限される。環境によっては標準ライブラリのresourceモジュールで最大スタックサイズを変更できる(Ubuntuではうまくいったが、Windows, macではうまくいかなかった)。

ここでは以下の内容について説明する。

  • 現在の再帰回数の上限を取得: sys.getrecursionlimit()
  • 再帰回数の上限を変更: sys.setrecursionlimit()
  • スタックの最大サイズを変更: resource.setrlimit()

サンプルコードはUbuntuで実行している。

スポンサーリンク

現在の再帰回数の上限を取得: sys.getrecursionlimit()

現在の再帰回数の上限はsys.getrecursionlimit()で取得可能。

import sys
import resource

print(sys.getrecursionlimit())
# 1000

例の場合は1000。環境によっては異なる場合がある。なお、ここでインポートしているresourceはあとで使う。Windowsには無いので注意。

例として以下の簡単な再帰関数を使用する。正の整数nを引数に指定すると呼び出し回数はn回となる。

def recu_test(n):
    if n == 1:
        print('Finish')
        return
    recu_test(n - 1)

上限を超える回数の再帰を実行しようとするとエラー(RecursionError)が発生する。

recu_test(950)
# Finish

# recu_test(1500)
# RecursionError: maximum recursion depth exceeded in comparison

なお、sys.getrecursionlimit()で取得できる値は厳密には最大再帰回数ではなくPyhtonインタープリタのスタックの深さ(?)の最大値であるため、この値より若干少ない再帰回数であってもエラー(RecursionError)となる。

The recursion limit is not the limit on recursion but the maximum depth of the python interpreter stack
python - Max recursion is not exactly what sys.getrecursionlimit() claims. How come? - Stack Overflow

# recu_test(995)
# RecursionError: maximum recursion depth exceeded while calling a Python object

再帰回数の上限を変更: sys.setrecursionlimit()

再帰回数の上限はsys.setrecursionlimit()で変更可能。引数に上限値を指定する。

より深い再帰を実行できるようになる。

sys.setrecursionlimit(2000)

print(sys.getrecursionlimit())
# 2000

recu_test(1500)
# Finish

指定した上限値が小さすぎたり大きすぎたりするとエラーとなる。この制約(上限値そのものの上限・下限)は環境によって異なる。

limit の最大値はプラットフォームによって異なります。深い再帰処理が必要な場合にはプラットフォームがサポートしている範囲内でより大きな値を指定することができますが、この値が大きすぎればクラッシュするので注意が必要です。
If the new limit is too low at the current recursion depth, a RecursionError exception is raised.
sys.setrecursionlimit() --- システムパラメータと関数 — Python 3.7.4 ドキュメント

sys.setrecursionlimit(4)
print(sys.getrecursionlimit())
# 4

# sys.setrecursionlimit(3)
# RecursionError: cannot set the recursion limit to 3 at the recursion depth 1: the limit is too low

sys.setrecursionlimit(10 ** 9)
print(sys.getrecursionlimit())
# 1000000000

# sys.setrecursionlimit(10 ** 10)
# OverflowError: signed integer is greater than maximum

また、次に説明するように最大再帰回数はスタックサイズによっても制限される。

スタックの最大サイズを変更: resource.setrlimit()

sys.setrecursionlimit()で大きな値を設定しても再帰回数が多いと実行できない場合がある。以下のようにセグメンテーション違反(Segmentation fault)が発生する。

sys.setrecursionlimit(10 ** 9)
print(sys.getrecursionlimit())
# 1000000000
recu_test(10 ** 4)
# Finish

# recu_test(10 ** 5)
# Segmentation fault

Pythonでは標準ライブラリのresourceモジュールでスタックの最大サイズを変更できる。ただし、resourceモジュールはUnix固有のモジュールなのでWindowsでは使えない。

resource.getrlimit()で、引数に指定したリソースのリミットを(ソフトリミット, ハードリミット)のタプルで取得できる。ここではリソースとして、現在のプロセスのコールスタックの最大サイズを表すresource.RLIMIT_STACKを指定する。

print(resource.getrlimit(resource.RLIMIT_STACK))
# (8388608, -1)

例ではソフトリミットが8388608(8388608 B = 8192 KB = 8 MB)、ハードリミットが-1(無制限)となっている。

resource.setrlimit()でリソースのリミットを変更できる。ここではソフトリミットも-1(無制限)に設定する。無制限を表す定数resource.RLIM_INFINITを使ってもよい。

スタックサイズ変更前にセグメンテーション違反(Segmentation fault)で実行できなかった深い再帰を実行できるようになる。

resource.setrlimit(resource.RLIMIT_STACK, (-1, -1))

print(resource.getrlimit(resource.RLIMIT_STACK))
# (-1, -1)

recu_test(10 ** 5)
# Finish

ここでは簡易的な実験のためソフトリミットを-1(無制限)に設定しているが、現実的には適当な値で制限しておいたほうが安心だろう。

なお、macでは同様に無制限のソフトリミットを設定しようとするとValueError: not allowed to raise maximum limitというエラーが発生した。sudoでスクリプトを実行してもダメだった。システムで制限されているのかもしれない。

スーパーユーザの実効 UID を持ったプロセスは無制限を含めあらゆる妥当な制限値を要求出来ますが、システムが課している制限を超過した要求ではやはり ValueError となります。
resource.setrlimit() --- リソース使用状態の情報 — Python 3.7.4 ドキュメント

Windowsにはそもそもresourceモジュールが無く、macではシステムの制限(?)で最大スタックサイズの変更ができなかった。何らかの手段でスタックサイズを大きくできればSegmentation faultは解消できるはずだが確認できていない。

スポンサーリンク
シェア
このエントリーをはてなブックマークに追加

関連カテゴリー

関連記事