Как я могу написать декоратор Python для увеличения stackdepth?

Ответ 1

Чтобы обойти ограничение рекурсии, вы можете поймать исключение RuntimeError, чтобы обнаружить, когда вы закончили пространство стека, а затем вернуть функцию продолжения-ish, которая при вызове перезапускает рекурсию на уровне, где вы выбежали из космоса. Назовите это (и его возвращаемое значение и т.д.), Пока не получите значение, затем повторите попытку с вершины. Как только вы запомните нижние уровни, более высокие уровни не будут превышать лимит рекурсии, поэтому в конечном итоге это сработает. Поместите функцию повторного вызова-до-это в функцию обертки. В основном это ленивая версия вашей идеи разминки.

Здесь приведен пример с простой рекурсивной функцией "добавить числа от 1 до n включительно".

import functools

def memoize(func):
    cache = {}
    @functools.wraps(func)
    def wrapper(*args, **kwargs):
        key = args, tuple(sorted(kwargs.items()))
        if key in cache:
            return cache[key]
        else:
            result = func(*args, **kwargs)
            if not callable(result):
                cache[key] = result
            return result
    return wrapper

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            result = _addup(n - 1)
        except RuntimeError:
            return lambda: _addup(n)
        else:
            return result if callable(result) else result + n

def addup(n):
    result = _addup(n)
    while callable(result):
        while callable(result):
            result = result()
        result = _addup(n)
    return result

assert addup(5000) == sum(xrange(5001))

Вместо того, чтобы возвращать лямбда-функцию полностью обратно в цепочку вызовов, мы можем создать исключение для короткого замыкания, что улучшает производительность и упрощает код:

# memoize function as above, or you can probably use functools.lru_cache

class UnwindStack(Exception):
    pass

@memoize
def _addup(n):
    if n < 2:
        return n
    else:
        try:
            return _addup(n - 1) + n
        except RuntimeError:
            raise UnwindStack(lambda: _addup(n))

def _try(func, *args, **kwargs):
    try:
        return func(*args, **kwargs)
    except UnwindStack as e:
        return e[0]

def addup(n):
    result = _try(_addup, n)
    while callable(result):
        while callable(result):
            result = _try(result)
        result = _try(_addup, n)
    return result

Это остается довольно неэлегантным, хотя и все еще имеет достаточное количество накладных расходов, и я не могу себе представить, как вы могли бы сделать его декоратором. Думаю, Python действительно не подходит для такого рода вещей.

Ответ 2

Здесь реализована реализация, которая использует список выражений генератора в виде стека:

def run_stackless(frame):
    stack, return_stack = [(False, frame)], []
    while stack:
        active, frame = stack.pop()
        action, res = frame.send(return_stack.pop() if active else None)
        if action == 'call':
            stack.extend([(True, frame), (False, res)])
        elif action == 'tail':
            stack.append((False, res))
        elif action == 'return':
            return_stack.append(res)
        else:
            raise ValueError('Unknown action', action)
    return return_stack.pop()

Чтобы использовать его, вам необходимо преобразовать рекурсивную функцию в соответствии со следующими правилами:

 return expr                    -> yield 'return', expr
 recursive_call(args...)        -> (yield 'call', recursive_call(args...))
 return recursive_call(args...) -> yield 'tail', recursive_call(args...)

Например, с функцией стоимости как a * b, ваша функция будет выглядеть следующим образом:

def f(a,b):
    if a>=0 and b>=0:
        yield 'return', min((yield 'call', f(a-1,b)),
                            (yield 'call', f(b,a-1))) + (a * b)
    else:
        yield 'return', 0

Тестирование:

In [140]: run_stackless(g(30, 4))
Out[140]: 410

В Python 2.6.2 он, по-видимому, дает 8-10-кратное увеличение производительности по сравнению с прямыми вызовами.

Действие tail для хвостовой рекурсии:

def factorial(n):
    acc = [1]
    def fact(n):
        if n == 0:
            yield 'return', 0
        else:
            acc[0] *= n
            yield 'tail', fact(n - 1)
    run_stackless(fact(n))
    return acc[0]

Преобразование в рекурсивный генераторный стиль довольно простое, и его можно было бы, вероятно, сделать как взломанный байт-код.

Ответ 3

Этот подход сочетает в себе memoisation и увеличенную глубину стека в один декоратор.

Я создаю пул потоков с каждым потоком, отвечающим за 64 уровня стека.
Темы создаются только один раз и сохраняются (но в настоящее время они никогда не удаляются).

Очереди используются для передачи информации между потоками, хотя обратите внимание, что на самом деле будет работать только поток, соответствующий текущей глубине стека.

Мои эксперименты показывают, что это добавляет около 10% накладных расходов для простой рекурсивной функции (и должно быть меньше для более сложных функций).

import threading,Queue

class BigstackThread(threading.Thread):

    def __init__(self,send,recv,func):
        threading.Thread.__init__( self )
        self.daemon = True
        self.send = send
        self.recv = recv
        self.func = func

    def run(self):
        while 1:
            args = self.send.get()
            v = self.func(*args)
            self.recv.put(v)

class Bigstack(object):

    def __init__(self,func):
        self.func = func
        self.cache = {}
        self.depth = 0
        self.threadpool = {}

    def __call__(self,*args):
        if args in self.cache:
            return self.cache[args]
        self.depth+=1
        if self.depth&63:
            v = self.func(*args)
        else:
            T=self.threadpool
            if self.depth not in T:
                send = Queue.Queue(1)
                recv = Queue.Queue(1)
                t = BigstackThread(send,recv,self)
                T[self.depth] = send,recv,t
                t.start()
            else:
                send,recv,_ = T[self.depth]
            send.put(args)
            v = recv.get()

        self.depth-=1
        self.cache[args]=v
        return v

@Bigstack
def f(a,b):
    if a>=0 and b>=0:
        return min(f(a-1,b),f(b-1,a))+1
    return 0