Как-то мне посчастливилось натолкнуться на хабрапост, посвященный мемоизации. На тот момент это слово было мне ещё не знакомым и я даже слегка растерялся.
Однако уже после первых строк я сразу понял, что скрывается под этим мудрёным словом - это же старое, доброе, классическое ("тёплое ламповое" ;-) ) табулирование функций, но подведённое под паттерн проектирования и с более удобным (в контексте языка Python) интерфейсом.
Почитав ещё несколько постов на эту же тему я увидел в представленных реализациях "фатальный недостаток" тут же кинулся переписывать самостоятельно, на примере расчёта факториала:
Однако отличия от увиденного ранее - минимальны. Такова уж специфика задачи и особенности Python (да, досадно вышло - хочется изобрести свой велосипед, а даже код получается почти такой же, как у всех!). Отличие от прочих вариантов - словарь описан снаружи и пригоден к сериализации с дальнейшим сохранением в файл посредством pickle.
Описанный выше подход - красив и лаконичен, но слишком обобщён и идеален, годится лишь как демонстрация красоты Python и наглядности подхода.
Теперь добавим несколько смачных ложек дёгтя.
1) В приведенном примере для хранения значений функций используется простой словарь, который хранится в памяти. Его размер определяется ограничениями используемой операционной системы. То есть запуская скрипт с мемоизацией на разных конфигурациях железа и ОС мы не можем расчитывать, что нам всегда будет хватать памяти на одних и тех же объёмах вычислений.
2) Может так получиться, что расчёты будут производиться внутри параллельно выполняющихся процессов - в этом случае, приведенный метод потребует доработки: словарь mem придётся сделать разделяемой переменной, что может несколько усложнить приложение.
3) Области определения функций и действительно ли надо хранить так много значений?
Например, простые числа или числа Фибоначчи. Куда удобнее хранить их не в словаре, а в упорядоченном списке - и использовать двоичный поиск для проверки наличия значений. Из этого следует очевидный вывод, что способ хранения и доступа определяется особенностями функции.
Всё-таки, если бы вдруг встала острая необходимость мемоизации - действительно важная функция (или их некоторое множество) считалась долго, нужна была часто и вероятность повторного вызова с таким же набором входных параметров была бы заметно отлична от нуля - пожалуй я выбрал бы для этого какую-нибудь базу данных, MySQL или PostgreSQL - не суть важно. Храни сколько хочешь, доставай хоть из треда, хоть из процесса. А обращение также обернул бы в декоратор.
Однако уже после первых строк я сразу понял, что скрывается под этим мудрёным словом - это же старое, доброе, классическое ("тёплое ламповое" ;-) ) табулирование функций, но подведённое под паттерн проектирования и с более удобным (в контексте языка 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 - не суть важно. Храни сколько хочешь, доставай хоть из треда, хоть из процесса. А обращение также обернул бы в декоратор.
