Замыкания в Python

Question

Я пытался изучать Python, и, хотя я с энтузиазмом относился к использованию замыканий в Python, у меня были проблемы с настройкой кода для правильной работы:

def memoize(fn):
    def get(key):
        return (False,)

    def vset(key, value):
        global get
        oldget = get
        def newget(ky):
            if key==ky: return (True, value)
            return oldget(ky)
        get = newget

    def mfun(*args):
        cache = get(args)
        if (cache[0]): return cache[1]

        val = apply(fn, args)
        vset(args, val)
        return val

    return mfun

def fib(x):
    if x<2: return x
    return fib(x-1)+fib(x-2)

def fibm(x):
    if x<2: return x
    return fibm(x-1)+fibm(x-2)

fibm = memoize(fibm)

По сути, это то, что предполагается сделать, это использовать замыкания для поддержания запомненного состояния функции. Я понимаю, что, вероятно, есть много более быстрых, простых для чтения и в целом более «питонских» способов реализовать это; однако моя цель - понять, как именно замыкания работают в Python и чем они отличаются от Lisp, поэтому меня не интересуют альтернативные решения, просто почему мой код не работает и что я могу сделать (если что-нибудь), чтобы исправить это.

Проблема, с которой я сталкиваюсь, заключается в том, что когда я пытаюсь использовать fibm - Python настаивает, что get не определено:

Python 2.6.1 (r261:67515, Feb  1 2009, 11:39:55) 
[GCC 4.0.1 (Apple Inc. build 5488)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import memoize
>>> memoize.fibm(35)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "memoize.py", line 14, in mfun
    cache = get(args)
NameError: global name 'get' is not defined
>>> 

Видя, что я новичок в Python, я не знаю, сделал ли я что-то не так или это просто ограничение языка. Я надеюсь, что это первое. : -)

Answer 1

def memoize(fn):
  get = [lambda key: (False, None)]

  def vset(args):
    value = fn(*args)
    oldget = get[0]
    def newget(key):
      if args == key:
        return (True, value)
      return oldget(key)
    get[0] = newget
    return value

  def mfun(*args):
    found, value = get[0](args)
    if found:
      return value
    return vset(args)

  return mfun

CALLS = 0

def fib(x):
  global CALLS
  CALLS += 1
  if x<2: return x
  return fib(x-1)+fib(x-2)

@memoize
def fibm(x):
  global CALLS
  CALLS += 1
  if x<2: return x
  return fibm(x-1)+fibm(x-2)

CALLS = 0
print "fib(35) is", fib(35), "and took", CALLS, "calls"
CALLS = 0
print "fibm(35) is", fibm(35), "and took", CALLS, "calls"

Вывод:

fib(35) is 9227465 and took 29860703 calls
fibm(35) is 9227465 and took 36 calls

Аналогично другим ответам, однако этот работает. :)

Важным изменением кода в вопросе является присвоение неглобального нелокального (get); Тем не менее, я также сделал некоторые улучшения, пытаясь сохранить закрытие * кашель * * кашель *. Обычно кеш - это диктат, а не связанный список замыканий.

Answer 2

Проблема в том, что вы находитесь в области видимости, а не в замыканиях. Если вас интересует какое-то серьезное чтение, попробуйте http://www.python.org/dev/peps/pep-3104/.

Если это не так, вот простое объяснение:

Проблема в утверждении global get. global относится к самой внешней области видимости, и поскольку не существует глобальной функции get, она выбрасывает.

То, что вам нужно, это спецификатор доступа к переменным во вложенной области, а не глобальная область.

В python 3.0, как я уже тестировал, ключевое слово nonlocal именно то, что вам нужно, вместо global.

nonlocal get
...

В python 2.x я только что удалил ссылки global get и oldget, и он работает правильно.

Answer 3

Get не глобально, а локально для окружающей функции, поэтому объявление global не выполняется.

Если вы удалите global, он все равно не будет выполнен, поскольку вы не можете присвоить захваченное имя переменной. Чтобы обойти это, вы можете использовать объект в качестве переменной, захваченной вашими замыканиями, а затем просто изменить свойства этого объекта:

class Memo(object):
    pass

def memoize(fn):
    def defaultget(key):
        return (False,)

    memo = Memo()
    memo.get = defaultget

    def vset(key, value):
        oldget = memo.get
        def newget(ky):
            if key==ky: return (True, value)
            return oldget(ky)
        memo.get = newget

    def mfun(*args):
        cache = memo.get(args)
        if cache[0]: return cache[1]

        val = apply(fn, args)
        vset(args, val)
        return val

    return mfun

Таким образом, вам не нужно присваивать захваченным именам переменных, но вы все равно получаете то, что хотели.

Answer 4

Вы хотите поставить global get в начале каждой функции (кроме самой get).

def get - это присвоение имени get, поэтому вы хотите быть объявленным глобальным до этого.

Помещение global get в mfun и vset заставляет их работать. Я не могу указать на общие правила, которые делают это необходимым, но это работает; -)

Твои мошенники тоже довольно шумные ...:)

Answer 5

Я думаю, что лучший способ будет:

class Memoized(object):
    def __init__(self,func):
        self.cache = {}
        self.func = func
    def __call__(self,*args):
        if args in self.cache: return cache[args]
        else:
            self.cache[args] = self.func(*args)
            return self.cache[args]

Answer 6

Возможно, потому что вы хотите получить global , пока он не глобальный? Кстати, apply устарело, вместо этого используйте fn (* args).

def memoize(fn):
    def get(key):
        return (False,)

    def vset(key, value):
        def newget(ky):
            if key==ky: return (True, value)
            return get(ky)
        get = newget

    def mfun(*args):
        cache = get(args)
        if (cache[0]): return cache[1]

        val = fn(*args)
        vset(args, val)
        return val

    return mfun

def fib(x):
    if x<2: return x
    return fib(x-1)+fib(x-2)

def fibm(x):
    if x<2: return x
    return fibm(x-1)+fibm(x-2)

fibm = memoize(fibm)