Алгоритмическая забава с хэшами

 memoization ||= Hash.new do |hash,key| hash[key] = case when (key % 3 == 0) && (key % 5 != 0) 'Fizz' when (key % 3 != 0) && (key % 5 == 0) 'Buzz' when (key % 3 == 0) && (key % 5 == 0) 'FizzBuzz' else key end end 

Мы создаем Hash, который инициализируется правильным значением FizzBuzz для каждого передаваемого ему числового ключа. Запустите его для диапазона до 100:

 (1..100).each { |n| memoization[n] } 

Хэш памятки создан и сопоставил каждому ключу от 1 до 100 значение FizzBuzz. В следующий раз, когда нам понадобится значение FizzBuzz для числа в этом диапазоне, его получит простое Hash#fetch .

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

 require 'net/http' http = Hash.new{|hash,key| hash[key] = Net::HTTP.get_response(URI(key)).body } puts http['http://www.google.com'] # make actual request puts http['http://www.google.com'] # get cached value 

Теперь давайте посмотрим на производительность. Вот тесты (на моей машине — ваши, очевидно, будут отличаться) при запуске каждого из наших решений FizzBuzz дважды для диапазона 1..1 000 000 .

При первом запуске кода напоминания он работает очень медленно. Ruby должен создать Hash, а также выполнить условную логику. Но во 2-й раз , и каждый раз после этого, его выполнение значительно быстрее. Это потому, что Hash уже содержит все значения для этого диапазона, поэтому он просто должен искать их всякий раз, когда мы просим об этом, а не вычислять их заново.

Вы можете заметить, что, хотя быстр для последующих запусков, метод if..elsif все же не так быстр, как подход if..elsif . Это потому, что мы не получаем полного преимущества от кэширования, применяя его к простым линейным алгоритмам, таким как FizzBuzz. Чтобы максимально использовать запоминание, нам нужно использовать его в более сложной, полиномиальной или алгоритмической логике экспоненциального порядка.

Рекурсивные хеши

Рекурсия — типичная область для алгоритмов быстрого роста. Давайте посмотрим на классический пример рекурсии: факториальная проблема. Обычная рекурсивная реализация выглядит так:

 def factorial(x) x == 1 ? 1 : x * factorial(x-1) end 

Мы можем запомнить это с помощью хэша:

 factorial_hash ||= Hash.new do |hash,key| hash[key] = key * hash[key-1] end # initialize special cases fib_hash[1] = 1; fib_hash[2] = 2 

Здесь мы инициализируем Hash таким образом, чтобы заставить код инициализации быть выполненным n раз для ввода n . Когда мы в первый раз запустим, скажем, factorial_hash[5] код будет выполнен 5 раз, создав хэш для ключей 2-5. Затем каждый раз, когда нам нужно получить факториальное значение числа до 5, Hash просто сделает простой поиск и выберет правильное значение.

Выполните каждую технику дважды, чтобы получить факториал 3000:

 factorial(3000) factorial(3000) factorial_hash[3000] factorial_hash[3000] 

Вот время:

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

Давайте попробуем что-то еще более сложное: последовательность Фибоначчи . Вот стандартный подход:

 def fibonacci(n) n <= 2 ? 1 : fibonacci(n - 1) + fibonacci(n - 2) end 

и вот наш подход кеширования Hash:

 fib_hash ||= Hash.new do |hash,key| hash[key] = hash[key-1] + hash[key-2] end # initialize special cases fib_hash[1] = 1; fib_hash[2] = 1 

Запуск каждого подхода дважды, чтобы получить значение Фибоначчи в 35, дает следующие моменты времени :

 fibonacci(35) fibonacci(35) fib_hash[35] fib_hash[35] 

Теперь даже первый запуск хэш-подхода значительно быстрее, чем некешированный рекурсивный метод. Последующие запуски приводят в замешательство некэшируемый метод! Чем сложнее проблема, тем больше преимуществ, полученных с помощью запоминания.

Но у каждой серебряной подкладки есть облако. Использование хэшей рекурсивно добавляет больше данных в стековый фрейм нашего приложения, что означает, что рекурсивный хэш-подход имеет гораздо более низкий порог для ошибок типа переполнения стека (это ошибка , а не веб-сайт). Таким образом, для алгоритмов с большим диапазоном входных значений рекурсивные хеши, вероятно, не лучшее решение.

Вывод

Хэши — это не просто способ передачи параметров в методы. При правильном использовании они могут помочь сделать наш код более элегантным, быстрым или иногда одновременно. Однако нам необходимо знать об их недостатках и знать, как и когда их эффективно использовать.

Код, представленный в этой статье, можно найти в следующих разделах:

• FizzBuzz
• мемоизации