Comments 48
У вас вычисление функции внутри блока synchronized(). Вычисление функции — длительный процесс, а так как функция является pure, то разные потоки могли бы вызывать её и считать параллельно. А в вашем варианте — добавили мемоизацию, убрали параллелизм.
есть такое дело, но как известно «there is no silver bullet» фактически. Поэтому как и сказано в разделе про производительность в каждом случае нужно рассматривать, что даёт мемоизация и на основе этого принимать решение о её необходимости.
По поводу параллелизма, фактически если мы знаем, что наш код будет выполняться в «сильно параллельном» приложении мы можем обеспечивать только синхронизацию операции put, тогда проверка наличия в хранилище (только чтение) может выполняться всеми потоками параллельно. В итоге единственной проблемой останется первый запуск функции, который могут начать выполнять сразу много потоков. Но т.к. о данном варианте я лишь думал, но не сделал рабочий прототип, то я не стал о нём писать, оставив лишь заметку о введении критической секции и того, что нужно обратить внимание на возможность уменьшение производительности при использовании большого количества потоков.
По поводу параллелизма, фактически если мы знаем, что наш код будет выполняться в «сильно параллельном» приложении мы можем обеспечивать только синхронизацию операции put, тогда проверка наличия в хранилище (только чтение) может выполняться всеми потоками параллельно. В итоге единственной проблемой останется первый запуск функции, который могут начать выполнять сразу много потоков. Но т.к. о данном варианте я лишь думал, но не сделал рабочий прототип, то я не стал о нём писать, оставив лишь заметку о введении критической секции и того, что нужно обратить внимание на возможность уменьшение производительности при использовании большого количества потоков.
Посмотрите в сторону Ehcache. Там есть говторые и тщательно оттестированные решения для самых разных задач кэширования. В частности есть вариант кэша, когда если несколько потоков обращаются к разным значениям — при их отсутствии вычисление будет выполнено паралелльно, а если несколько потоков пробуют обратиться к за одним значением, то вычисление будет выполнено только в одном потоке, а результат получат все.
А не подскажете куда конкретно там посмотреть на многопоточное вычисление? Насколько я помню (правда еще по 1.4) там все методы класса кеша были объявлены как synchronized, собственно поэтому от него и отказался.
Если мне не изменяет память, то что вам нужно — SelfPopulatingCache.
Автор, специально для таких вещей придумали AOP и IoC. Не надо городить кучу кода, в которой потом хрен разберешься.
Использовать HashMap для *общего* случая может быть неверно из-за потенциальных утечек памяти.
Про невозможность распаралеливания уже написали выше.
> Замечу, что в данный класс можно добавить функцию:
> public Object memorize(Callable fubc, final Map obj)
> Однако в данном случае мы заведомо теряем возможность работы в generic
С чего бы это? Что мешает написать public T memorize(Callable func, Map obj)? Или я неправильно вас понял?
Использовать HashMap для *общего* случая может быть неверно из-за потенциальных утечек памяти.
Про невозможность распаралеливания уже написали выше.
> Замечу, что в данный класс можно добавить функцию:
> public Object memorize(Callable fubc, final Map obj)
> Однако в данном случае мы заведомо теряем возможность работы в generic
С чего бы это? Что мешает написать public T memorize(Callable func, Map obj)? Или я неправильно вас понял?
> Автор, специально для таких вещей придумали AOP и IoC. Не надо городить кучу кода, в которой потом хрен разберешься.
если Вы поделитесь ссылкой на реализацию мемоизации в рамках реализаций AOP и IoC для Java, то я буду Вам благодарен. Поиск привёл меня лишь к некоторым «наколенным» вариантам реализации. Впрочем как и данные варианты.
> Использовать HashMap для *общего* случая может быть неверно из-за потенциальных утечек памяти
Идея мемоизации, заключается в том, что мы должны хранить результаты всех вызовов данной функции. Т.е. вариант использования WeakHashMap убережет нас от утечек памяти, но выведет за границы изначальной парадигмы. Возможно использование и более сложных структур данных считающих статистику, или удаляющих часть давно не использованных данных при каждом вызове не выходя за рамки O(1).
> С чего бы это? Что мешает написать public T memorize(Callable func, Map obj)? Или я неправильно вас понял?
я хотел написать public static T memorize... не статический метод, действительно ничего написать не запрещает. Ошибку поправлю
если Вы поделитесь ссылкой на реализацию мемоизации в рамках реализаций AOP и IoC для Java, то я буду Вам благодарен. Поиск привёл меня лишь к некоторым «наколенным» вариантам реализации. Впрочем как и данные варианты.
> Использовать HashMap для *общего* случая может быть неверно из-за потенциальных утечек памяти
Идея мемоизации, заключается в том, что мы должны хранить результаты всех вызовов данной функции. Т.е. вариант использования WeakHashMap убережет нас от утечек памяти, но выведет за границы изначальной парадигмы. Возможно использование и более сложных структур данных считающих статистику, или удаляющих часть давно не использованных данных при каждом вызове не выходя за рамки O(1).
> С чего бы это? Что мешает написать public T memorize(Callable func, Map obj)? Или я неправильно вас понял?
я хотел написать public static T memorize... не статический метод, действительно ничего написать не запрещает. Ошибку поправлю
>если Вы поделитесь ссылкой на реализацию мемоизации в рамках реализаций AOP и IoC для Java, то я буду Вам благодарен.
к примеру вот: www.dev2dev.ru/content/spring-i-ehcache-chast%D1%8C-vtoraia-cacheflush-i-nazvaniie-kiesha-v-annotatsii
к примеру вот: www.dev2dev.ru/content/spring-i-ehcache-chast%D1%8C-vtoraia-cacheflush-i-nazvaniie-kiesha-v-annotatsii
Зачем делиться ссылкой на реализацию? Это все делается буквально за пару минут, если знаешь что такое AOP / IoC. Тут даже и описывать-то нечего.
Идея идеей, но описать возможные проблемы все равно стоит.
Парсер — лох. Я имел ввиду: public <T> T memorize(Callable<T> func, Map<Callable<T>, T> obj)
Идея идеей, но описать возможные проблемы все равно стоит.
Парсер — лох. Я имел ввиду: public <T> T memorize(Callable<T> func, Map<Callable<T>, T> obj)
Мемоизация это… Это просто кеширование результатов функции.
Метод известный десятки лет из динамического программирования (теория алгоритмов)
И применимый к очень узкому классу задач.
И в общем случае не имеющий смысла.
1 А как вы будете кешировать значения, если параметры функции — объекты?
Придется удерживать все объекты в памяти — а это очень, очень много памяти.
2 А чтобы найти сохраненное значение для параметров a,b,c придется очень хороши[ и долго] поискать.
3 А что будет, если объекты сохранные как параметры для данного значения будут изменены (mutable-объекты)?
Метод известный десятки лет из динамического программирования (теория алгоритмов)
И применимый к очень узкому классу задач.
И в общем случае не имеющий смысла.
1 А как вы будете кешировать значения, если параметры функции — объекты?
Придется удерживать все объекты в памяти — а это очень, очень много памяти.
2 А чтобы найти сохраненное значение для параметров a,b,c придется очень хороши[ и долго] поискать.
3 А что будет, если объекты сохранные как параметры для данного значения будут изменены (mutable-объекты)?
на основе параметров нужно вычислять хэш и искать по нему в таблице. правда хэш нужен без коллизий…
> Мемоизация это… Это просто кеширование результатов функции.
с точностью до того, что это частный случай =)
> И применимый к очень узкому классу задач.
> И в общем случае не имеющий смысла.
В общем то об этом было сказано. Но спасибо за резюмирование.
> 1 А как вы будете кешировать значения, если параметры функции — объекты?
1). у объектов передаваемых в функцию должна быть определена адекватная операция кэширования. Так например в 3ем варианте используется стандарный кэш. Используя первые два варианта Вы фактически можете создать свою функцию отвечающую условиям Вашей задачи.
Как уже отметили до меня нужен хэш без коллизий. Но эта проблема может возникнуть в любом месте, где используется Map, Set и т.д.
> 2 А чтобы найти сохраненное значение для параметров a,b,c придется очень хороши[ и долго] поискать.
В конце топика приведён рабочий вариант для кэша функции двух аргуметров. Так же Вы можете построить «каррированную» функцию т.е. Map<T,Map<?>> -> Map<T2,Map<?> -> Map<T3,K>
где T1,T2,T3 — тип параметров, K — результат. В этом случае поиск будет дольше и использует лишнюю память и нужно рассматривать, к чему это приведёт. Скажу честно я этого пока не делал.
Можно использовать более сложные структуры памяти главное, чтобы они реализовали требуемый интерфейс.
> 3 А что будет, если объекты сохранные как параметры для данного значения будут изменены (mutable-объекты)?
если в ходе вызова функции, то будет грустно. Если между вызовами, то программист должен позаботиться, чтобы его объект Callable отработал данную ситуацию при вычислении хэш функции.
надеюсь я ответил на вопросы?
с точностью до того, что это частный случай =)
> И применимый к очень узкому классу задач.
> И в общем случае не имеющий смысла.
В общем то об этом было сказано. Но спасибо за резюмирование.
> 1 А как вы будете кешировать значения, если параметры функции — объекты?
1). у объектов передаваемых в функцию должна быть определена адекватная операция кэширования. Так например в 3ем варианте используется стандарный кэш. Используя первые два варианта Вы фактически можете создать свою функцию отвечающую условиям Вашей задачи.
Как уже отметили до меня нужен хэш без коллизий. Но эта проблема может возникнуть в любом месте, где используется Map, Set и т.д.
> 2 А чтобы найти сохраненное значение для параметров a,b,c придется очень хороши[ и долго] поискать.
В конце топика приведён рабочий вариант для кэша функции двух аргуметров. Так же Вы можете построить «каррированную» функцию т.е. Map<T,Map<?>> -> Map<T2,Map<?> -> Map<T3,K>
где T1,T2,T3 — тип параметров, K — результат. В этом случае поиск будет дольше и использует лишнюю память и нужно рассматривать, к чему это приведёт. Скажу честно я этого пока не делал.
Можно использовать более сложные структуры памяти главное, чтобы они реализовали требуемый интерфейс.
> 3 А что будет, если объекты сохранные как параметры для данного значения будут изменены (mutable-объекты)?
если в ходе вызова функции, то будет грустно. Если между вызовами, то программист должен позаботиться, чтобы его объект Callable отработал данную ситуацию при вычислении хэш функции.
надеюсь я ответил на вопросы?
Замечу, что к моему удивлению, добавление лишней сущности во втором примере привело лишь к улучшению производительности. Хотя скорее всего это произошло лишь из-за простоты примера и того. функцию из первого примера я вызывал как статическую функцию (функцию класса) тестового класса, а во втором случае это была функция объекта.
В любом случае точно можно сделать вывод, что простое обобщение первого случая до второго не привело к потере производительности.
Может быть, если у найду время, то я попробую поточнее рассмотреть данный вопрос.
В любом случае точно можно сделать вывод, что простое обобщение первого случая до второго не привело к потере производительности.
Может быть, если у найду время, то я попробую поточнее рассмотреть данный вопрос.
Про float.
Как правило для большинства задач можно задать более-менее объективную границу отсечения (например, 3 знака после запятой), и все float-значения перед обработкой округлять до заданной границы. Это снимет проблему повторных вычислений и (!), что более важно, потенциальные ошибки сравнения (float_1 == float_2).
Как правило для большинства задач можно задать более-менее объективную границу отсечения (например, 3 знака после запятой), и все float-значения перед обработкой округлять до заданной границы. Это снимет проблему повторных вычислений и (!), что более важно, потенциальные ошибки сравнения (float_1 == float_2).
может быть ehcache и не мучаться?
Спасибо за введение, я думаю что начинающим это пригодится. Тем более приведены очень простые примеры, благодаря которым можно понять механизм работы кэширования вызовов.
Кстати, я нечто подобное уже заимплементил в своем проекте (на базе: аннотаций + интерцепторов). И пришел к выводу, что это чрезвычайно полезная штука для сложных вычислений. К примеру, у меня есть код который считает финансовый план, при этом данные берутся из 10-20 разных источников, причем есть граф вызовов методов. Без кэширования расчет занимал порядка часа, а при кэшировании расчет проходил за 2-3 минуты.
Конечно можно было оптимизировать все на уровне запросов к БД, но это бы сильно усложнило код, да и запросы понять было бы намного сложнее. А так получилось все намного проще и лучше. К тому же модульность не пострадала.
Немного слов о кэшировании. К сожалению кэшировать данные иногда не лучший выбор, но иногда можно выделить неизменный контекст. Например описанный мной ранее пример кэширует данные на уровне транзакции пользователя. И для запросов на чтение и расчет это довольно неплохо работает.
Также стоит отметить что готовых решений из коробки нет, практически все предлагают допиливание решений под себя, что немного грустно (потому что не всегда адекватно и понятно работает). Возможно мир еще не готов к данному подходу. Хотя говорят у сапа есть что-то подобное, но тут нужен ихний специалист :)
Кстати, я нечто подобное уже заимплементил в своем проекте (на базе: аннотаций + интерцепторов). И пришел к выводу, что это чрезвычайно полезная штука для сложных вычислений. К примеру, у меня есть код который считает финансовый план, при этом данные берутся из 10-20 разных источников, причем есть граф вызовов методов. Без кэширования расчет занимал порядка часа, а при кэшировании расчет проходил за 2-3 минуты.
Конечно можно было оптимизировать все на уровне запросов к БД, но это бы сильно усложнило код, да и запросы понять было бы намного сложнее. А так получилось все намного проще и лучше. К тому же модульность не пострадала.
Немного слов о кэшировании. К сожалению кэшировать данные иногда не лучший выбор, но иногда можно выделить неизменный контекст. Например описанный мной ранее пример кэширует данные на уровне транзакции пользователя. И для запросов на чтение и расчет это довольно неплохо работает.
Также стоит отметить что готовых решений из коробки нет, практически все предлагают допиливание решений под себя, что немного грустно (потому что не всегда адекватно и понятно работает). Возможно мир еще не готов к данному подходу. Хотя говорят у сапа есть что-то подобное, но тут нужен ихний специалист :)
Извиняюсь, что не по теме топика, просто больше особо негде про Java спросить.
Integer c = 1000, d = 1000;
System.out.println(c == d); // false
Integer e = 100, f = 100;
System.out.println(e == f); // true
Почему в первом случае false, во втором true? False понятно, а вот true откуда берется?
Integer c = 1000, d = 1000;
System.out.println(c == d); // false
Integer e = 100, f = 100;
System.out.println(e == f); // true
Почему в первом случае false, во втором true? False понятно, а вот true откуда берется?
Раз почему false понятно, то объясню только второе. Для ускорения работы (чтобы не генерировать новые объекты) в Java автоматически создаются Integer, Byte,Long от -128 до 127, и Character от 0 до 127. Поскольку это неизменяемые объекты, то мы можем вместо инициализации нового объекта выдать ссылку на уже существущий, в итоге ускорение.
По скользкой дороге идёте… Сравнивать ссылки вместо объектов…
Можно узнать зачем это Вам?
Можно узнать зачем это Вам?
Какраз вчера твиттере прошла волна про проезенташку C# vs Java. И там в примерах почему Java это плохо приводился этот пример.
Ага, именно оттуда, поэтому вопрос чисто теоретический, но он меня очень заинтересовал.
Я знаком не только с C#, но такой подход к базовым типам языка встречаю впервые — поэтому интересно, какие предпосылки стояли перед разработчиками Java когда они принимали такое решение.
То что они что-то оптимизировали кажется понятно, но вот что именно и на сколько успешно — открытый вопрос.
Я знаком не только с C#, но такой подход к базовым типам языка встречаю впервые — поэтому интересно, какие предпосылки стояли перед разработчиками Java когда они принимали такое решение.
То что они что-то оптимизировали кажется понятно, но вот что именно и на сколько успешно — открытый вопрос.
Кстати говоря, выводы той презентации — JVM рулит, юзайте Scala :)
А как в вашем коде дела с оптимизацией хвостовой рекурсии? У JVM как известно есть с этим определённые проблемы. Не хочется ловить StackOverflow при больших значениях аргументов.
Oh, Really! :)
В разделе «общий вид» в примере в строке
if ( result==null && cache.containsKey(k) ) {
забыли отрицание перед проверкой наличия ключа поставить
if ( result==null && cache.containsKey(k) ) {
забыли отрицание перед проверкой наличия ключа поставить
Поправка — при использовании статического метода можно использовать Generic'и:
public R memorize(Callable fubc, final Map<Callable,R> obj) {… }
Стандартная нотация :-)
public R memorize(Callable fubc, final Map<Callable,R> obj) {… }
Стандартная нотация :-)
Также можно добавить, что средствами AspectJ можно, немного подумав, реализовать автоматическое кеширование для методов с определенной сигнатурой.
Предлагаю освятить это в следующей статье.
Предлагаю освятить это в следующей статье.
Sign up to leave a comment.
Мемоизация в Java