Python func_dict используется для запоминания; другие полезные трюки? - PullRequest
Новая
       46

Python func_dict используется для запоминания; другие полезные трюки?

6 голосов
/ 19 ноября 2009

Объект функции Python имеет словарь атрибутов с именем func_dict, который виден снаружи функции и является изменяемым, но не изменяется при вызове функции. (Я узнал об этом из ответов на вопрос, который я задал вчера (# 1753232): спасибо!) Я читал код (на http://pythonprogramming.jottit.com/functional_programming), который запомнил вычисление чисел Фибоначчи и подумал: «Почему бы не использовать func_dict атрибут для запоминания? "Это сработало (см. ниже; выходные данные находятся в конце кода.). Это немного похоже на наличие свойства класса, но с кодом инициализации вне объекта (в данном случае, не класс, а функция ).

Интересно, , какие похожие (или разные) трюки можно сделать с помощью этого атрибута ? 

def fib(n):
    if n in fib.cache:
        print "found fib.cache[%d] = %d: " %(n, fib.cache[n])
        return fib.cache[n]
    else:
        print "fib.cache[%d] = fib(%d) + fib(%d)" % (n, n-1, n-2)
        fib.cache[n] = fib(n-1) + fib(n-2)
        print "modified fib.cache: ", fib.cache
        return fib.cache[n]

fib.cache = {0:0, 1:1}

for x in range(7):
    print "==================>", x
    print fib( x)

"""
==================> 0
found fib.cache[0] = 0: 
0
==================> 1
found fib.cache[1] = 1: 
1
==================> 2
fib.cache[2] = fib(1) + fib(0)
found fib.cache[1] = 1: 
found fib.cache[0] = 0: 
modified fib.cache:  {0: 0, 1: 1, 2: 1}
1
==================> 3
fib.cache[3] = fib(2) + fib(1)
found fib.cache[2] = 1: 
found fib.cache[1] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2}
2
==================> 4
fib.cache[4] = fib(3) + fib(2)
found fib.cache[3] = 2: 
found fib.cache[2] = 1: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3}
3
==================> 5
fib.cache[5] = fib(4) + fib(3)
found fib.cache[4] = 3: 
found fib.cache[3] = 2: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5}
5
==================> 6
fib.cache[6] = fib(5) + fib(4)
found fib.cache[5] = 5: 
found fib.cache[4] = 3: 
modified fib.cache:  {0: 0, 1: 1, 2: 1, 3: 2, 4: 3, 5: 5, 6: 8}
8
"""

Ответы [ 2 ]

7 голосов
/ 19 ноября 2009

Только будьте осторожны: трюк fib.cache работает только в том случае, если fib действительно является именем соответствующего функционального объекта в области, которая активна во время его выполнения (например, когда вы украшаете его, как вы это сделали, вы должны присвойте начальное значение для кэша оболочке декоратора, а не декорированной функции - и, если после этого он будет декорирован, все прекратится).

Это немного хрупко по сравнению со стандартной идиомой запоминания: 

def fib(n, _memo={0:1, 1:1}):
    if n in _memo:
        return _memo[n]
    else:
        _memo[n] = fib(n-1) + fib(n-2)
        return _memo[n]

или эквивалент декоратора. Стандартная идиома также быстрее (хотя и ненамного) - помещая их оба в mem.py под именами fib1 (.cache-trick, без отпечатков и без отделки) и fib2 (моя версия), мы видим ...: 

$ python -mtimeit -s'import mem' 'mem.fib1(20)'
1000000 loops, best of 3: 0.754 usec per loop
$ python -mtimeit -s'import mem' 'mem.fib2(20)'
1000000 loops, best of 3: 0.507 usec per loop

Таким образом, стандартная версия экономит около 33% времени, но именно тогда почти все вызовы действительно попадают в кэш напоминаний (который заполняется после первого из этих миллионов циклов) - преимущество в скорости fib2 меньше отсутствует кеш, так как он происходит из-за более высокой скорости доступа к _memo (локальная переменная) по сравнению с fib.cache (глобальное имя, fib, а затем его атрибут, кеш), а доступ к кешу преобладает при обращениях к кешу (нет ничего еще ;-) но есть небольшая дополнительная работа (равная для обеих функций) при промахах кэша.

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

1 голос
/ 30 декабря 2009

Я всегда использовал эту технику для запоминания. Он использует тот факт, что вы можете вызывать объект , который не является функцией, если для этого объекта определен метод __call__. По какой-то причине мне не приходило в голову ни метода за спиной, ни метода Алекса Мартелли. Я полагаю, что производительность примерно такая же, как у backthefall, потому что она работает примерно так же. Может быть немного медленнее. Но, как указывает связанная страница, «определение fib () теперь является« очевидным »без кеширующего кода, скрывающего алгоритм», что довольно приятно.

...