стиля Non-pointfree значительно медленнее

У меня есть следующий, часто цитируемый код для вычисления энного количества Фибоначчи в Haskell:стиля Non-pointfree значительно медленнее

fibonacci :: Int -> Integer 
fibonacci = (map fib [0..] !!) 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1)

Используя это, я могу сделать вызовы, такие как:

ghci> fibonacci 1000

и получите почти мгновенный ответ.

Однако, если я изменить код выше, так что это не в стиле pointfree, т.е.

fibonacci :: Int -> Integer 
fibonacci x = (map fib [0..] !!) x 
    where fib 0 = 0 
      fib 1 = 1 
      fib n = fibonacci (n-2) + fibonacci (n-1)

это существенно медленнее. В той степени, в которой такой звонок, как

ghci> fibonacci 1000

висит.

Насколько я понимаю, эти два фрагмента кода были эквивалентны, но GHCi требует отличия. У кого-нибудь есть объяснение этого поведения?

источник

2015-10-04 MadMonty

Первое определение больше похоже на 'fibonacci = let k = map fib [0 ..] в \ x -> k !! x'. Вероятно, он разделяет список результатов, а не пересчитывает их каждый раз. – melpomene

Мм, поэтому я доволен, что это «совместное использование» (memoization), которое делает первый супер быстрый. Но зачем делать то же самое для второго? – MadMonty

Вы используете свой код в GHCI без оптимизации. Попробуйте скомпилировать обе функции с помощью '-O2' и посмотреть, достаточно ли GHC для решения вашей проблемы. – user2407038

Чтобы наблюдать разницу, вам следует, вероятно, взглянуть на ядро. Я предполагаю, что это сводится к сравнению (примерно)

let f = map fib [0..] in \x -> f !! x

\x -> let f = map fib [0..] in f !! x

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

Бывает, что в этом конкретном случае GHC удалось оптимизировать второе в первом, как только оптимизация включена.

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

источник

2015-10-04 18:24:31 chi

Я попытался найти его, но вычеркнул. Я думаю, что у меня есть это на моем ПК дома. То, что я читал, было то, что функции с использованием фиксированной точки были быстрее. Существуют и другие причины использования фиксированной точки. Я столкнулся с этим, написав эту итеративную функцию Фибоначчи. Я хотел посмотреть, как будет выполняться итеративная версия, тогда я понял, что у меня нет готового способа измерения. Я неофит Хаскелла. Но вот итеративная версия для кого-то для тестирования. Я не мог определить это, если бы не использовал точку после первой последней функции. Я не мог уменьшить его дальше. параметр [0,1] является фиксированным и не должен указываться в качестве значения параметра.

Prelude> fib = last . flip take (iterate (\ls -> ls ++ [last ls + last (init ls)]) [0,1]) 
Prelude> fib 25

[0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368,75025]

источник

2018-02-20 20:53:25 fpmora

стиля Non-pointfree значительно медленнее

ответ

Смежные вопросы