Мемоизация — (Memoization, англ) вариант кеширования, заключающийся в том, что для функции создаётся таблица результатов, и будучи вычисленной при определённых значениях параметров результат заносится в эту таблицу. В дальнейшем результат берётся из данной таблицы.
Эта техника позволяет засчёт использования дополнительной памяти ускорить работу программы.Данный подход очень частно применяется в функциональных языках программирования, однако и в императивных ему так же можно найти применение. В данном топике рассматривается использование мемоизации в языке java приводятся различные примеры мемоизации и в конце производится небольшое сравнение производительности данных методов.
Естественным образом, мемоизация может быть использована далеко не для всех функций. Фактически её можно применить только к чистым функциям. Т.е. функциям, которые являются: а). детерминированными (т.е. при одном и том же наборе параметров функции должны возвращать одинаковое значение), б). без побочных эффектов (т.е. не должны влиять на состояние системы). Фактически такие функции должны являться «черным ящиком», единственное взаимодействие с которыми может производиться через аргументы и возвращаемое значение. Так же при построении определенных реализаций мемоизации у нас могут возникать дополнительные ограничения, специфичные для данной реализации (или языка).
Ещё одним дополнительным ограничением может служить то, что мемоизация будет эффективна только для функций с дискретной областью определения. Несмотря на то, что в компьютерном представлении все данные являются дискретными, для чисел с плавающей точкой у нас могут возникать проблемы из-за погрешностей при вычислении. Так, например, (float f1 = 0.1f;float f2 = 0.7f;System.out.print(f1+f2==0.8);) выдаст значение false, потому, что сумма 0.1 и 0.7 отличается в двоичном представлении от 0.8 и как следствие даже в мемоизированной функции при вычислении foo (f1+f2), foo(0.8) функция будет вычисляться оба раза.
Теперь обратимся непосредственно к реализации данной технологии. Попробуем записать общий вид мемоизации для одной функции:
Как видно нам требуется объект хранилище реализующий следующий интерфейс:
В Java наиболее подходящей кандидатурой на роль хранилища является интерфейс Map, для для некоторых случаев (будет описано ниже) возможно использовать более быстрые структуры данных. Амортизированная сложность операций get,put,contains равна O(1). Что позволяет гарантировать ограничение задержки при выполении мемоизации. Поскольку мы должны гарантировать потокобезопасность в случае одновременного обращения различных потоков к хранилищу во время выполнения всей серии операций, мы должны объявить критическую секцию на этом участке кода, как следствие использование изначально потокобезопасных структур (например hashtable) является бессмысленным.
UPD. Как правильно заметили в комментариях хабраюзеры gribozavr, remal и gvsmirnov в данном коде возникают проблемы с многопоточностью. Более того gvsmirnov предложил решение, которое можно найти в книге Java Concurrency in Practice. От себя добавлю, что в некоторых случаях можно синхронизировать только операцию put в этом случае при первом обращении к функции одну и ту же функцию могут вызвать несколько потоков. Хотелось бы заметить, что иногда при очень сложной операции (обращение по сети или к БД) даже не многопоточная версия функции может иметь смысл. Т.к. многопоточный вариант был предложен после написания поста, то далее используется обычный
Пример реализации (числа Фибоначчи):
В итоге мы получили решение отвечающая следующим
Теперь, решив частную задачу, попробуем обобщить её на класс вызываемых функций без аргументов. Для этого мы будем рассматривать интерфейс Callable с операцией call. Таким образом все аргументы функции должны быть переданны через поля класса реализующего интерфейс. Это существенно усложняет работу программисту, но позволяет достаточно просто сделать работу с такими методами. Так же мы будем считать наш класс неизменяемым и с функцией определения хэша зависящей только от параметров, это необходимо, чтобы гарантировать правильность проверки хэша в кэш таблице. Т.к. если наш класс изменяемый, то при изменении параметров хэш функция может не измениться и в итоге мы получим неправильное значение, и наоборот объекты классы с одинаковыми параметрами могут быть считаться различными объектами.
Если выполнены все предположения, то мы можем построить следующий класс предок для мемоизированных функций.
Замечу, что в данный класс можно добавить функцию:
аналогичную invoke, но работающую для любых функций, не обязательно наследников MemoizedFunction. Однако в данном случае мы заведомо теряем возможность работы в generic, да и необходимость использования такой функции это дискуссионный вопрос, который, однако, не хотелось бы затрагивать в данной теме.
Итого, в данном примере мы абстрагировались от выбора определенного кэша и функции оставив это программисту. Таким образом при использовании данного класса мы можем легко изменять кэш и использовать различные вычислительные функции. Однако не все прекрасно рассмотрим пример (те же числа Фибоначчи):
Для этого нам нужно создать наследника, передав в MemoizedFunction ссылку на используемый кэш
Важно заметить, что для того, чтобы мемоизация рекурсивных вызовов работала нам необходим доступ к внешнему классу. Это ограничивает возможность использования данного типа мемоизации для рекурсивных функций, что и показано в примере выше.
В итоге мы получаем интерфейс со следующими характеристиками:
N.B. В скором временем с приходом замыканий в java данный фреймворк можно будет сильно упростить (примеры можно посмотреть блоге Mark Mahieu).
Ценой потерь производительности мы можем улучшить прозрачную мемоизацию, использовав Proxy класс.
(реализация метода взята из книги O'Really , кстати там есть и более продвинутая версия мемоизатора. Познакомиться с принципами работы прокси классов можно по ссылке Java Reflection in Action: Using Java's Dynamic Proxy или на сайте java.sun.com. Вкратце создаётся объект перехватывающий все вызовы к «спрятанному» объекту и вызывающие их обработчик.
В этом случае для использования мемоизации нам нужно будет создать дополнительный интерфейс описывающий нашу структуру (и функции мемоизации)
однако создание структуры существенно упрощается, достаточно вместо
характеристики:
К сожалению единственный действующий способ понять улучшается ли скорость работы от мемоизации это отпрофилировать его. Поэтому варианты с простым добавлением/убиранием мемоизации могут помочь при профилировке. Можно предложить следующую стратегию
Теперь хочется поговорить о производительности приеведенных решений. Во первых измерялась скорость вычисления чисел Фиббоначи, простой вариант и вариант с рефлексией, не поддерживают кэширование, поэтому имеют экспоненциальную сложность, в отличии от полиномиальной сложности 1 и 2 вариантов.
Формально для на скорость работы влияют следующие параметры: размер области определения и распределение параметров по нему, время выполнения функции, количество потоков совершающих одновременный доступ к хранилищу. В приципе можно провести многопараметрический анализ зависимостей, но в любом случае это не входит в рамки данного топика.
Нераскрытым остался вопрос об использовании функции от нескольких аргументов, тут могут быть разные решения: а). создание специальной хэш функции, б). использование каррирования и соответственно нескольких хэш таблиц, в). использование хэша так как он был использован в варианте с ферлексией, г). другие варианты.
Вот пример варианта создания своей хэш функции:
Далее при работе с таким хэшом мы должны создать объект ключ Pair<Integer,Integer> p = new Pair(i,j); и использовать его для работы с хранилищем.
Так же существуют некоторые способы оптимизации:
В общем это на этом можно закончить краткое введение в технологию мемоизации, любые комментарии замечания, уточнения приветствуются.
UPD. добавил пару слов о многопоточности.
UPD2 добавил ссылку на Java Concurrency in Practive
UPD3 во многих комментариях отметили open source библиотеку ehcache, в которой реализована мемоизация и многое другое, так что интересующимся наверное стоит обратить на неё внимание.
Эта техника позволяет засчёт использования дополнительной памяти ускорить работу программы.Данный подход очень частно применяется в функциональных языках программирования, однако и в императивных ему так же можно найти применение. В данном топике рассматривается использование мемоизации в языке java приводятся различные примеры мемоизации и в конце производится небольшое сравнение производительности данных методов.
Введение
Естественным образом, мемоизация может быть использована далеко не для всех функций. Фактически её можно применить только к чистым функциям. Т.е. функциям, которые являются: а). детерминированными (т.е. при одном и том же наборе параметров функции должны возвращать одинаковое значение), б). без побочных эффектов (т.е. не должны влиять на состояние системы). Фактически такие функции должны являться «черным ящиком», единственное взаимодействие с которыми может производиться через аргументы и возвращаемое значение. Так же при построении определенных реализаций мемоизации у нас могут возникать дополнительные ограничения, специфичные для данной реализации (или языка).
Ещё одним дополнительным ограничением может служить то, что мемоизация будет эффективна только для функций с дискретной областью определения. Несмотря на то, что в компьютерном представлении все данные являются дискретными, для чисел с плавающей точкой у нас могут возникать проблемы из-за погрешностей при вычислении. Так, например, (float f1 = 0.1f;float f2 = 0.7f;System.out.print(f1+f2==0.8);) выдаст значение false, потому, что сумма 0.1 и 0.7 отличается в двоичном представлении от 0.8 и как следствие даже в мемоизированной функции при вычислении foo (f1+f2), foo(0.8) функция будет вычисляться оба раза.
Общий вид
Теперь обратимся непосредственно к реализации данной технологии. Попробуем записать общий вид мемоизации для одной функции:
private static final Map<K, R> cache = new HashMap<K, R>();
R bar(K k){
R result = null;
synchronized( cache ) {
result = cache.get(k);
if ( result==null && ! cache.containsKey(k) ) {
Result result = //real function evaluation
cache.put(k,result);
}
}
return result;
}
Как видно нам требуется объект хранилище реализующий следующий интерфейс:
- get::Key ->(Value|Null) — возвращающая по ключу объект из хранилища или специальное значение Null, если такого ключа нет,
- put::(Key,Value)->Void — операция сохраниения пары (ключ-объект) в хранилище.
- contains::Key->Boolean — операция проверки наличия ключа в хранилице. Она требуется если значение Null возвращаемое операцией get является возможным значением объекта в хранилище.
В Java наиболее подходящей кандидатурой на роль хранилища является интерфейс Map, для для некоторых случаев (будет описано ниже) возможно использовать более быстрые структуры данных. Амортизированная сложность операций get,put,contains равна O(1). Что позволяет гарантировать ограничение задержки при выполении мемоизации. Поскольку мы должны гарантировать потокобезопасность в случае одновременного обращения различных потоков к хранилищу во время выполнения всей серии операций, мы должны объявить критическую секцию на этом участке кода, как следствие использование изначально потокобезопасных структур (например hashtable) является бессмысленным.
UPD. Как правильно заметили в комментариях хабраюзеры gribozavr, remal и gvsmirnov в данном коде возникают проблемы с многопоточностью. Более того gvsmirnov предложил решение, которое можно найти в книге Java Concurrency in Practice. От себя добавлю, что в некоторых случаях можно синхронизировать только операцию put в этом случае при первом обращении к функции одну и ту же функцию могут вызвать несколько потоков. Хотелось бы заметить, что иногда при очень сложной операции (обращение по сети или к БД) даже не многопоточная версия функции может иметь смысл. Т.к. многопоточный вариант был предложен после написания поста, то далее используется обычный
Пример реализации (числа Фибоначчи):
public static BigInteger fib(Integer k){
if (fibTable.containsKey(k)) {
return fibTable.get(k);
} else {
BigInteger r;
if (k<0) return BigInteger.ZERO;
else if(k == 1) return BigInteger.ONE;
else r = fib(k-1).add(fib(k-2));
fibTable.put(k, r);
return r;
}
}
В итоге мы получили решение отвечающая следующим
- [+] небольшой overhead при работе
- [+] нет необходимости создания дополнительных сущностей
- [+] функция может вызываться рекурсивно
- [±] использование кеширования лежит на программисте. В случае функции от более чем одного аргумента пользователю необходимо самому решать, как создать отображение параметров функции результату.
- [-] изменения не стандартизированны. Т.е. для каждой новой мемоизированной функции нам нужно будет повторять весь исходный код, а так же искать ошибки по всему коду
Обобщение решения
Теперь, решив частную задачу, попробуем обобщить её на класс вызываемых функций без аргументов. Для этого мы будем рассматривать интерфейс Callable с операцией call. Таким образом все аргументы функции должны быть переданны через поля класса реализующего интерфейс. Это существенно усложняет работу программисту, но позволяет достаточно просто сделать работу с такими методами. Так же мы будем считать наш класс неизменяемым и с функцией определения хэша зависящей только от параметров, это необходимо, чтобы гарантировать правильность проверки хэша в кэш таблице. Т.к. если наш класс изменяемый, то при изменении параметров хэш функция может не измениться и в итоге мы получим неправильное значение, и наоборот объекты классы с одинаковыми параметрами могут быть считаться различными объектами.
Если выполнены все предположения, то мы можем построить следующий класс предок для мемоизированных функций.
public class MemoizedFunction<R>{
private final Map<Callable<R>,R> cache;
public MemoizedFunction(Map<Callable<R>,R> cache){
this.cache = cache;
}
public R invoke(Callable<R> function) throws Exception {
R result;
synchronized (cache) {
result = cache.get(function);
if ( result==null && ! cache.containsKey(function)) {
result = function.call();
cache.put(function, result);
}
}
return result;
}
Замечу, что в данный класс можно добавить функцию:
public Object memorize(Callable fubc, final Map<Callabl,Object> obj) { аналогичную invoke, но работающую для любых функций, не обязательно наследников MemoizedFunction. Однако в данном случае мы заведомо теряем возможность работы в generic, да и необходимость использования такой функции это дискуссионный вопрос, который, однако, не хотелось бы затрагивать в данной теме.
Итого, в данном примере мы абстрагировались от выбора определенного кэша и функции оставив это программисту. Таким образом при использовании данного класса мы можем легко изменять кэш и использовать различные вычислительные функции. Однако не все прекрасно рассмотрим пример (те же числа Фибоначчи):
Для этого нам нужно создать наследника, передав в MemoizedFunction ссылку на используемый кэш
public class Fibber extends MemoizedFunction<BigInteger> {
static HashMap<Callable<BigInteger>,BigInteger> cache =
new HashMap<Callable<BigInteger>,BigInteger>();
public Fibber(){
super(cache);
}
public BigInteger fib(int k){
BigInteger result = null;
try {
result = this.invoke(new Calculation(k));
} catch (Exception ex) {/* убрано для сокращения кода */ }
return result;
}
class Calculation implements Callable<BigInteger> {
private int k;
Calculation(int k){ this.k = k; }
public boolean equals(Object obj) { /*для уменьшения количества года убрано */ }
public int hashCode(){ return k; }
public BigInteger call() throws Exception {
if (k<1) { return BigInteger.ZERO;
} else if (k==1) {return BigInteger.ONE;
} else { return (Fibber.this.fib(k-1)).add(Fibber.this.fib(k-2)); } //<-- Внимание (!)
}
}
}
Важно заметить, что для того, чтобы мемоизация рекурсивных вызовов работала нам необходим доступ к внешнему классу. Это ограничивает возможность использования данного типа мемоизации для рекурсивных функций, что и показано в примере выше.
В итоге мы получаем интерфейс со следующими характеристиками:
- [+]возможность единообразно создавать мемоизированные функции
- [±]невозможно использование рекурентных функций напрямую
- [-]необходимо создание дополнительных сущностей
- [-]использование мемоизированных функций не прозрачно. Мы не можем простым образом переделать обычную функцию в мемоизированную и наоборот.
N.B. В скором временем с приходом замыканий в java данный фреймворк можно будет сильно упростить (примеры можно посмотреть блоге Mark Mahieu).
Моемоизация с применением рефлексии
Ценой потерь производительности мы можем улучшить прозрачную мемоизацию, использовав Proxy класс.
(реализация метода взята из книги O'Really , кстати там есть и более продвинутая версия мемоизатора. Познакомиться с принципами работы прокси классов можно по ссылке Java Reflection in Action: Using Java's Dynamic Proxy или на сайте java.sun.com. Вкратце создаётся объект перехватывающий все вызовы к «спрятанному» объекту и вызывающие их обработчик.
public class Memoizer implements InvocationHandler {
public static Object memoize(Object object) {
return Proxy.newProxyInstance(
object.getClass().getClassLoader(),
object.getClass().getInterfaces(),
new Memoizer(object));
}
private Object object;
private Map caches = new HashMap();
private Memoizer(Object object) {
this.object = object;
}
public Object invoke(Object proxy, Method method,
Object[] args) throws Throwable {
if (method.getReturnType().equals(Void.TYPE)) {
// Don't cache void methods
return method.invoke(object, args);
} else {
Map cache = getCache(method);
List key = Arrays.asList(args);
Object value = cache.get(key);
if (value == null && !cache.containsKey(key)) {
value = method.invoke(object, args);
cache.put(key, value);
}
return value;
}
}
private synchronized Map getCache(Method m) {
Map cache = (Map) caches.get(m);
if (cache == null) {
cache = Collections.synchronizedMap( new HashMap() );
caches.put(m, cache);
}
return cache;
}
}
В этом случае для использования мемоизации нам нужно будет создать дополнительный интерфейс описывающий нашу структуру (и функции мемоизации)
public interface IFibber {
public BigInteger fib(int k);
}
public class Fibber implements IFibber {
public BigInteger fib(int k) {
if (k<0) { return BigInteger.ZERO; }
if (k == 1) { return BigInteger.ONE; }
return this.fib(k-1).add(this.fib(k-2));
}
}
однако создание структуры существенно упрощается, достаточно вместо
IFibber f = new Fibber();написать
IFibber f = (IFibber) Memoizator.memoize(new Fibber());
характеристики:
- [+]возможность прозрачного добавления в программу
- [+]возможность единообразно добавлять мемоизированные функции
- [-]нельзя использовать рекурсию
- [-]происходят существенные потери производительности из-за использования рефлексии
Производительность
К сожалению единственный действующий способ понять улучшается ли скорость работы от мемоизации это отпрофилировать его. Поэтому варианты с простым добавлением/убиранием мемоизации могут помочь при профилировке. Можно предложить следующую стратегию
- Выберете класс/функцию для мемоизации
- Отпрофилируйте класс/функцию (и всю систему в целом)
- Если производительность применимая то идите к пункту 6, иначе добавьте мемоизацию
- Отпрофилируйте момоизированную функуцию/класс (и всю систему в целом)
- Если производительность не изменилась или мало изменилась, то уберите мемоизацию
- повторите если необходимо
Теперь хочется поговорить о производительности приеведенных решений. Во первых измерялась скорость вычисления чисел Фиббоначи, простой вариант и вариант с рефлексией, не поддерживают кэширование, поэтому имеют экспоненциальную сложность, в отличии от полиномиальной сложности 1 и 2 вариантов.
| 20 | 1000 | 2000 | |
| вариант 1 | 3.8±0.5мс | 14±4мс | 27.3±2.0мс |
| вариант 2 | 3.4±0.2мс | 13±3мс | 15.0±1.5мс |
Формально для на скорость работы влияют следующие параметры: размер области определения и распределение параметров по нему, время выполнения функции, количество потоков совершающих одновременный доступ к хранилищу. В приципе можно провести многопараметрический анализ зависимостей, но в любом случае это не входит в рамки данного топика.
Бонусы
Нераскрытым остался вопрос об использовании функции от нескольких аргументов, тут могут быть разные решения: а). создание специальной хэш функции, б). использование каррирования и соответственно нескольких хэш таблиц, в). использование хэша так как он был использован в варианте с ферлексией, г). другие варианты.
Вот пример варианта создания своей хэш функции:
private static HashMap<Pair<Integer,Integer>, Integer> cache =
new HashMap<Pair<Integer,Integer>, Integer>();
static class Pair<T1,T2> {
final int hash;
Pair(T1 p1, T2 p2) {
int h = 7;
h = 23 * h + Objects.hashCode(p1);
h = 23 * h + Objects.hashCode(p2);
hash = h;
}
public int hashCode() {
return hash;
}
public boolean equals(Object obj) { /*опущено т.к. может быть сгенерировано IDE */ }
}
Далее при работе с таким хэшом мы должны создать объект ключ Pair<Integer,Integer> p = new Pair(i,j); и использовать его для работы с хранилищем.
Так же существуют некоторые способы оптимизации:
- Иногда в случае если мы работаем с функцией параметры область определения, которой гомеоморфна отрезку на множестве целых чисел, (Существует однозначное преобразование Key->[0..N]), то мы можем использовать в качестве хранилища более быстрые структуры, такие как ArrayList
- В случае если область значения очень широкая и мы можем позволить себе иногда пересчитывать значение мы можем использовать WeakHashMap, тем самым освобождая не используемые часто значения
В общем это на этом можно закончить краткое введение в технологию мемоизации, любые комментарии замечания, уточнения приветствуются.
UPD. добавил пару слов о многопоточности.
UPD2 добавил ссылку на Java Concurrency in Practive
UPD3 во многих комментариях отметили open source библиотеку ehcache, в которой реализована мемоизация и многое другое, так что интересующимся наверное стоит обратить на неё внимание.
