zzeus Jan 28 2009 at 13:14

Memoization в Python

1 min

16K

Python*

+45

Comments 17

sash_ko Jan 28 2009 at 14:01

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

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

zzeus Jan 28 2009 at 14:04

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

sash_ko Jan 28 2009 at 14:27

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

zzeus Jan 28 2009 at 14:31

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

-1

UFO just landed and posted this here

zzeus Jan 28 2009 at 14:14

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

-1

UFO just landed and posted this here

zzeus Jan 28 2009 at 14:26

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

UFO just landed and posted this here

kmike Jan 29 2009 at 15:25

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

genk Jan 29 2009 at 11:04

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

Cancel Jan 29 2009 at 12:38

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

zzeus Jan 29 2009 at 12:56

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

non7top Jan 29 2009 at 11:32

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

zzeus Jan 29 2009 at 11:35

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

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

Ewka Jan 29 2009 at 12:06

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

ssmaxss Jan 29 2009 at 22:04

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

Show the best of all time