Рекурсия Haskell вычисляет центральные биномиальные коэффициенты

Question

Я новичок в Haskell и изучаю, как правильно использовать рекурсию.

Следующая функция (которая использует формулу для расчета central binomial coefficients) чрезвычайно медленная; например, grid (20,20) разбивает мой ноутбук. Можете ли вы помочь мне понять, почему?

grid::(Integer,Integer)->Integer 

grid (1, x) = 1 + x 

grid (x, 1) = 1 + x 

grid (x, y) = grid ((x-1),y) + grid ((x),(y-1)) 

Answer 1

Примечательно, что в вашем алгоритме нет кеширования или заметок. GHC не делает магии и не будет оптимизировать подобные проблемы. Для сетки 5x5 вы звоните grid 139 раз, для 6x6 503, для 7x7 - 1847, а для 10x10 - 97239 раз. К тому времени, когда вы доберетесь до 20x20, вы делаете так много рекурсивных вызовов, что это просто невозможно. Это то же самое понятие, как делать

fib 0 = 1 
fib 1 = 1 
fib n = fib (n - 1) + fib (n - 2) 

Вы собираетесь иметь экспоненциальное число вызовов по мере увеличения n, замедляя Вас. Вместо этого, вы можете подойти к этой проблеме аналогично тому, как это решается в случае последовательности Фибоначчи, используя списки и запоминанием:

fibs = 1 : 1 : zipWith (+) fibs (tail fibs) 

За исключением здесь вы хотите, чтобы вычислить биномиальных коэффициентов. Что касается реализации такого алгоритма, вам придется это выяснить самостоятельно;) Я могу указать вам на a previous answer of mine, который решил проблему для создания треугольника Паскаля.

Answer 2

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

Последствия этого более заметны при больших входных значений, как 20

Давайте посмотрим на вызов к сетке (5, 5).

Это расширяется следующим образом.

grid(5, 5) 

grid(4, 5) + grid(5, 4) 

(grid(3, 5) + grid(4, 4)) + (grid(4, 4) + grid(5, 3)) 

((grid(2, 5) + grid(3, 4)) + (grid(4, 3) + grid(3, 4))) + 
((grid(3, 4) + grid(4, 3)) + (grid(4, 3) + grid(5, 2))) 

...and so on 

Как вы можете видеть, что вещи получить из рук быстро даже при малых значениях х и у сетки (3, 4) и сетка (4, 3) рассчитываются несколько раз. Как было сказано ранее, решение, использующее zipWith, будет намного более эффективным.

Answer 3

Как объясняется в других ответах, проблема с вашей реализацией заключается в том, что количество рекурсивных вызовов является экспоненциальным, хотя число различных значений grid (x,y), которые необходимо вычислить, является просто квадратичным.

Решение проблемы называется memoization, что в основном означает кеширование значений, которые были вычислены ранее. Я определенно рекомендую вам написать свою собственную реализацию на основе списков, как рекомендовано @bheklilr.

Существует, однако, быстрое решение, предложенное существующих библиотеки, такие как MemoTrie:

import Data.MemoTrie 

grid :: (Integer, Integer) -> Integer 
grid = memo grid' 

grid' :: (Integer, Integer) -> Integer 
grid' (1, x) = 1 + x 
grid' (x, 1) = 1 + x 
grid' (x, y) = grid (x - 1, y) + grid (x , y - 1) 

Обратите внимание, что в настоящее время grid определяется как значение- это не полиморфные и не принимает никаких аргументов (хотя это значение функция).Вызов memo создает один экземпляр trie, который кэширует все значения и использует grid' для вычисления значений, отсутствующих в кеше.

Answer 4

Альтернатива memoization - генерировать строки итеративно, уменьшая количество вычислений.

central :: [Integer] -> [Integer] 
central x = zipWith (+) x (0:central x) 

Например, чтобы сформировать следующую строку из предыдущего

> central [1,2,3] 
[1,3,6] 

или для вашей функции сетки

grid x y = (iterate central [1..]) !! x !! y 

и для индекса на основе нулевого

> grid 2 4 
35