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

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