如何存储和引用递归函数的中间值(Haskell)

问题描述 投票:0回答:1

我最近几周才开始学习Haskell。我正在使用Euler项目的问题进行学习,目前正在尝试找出是否有可能。不需要找人给我答案,只需要帮助了解Haskell中的数据结构即可。

我目前正在研究problem 484,它指定了一个递归函数。编写函数不是问题,我目前有:

import Math.NumberTheory.Primes
import Data.Maybe
import Data.List

derivative :: Integer -> Integer
derivative x
    | x < 2 = error "Error: Attempt to evaluate outside domain"
    | isPrime x = 1
    | otherwise = (derivative a)*b + a*(derivative b)
    where
        [a, b] = int_split x

--this function find the first pair of divisors
int_split :: Integer -> [Integer]
int_split n = [first_div, n `div` first_div] where
              first_div = fromJust $ find (\x -> (n `mod` x) ==0) [2..]

这似乎很好,因为计算与问题给出的样本值匹配。问题在于,我需要针对非常大的值进行计算,以使所有值均达到5x10 ^ 15。将所有值提高到〜10 ^ 8的速度非常快,但过了很慢。仅使用map绝对是无效的,因为它没有利用我们可以引用先前计算出的值的事实。

我的想法是更改函数以将值存储在查找表中,因为这些值是根据计算得出的功能可以引用的。我尝试使用Data.Map存储值,但是我不知道如何以递归方式将其集成到函数中。在Haskell中这可能吗?还是有我不打算存储和使用中间计算的更好方法?

haskell recursion
1个回答
0
投票

我真的不认为优化您当前的方法可以在合理的时间内为您找到所需的答案。假设您进行了很好的优化,可以在一个时钟周期内为任意数字计算解决方案,并为您提供一个相对普通的3GHz处理器。

$ units
You have: 3 giga hertz
You want: days
        reciprocal conversion
        * 3.8580247e-15
        / 2.592e+14

即使以如此之快的速度,每天也只能解决2.5e14的输入。因此,计算高达5e15的解决方案将花费您6天的时间。但是,当然,即使算法的最佳优化也永远无法让您步入正轨。与Project Euler问题一样,在使用计算机解决问题之前,您必须做一些简化的数学运算以减小问题的严重程度。

© www.soinside.com 2019 - 2024. All rights reserved.