Memoization в Python

    Memoization – свойство функций сохранять (кешировать) результаты вычислений, дабы не вычислять в последствии повторно.

    Эта технология оптимизации позволят достичь прироста скорости работы за счет потерь в свободной памяти.

    Допустим, у нас есть некая функция bigfunc, результат которой зависят только от переданных в нее аргументов, а сложность вычислений достаточно большая. Естественно нам не хотелось бы производить вычисления при каждом вызове bigfunc если она уже вызывалась ранее с теми же параметрами. Тут то нам на помощь и приходит memoization.

    Для python декоратор для функции будет выглядеть следующим образом:

    import cPickle
    def memoized(func):
        memory = {}
        def memo(*args,**kwargs):
           hash = cPickle.dumps((args, sorted(kwargs.iteritems())))
           if hash not in memory:
               memory[hash] = func(*args,**kwargs)
           return memory[hash]
        return memo
    

    Далее, нам достаточно объявить bigfunc как

    @memoized
    def bigfunc(…):
    …

    Или переопределить, если она уже объявлена:

    bigfunc = memoized(bigfunc)

    Декоратор, объявленный в начале статьи, работает только с пиклезуемыми объектами. Если ваша функция работает с непиклезуемыми объектами – вы можете заменить

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

    на

    hash = (tuple(args), frozenset(kwargs.items())

    но вы потеряете возможность работы с mutable объектами.

    Декоратор можно легко модифицировать, для ограничения количества закешированных элементов.
    Поделиться публикацией
    Ой, у вас баннер убежал!

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

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

        0
        зависит от размера пиклезованых аргументов. если небольшие — hash создаст лишние вычислительные расходы. Если большие — действительно, неплохо.
          +1
          Время вычисления хеша на порядок меньше времени «пиклизации» (несложно написать 3 строки и убедиться в этом), так что это не создаст большую проблему, а экономия памяти будет значительная. Кстати, если передаваемые аргументы имеют большой размер, то сложность вычислений bigfunc должна быть больше, чем dumps, что бы вообще имела смысл меморизация.
            –1
            мемоизация вообще имеет смысл для сложных (точнее долго вычисляемых) функций.
      • НЛО прилетело и опубликовало эту надпись здесь
          –1
          pickle — быстрая сериализация в python
          • НЛО прилетело и опубликовало эту надпись здесь
              0
              сериализация бывает разная :] конкретно здесь — пиклезация. Может ваш объект pickle не ест, но какаянить megaserial — вполне кушает.
              • НЛО прилетело и опубликовало эту надпись здесь
              0
              пиклезуемые — те, которые может сериализовать функция pickle
              0
              А что будет если функция рекурсивная, а мы хотим добавить Memoization, чтобы переделать её в динамический алгоритм? Этот метод подойдет? Если да, то очень элегантно…
                0
                Я так понимаю, что закешируются все промежуточные значения. Поэтому, если уровней рекурсии было много, получим много бесполезного ужаса, поиск по которому может оказаться неэффективнее повторного вычисления.
                  0
                  зависит от функции. например класическое фибоначчи без генератора (fib(n)=fib(n-1)+fib(n-2)) — при частых вызовах с мемоизацией экономит кучу вычислительной мощности. Единственный вопрос — не не будет ли запрос fib(100000000) :] но это легко обойти, как я уже написал.
                0
                а память не утечет?
                  +1
                  вычисленные результаты будут храниться все время существования функции (до del, например). чуть модифицировав можно ограничить как количество так и время хранения. но это уже по желанию :]

                  «утечка» как таковая в питоне в принципе невозможна. как только пропадут все ссылки на объект, за ним придет GC :]
                  0
                  Большое спасибо, позновательно и необычно.
                  Хотелось бы видеть больше статей на тему декораторов.
                    0
                    Сразу вспоминается вот это: code.activestate.com/recipes/498245/
                    Там еще сделан LRU cache, для экономии памяти, но не используется pickle

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое