Предел рекурсии в Python при индексации - PullRequest
0 голосов
/ 29 января 2019

Я дурачился с пределом рекурсии в Python, который можно динамически изменять с помощью sys.setrecursionlimit(limit).Приведенный ниже код демонстрирует, что целое число limit точно соответствует максимальной глубине, допустимой для рекурсивных вызовов функций.

Для рекурсивного индексирования с использованием [], похоже, применяется тот же предел рекурсии,но, очевидно, с коэффициентом 3, что означает, что я могу индексировать в три раза глубже, чем могу позвонить: enter image description here

Приведенный выше график генерируется с помощью кода ниже.

import itertools, sys
import numpy as np
import matplotlib.pyplot as plt

limits = np.arange(10, 500, 100)

# Find max depth of recursive calls
maxdepth = []
for limit in limits:
    sys.setrecursionlimit(limit)
    try:
        n = [0]
        def fun(n=n):
            n[0] += 1
            fun()
        fun()
    except RecursionError:
        maxdepth.append(n[0])
a, b = np.polyfit(limits, maxdepth, 1)
plt.plot(limits, maxdepth, '*')
plt.plot(limits, a*limits + b, '-', label='call')
plt.text(np.mean(limits), a*np.mean(limits) + b, f'slope = {a:.2f}')

# Find max depth of getitem
maxdepth = []
n = 0
l = []; l.append(l)
for limit in limits:
    sys.setrecursionlimit(limit)
    for n in itertools.count(n):
        try:
            eval('l' + '[-1]'*n)
        except RecursionError:
            break
    maxdepth.append(n)
a, b = np.polyfit(limits, maxdepth, 1)
plt.plot(limits, maxdepth, '*')
plt.plot(limits, a*limits + b, '-', label='getitem')
plt.text(np.mean(limits), a*np.mean(limits) + b, f'slope = {a:.2f}')

plt.xlabel('Recursion limit')
plt.ylabel('Max depth')
plt.legend()
plt.savefig('test.png')

Чтобы проверить рекурсивное индексирование, я добавляю к себе список l и создаю длинный литерал [-1][-1][-1]..., который я затем вычисляю на l динамически.

Вопрос: Объясните этот коэффициент 3.

1 Ответ

0 голосов
/ 31 января 2019

Там нет рекурсии в l[-1][-1]… - он компилируется в «push l;заменить вершину стека своим последним элементом;заменить ...».Ваш RecursionError из компилирует длинную строку.

Существует буквально коэффициент 3 , используемый для аппроксимации использования стека байтовым компилятором против собственно переводчик.(Python 2 не имеет такого ограничения и просто падает при таких выражениях.)

...