zzeus 28 янв 2009 в 13:14

Memoization в Python

1 мин

16K

Python*

+45

Комментарии 17

sash_ko 28 янв 2009 в 14:01

Интересный способ, а что если уменьшить потери памяти за счет использования функции hash():

key = hash( cPickle.dumps((args, sorted(kwargs.iteritems()))) )

zzeus 28 янв 2009 в 14:04

зависит от размера пиклезованых аргументов. если небольшие — hash создаст лишние вычислительные расходы. Если большие — действительно, неплохо.

sash_ko 28 янв 2009 в 14:27

Время вычисления хеша на порядок меньше времени «пиклизации» (несложно написать 3 строки и убедиться в этом), так что это не создаст большую проблему, а экономия памяти будет значительная. Кстати, если передаваемые аргументы имеют большой размер, то сложность вычислений bigfunc должна быть больше, чем dumps, что бы вообще имела смысл меморизация.

zzeus 28 янв 2009 в 14:31

мемоизация вообще имеет смысл для сложных (точнее долго вычисляемых) функций.

-1

НЛО прилетело и опубликовало эту надпись здесь

zzeus 28 янв 2009 в 14:14

pickle — быстрая сериализация в python

-1

НЛО прилетело и опубликовало эту надпись здесь

zzeus 28 янв 2009 в 14:26

сериализация бывает разная :] конкретно здесь — пиклезация. Может ваш объект pickle не ест, но какаянить megaserial — вполне кушает.

НЛО прилетело и опубликовало эту надпись здесь

kmike 29 янв 2009 в 15:25

пиклезуемые — те, которые может сериализовать функция pickle

genk 29 янв 2009 в 11:04

А что будет если функция рекурсивная, а мы хотим добавить Memoization, чтобы переделать её в динамический алгоритм? Этот метод подойдет? Если да, то очень элегантно…

Cancel 29 янв 2009 в 12:38

Я так понимаю, что закешируются все промежуточные значения. Поэтому, если уровней рекурсии было много, получим много бесполезного ужаса, поиск по которому может оказаться неэффективнее повторного вычисления.

zzeus 29 янв 2009 в 12:56

зависит от функции. например класическое фибоначчи без генератора (fib(n)=fib(n-1)+fib(n-2)) — при частых вызовах с мемоизацией экономит кучу вычислительной мощности. Единственный вопрос — не не будет ли запрос fib(100000000) :] но это легко обойти, как я уже написал.

non7top 29 янв 2009 в 11:32

а память не утечет?

zzeus 29 янв 2009 в 11:35

вычисленные результаты будут храниться все время существования функции (до del, например). чуть модифицировав можно ограничить как количество так и время хранения. но это уже по желанию :]

«утечка» как таковая в питоне в принципе невозможна. как только пропадут все ссылки на объект, за ним придет GC :]