Memoize и Cache в Джулии

Используйте динамическое программирование, чтобы сделать ваши функции быстрее

Мемоизация — это простой прием в программировании, при котором вы уменьшаете количество необходимых вычислений, запоминая некоторые прерывистые результаты. Здесь я покажу вам, как сделать это в Julia самым простым способом.

🙏 Огромное спасибо тем, кто сделал Memoize.jl Посмотрите репозиторий здесь.

Быть наивным

Мы начнем с простой функции Фибоначчи и посмотрим, насколько медленно она может работать для больших чисел. Ряд Фибоначчи определяется следующим простым правилом:

F(1) = 1, F(2) = 1, F(n) = n — 2 + n — 1

Где n — целое положительное число.

Давайте закодируем это в Джулии:

Это рекурсивная функция, которая вызывает сама себя, что само по себе не является грехом, но для этой конкретной функции это обходится очень дорого. Если вы хотите узнать, почему это так дорого и как работает мемоизация, посмотрите это замечательное видео от freeCodeCamp:

😉 Что мне нравится в Джулии, так это краткость определения простых функций. Вышеупомянутое то же самое, что и этот маленький однострочник:

Давайте проверим, работает ли вышеизложенное, используя удобный макрос @show:

julia> for i in 1:10
           @show i, fibonacci(i)
       end
(i, fibonacci(i)) = (1, 1)
(i, fibonacci(i)) = (2, 1)
(i, fibonacci(i)) = (3, 2)
(i, fibonacci(i)) = (4, 3)
(i, fibonacci(i)) = (5, 5)
(i, fibonacci(i)) = (6, 8)
(i, fibonacci(i)) = (7, 13)
(i, fibonacci(i)) = (8, 21)
(i, fibonacci(i)) = (9, 34)
(i, fibonacci(i)) = (10, 55)

Мы также можем проверить, насколько быстро это работает, используя пакет BenchmarkTools:

julia> @btime fibonacci(30)
  2.280 ms (0 allocations: 0 bytes)
832040

Хотите почитать что-нибудь еще от Джулии? Не стесняйся, просто следуй за мной 😅

Оставаться наивным

Код, который у нас есть, теперь работает, но он мучительно медленный, особенно для больших чисел. Так что в духе наивности давайте попробуем реализовать нашу собственную запомненную версию этой функции.

Запоминание — это не что иное, как использование словаря (или аналогичного кеша) для хранения результатов, и вместо того, чтобы пересчитывать F(3) тысячу раз, мы вместо этого ищем его в словаре. Вот как это работает:

Шаги:

1. Проверяем, есть ли у нас в памяти уже результат для n, если да, то счастливых дней.
2. Если нет, вычислите его и немедленно сохраните в памяти.
3. Вернуть вычисленный результат.

Результаты лучше:

julia> @btime fibonacci_memory(30)
  1.630 μs (7 allocations: 1.97 KiB)
832040

Это 0,00163 мс против 2,28 мс раньше. Это ускорение в 1400 раз! 😜

Не изобретайте велосипед

Хотя написание этой версии не было слишком сложным, есть способ получше. А именно, пакет Memoize.jl делает именно то, что говорит его название. Использовать его очень просто. Установите его обычным способом с помощью Pkg.add("Memoize") или ] add Memoize, и вы получите замечательный маленький макрос, который может запомнить ваши функции для вас:

Это та же функция, что и в первом разделе, за исключением того, что теперь она заключена в макрос @memoize. Вот как это легко.

Посмотрим, как быстро:

julia> @btime fibonacci_easy(30)
  58.189 ns (0 allocations: 0 bytes)
83204

Подожди секунду! Это в 30 раз быстрее, чем раньше. Как это вообще возможно? 🧐

На самом деле, эта запоминаемая функция хранит все предыдущие результаты, так что теперь она вообще не выполняет никаких вычислений. Это буквально просто поиск результатов в словаре. Вы можете проверить словарь с помощью функции memoize_cache из пакета:

julia> memoize_cache(fibonacci_easy)
IdDict{Any, Any} with 30 entries:
  (7,)  => 13
  (29,) => 514229
  (25,) => 75025
  (21,) => 10946
  (15,) => 610
  (4,)  => 3
  (13,) => 233
  (26,) => 121393
  (18,) => 2584
  (10,) => 55
  (2,)  => 1
  (27,) => 196418
  (20,) => 6765
  (16,) => 987
  (5,)  => 5
  (8,)  => 21
  (28,) => 317811
  (24,) => 46368
  (12,) => 144
  ⋮     =>

Как видите, он содержит 30 записей, поэтому он уже выучил первые 30 чисел Фибоначчи.

Если вашей функции требуется много разных входных данных, и вы беспокоитесь, что может возникнуть проблема с памятью, вы можете переключить кэш на кеш наименее использовавшихся (LRU). Пример этого есть в главном ридми репозитория Memoize.jl.

И для чего-то совсем другого… 🥁

На всякий случай вот генератор Фибоначчи без мемоизации и без рекурсии:

Вот некоторое доказательство того, что это делает то же самое со всеми остальными функциями:

julia> for i in 1:10
           @show i, fibonacci(i), fib(i)
       end
(i, fibonacci(i), fib(i)) = (1, 1, 1)
(i, fibonacci(i), fib(i)) = (2, 1, 1)
(i, fibonacci(i), fib(i)) = (3, 2, 2)
(i, fibonacci(i), fib(i)) = (4, 3, 3)
(i, fibonacci(i), fib(i)) = (5, 5, 5)
(i, fibonacci(i), fib(i)) = (6, 8, 8)
(i, fibonacci(i), fib(i)) = (7, 13, 13)
(i, fibonacci(i), fib(i)) = (8, 21, 21)
(i, fibonacci(i), fib(i)) = (9, 34, 34)
(i, fibonacci(i), fib(i)) = (10, 55, 55)

И о, мальчик, это быстро:

julia> @btime fib(30)
  2.000 ns (0 allocations: 0 bytes)
832040

Это в 30 раз быстрее, чем поиск результата в памяти. О, Юля, ты зверь! 😆

Хотите еще немного Фибоначчи или жаждете еще Джулии? Проверьте это:

Краткое содержание

Если у вас есть функция, которая может извлечь выгоду из запоминания промежуточных результатов собственных вычислений, используйте функцию @memoize из того же пакета. Это сделает ваши функции намного быстрее, и это очень просто в использовании.

И если вам нужен язык программирования, который имеет смысл, прост в использовании и быстр — даже с циклами for — используйте Julia!

Весь используемый здесь код можно найти на GitHub по адресу https://github.com/niczky12/medium

Для полного доступа ко всем статьям на Medium, в том числе и к моей, рассмотрите возможность подписки здесь.