Memoization в Python

[sash_ko]

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

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

[zzeus]

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

[sash_ko]

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

[zzeus]

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

[zzeus]

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

[zzeus]

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

[kmike]

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

[genk]

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

[Cancel]

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

[zzeus]

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

[non7top]

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

[zzeus]

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

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

[Ewka]

Большое спасибо, позновательно и необычно.
Хотелось бы видеть больше статей на тему декораторов.

[ssmaxss]

Сразу вспоминается вот это: code.activestate.com/recipes/498245/
Там еще сделан LRU cache, для экономии памяти, но не используется pickle