воскресенье, 18 марта 2012 г.

Мемоизация в Python: пробуем на зуб.

Как-то мне посчастливилось натолкнуться на хабрапост, посвященный мемоизации. На тот момент это слово было мне ещё не знакомым и я даже слегка растерялся.
Однако уже после первых строк я сразу понял, что скрывается под этим мудрёным словом - это же старое, доброе, классическое ("тёплое ламповое" ;-) ) табулирование функций, но подведённое под паттерн проектирования и с более удобным (в контексте языка Python) интерфейсом.

Почитав ещё несколько постов на эту же тему я увидел в представленных реализациях "фатальный недостаток" тут же кинулся переписывать самостоятельно, на примере расчёта факториала:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from functools import wraps
import cPickle
import math
import time

mem = {}

def save():
    f = open('memoization.dat', 'wb')
    cPickle.dump(mem, f)
    f.close()

def load():
    global mem
    try:
        f = open("memoization.dat", 'rb')
        mem = cPickle.load(f)
        f.close()
    except:
        pass

def make_key(name, *args, **kw):
    # создание строкового ключа на основе имени функции и её входных параметров
    key = name + '|'
    key += "|".join([str(p) for p in args]) + "|"
    key += "|".join(["%s:%s" % (str(k),str(kw[k])) for k in sorted(kw.keys())])
    return key

def memoization(func):
    # специальный декоратор для кеширования
    @wraps(func)
    def wrap(*args, **kwargs):
        # формируем ключ
        key = make_key(func.__name__, *args,**kwargs)
        # поиск в кеше
        if key not in mem:
            mem[key] = func(*args,**kwargs)
        return mem[key]

    return wrap

def tracetime(func):
    # специальный декоратор для оценки времени работы функций
    @wraps(func)
    def wrap(*args, **kwargs):
        t1 = time.time()
        res = func(*args, **kwargs)
        t2 = time.time()
        print func.__name__, '/ dt=', t2-t1
        return res

    return wrap

@memoization
def fact(x):
    # мемоизированный факториал
    return math.factorial(x)

# простой тест: сумма длин строковых представлений факториалов
# из заданного диапазона

@tracetime
def test1(a,b):    
    L = 0
    for x in range(a,b):
        L += len(str(fact(x)))

    return L

@tracetime
def test2(a,b):
    L = 0
    for x in range(a,b):
        L += len(str(math.factorial(x)))

    return L

a = 2000
b = 3000

# первый вызов - данных в словаре нет
print test1(a,b)
# обычный расчёт
print test2(a,b)
# при повторном вызове - мемоизация будет уже задействована
print test1(a,b)

Однако отличия от увиденного ранее - минимальны. Такова уж специфика задачи и особенности Python (да, досадно вышло - хочется изобрести свой велосипед, а даже код получается почти такой же, как у всех!). Отличие от прочих вариантов - словарь описан снаружи и пригоден к сериализации с дальнейшим сохранением в файл посредством pickle.
Описанный выше подход - красив и лаконичен, но слишком обобщён и идеален, годится лишь как демонстрация красоты Python и наглядности подхода.
Теперь добавим несколько смачных ложек дёгтя.

1) В приведенном примере для хранения значений функций используется простой словарь, который хранится в памяти. Его размер определяется ограничениями используемой операционной системы. То есть запуская скрипт с мемоизацией на разных конфигурациях железа и ОС мы не можем расчитывать, что нам всегда будет хватать памяти на одних и тех же объёмах вычислений.

2) Может так получиться, что расчёты будут производиться внутри параллельно выполняющихся процессов - в этом случае, приведенный метод потребует доработки: словарь mem придётся сделать разделяемой переменной, что может несколько усложнить приложение.

3) Области определения функций и действительно ли надо хранить так много значений?
Например, простые числа или числа Фибоначчи. Куда удобнее хранить их не в словаре, а в упорядоченном списке - и использовать двоичный поиск для проверки наличия значений. Из этого следует очевидный вывод, что способ хранения и доступа определяется особенностями функции.

Всё-таки, если бы вдруг встала острая необходимость мемоизации - действительно важная функция (или их некоторое множество) считалась долго, нужна была часто и вероятность повторного вызова с таким же набором входных параметров была бы заметно отлична от нуля - пожалуй я выбрал бы для этого какую-нибудь базу данных, MySQL или PostgreSQL - не суть важно. Храни сколько хочешь, доставай хоть из треда, хоть из процесса. А обращение также обернул бы в декоратор.