gpt4 book ai didi

elm - 有没有办法在 elm 中缓存函数结果?

转载 作者:行者123 更新时间:2023-12-04 12:06:39 25 4
gpt4 key购买 nike

我想用 O(1) 计算第 n 个斐波那契数复杂性和 O(n_max)预处理。

为此,我需要像在此 C++ 代码中一样存储先前计算的值:

#include<vector>
using namespace std;
vector<int> cache;
int fibonacci(int n)
{
if(n<=0)
return 0;
if(cache.size()>n-1)
return cache[n-1];
int res;
if(n<=2)
res=1;
else
res=fibonacci(n-1)+fibonacci(n-2);
cache.push_back(res);
return res;
}

但它依赖于榆树不允许的副作用。

最佳答案

斐波那契

Elm 中斐波那契的正常递归定义是:

fib1 n = if n <= 1 then n else fib1 (n-2) + fib1 (n-1)

缓存

如果你想要简单的缓存, maxsnew/lazy library应该管用。它使用原生 JavaScript 代码中的一些副作用来缓存计算结果。它通过审查来检查 native 代码是否没有向 Elm 用户公开副作用,为了便于内存,很容易检查它是否保留了程序的语义。

你应该小心你如何使用这个库。当您创建 Lazy值,第一次强制它需要时间,从那时起它就会被缓存。但是如果你重新创建 Lazy value 多次,那些不会共享缓存。例如,这个 没有工作:
fib2 n = Lazy.lazy (\() ->
if n <= 1
then n
else Lazy.force (fib2 (n-2)) + Lazy.force (fib2 (n-1)))

工作解决方案

我通常看到用于斐波那契的是一个懒惰的列表。我将给出整个编译代码:
import Lazy exposing (Lazy)
import Debug

-- slow
fib1 n = if n <= 1 then n else fib1 (n-2) + fib1 (n-1)
-- still just as slow
fib2 n = Lazy.lazy <| \() -> if n <= 1 then n else Lazy.force (fib2 (n-2)) + Lazy.force (fib2 (n-1))

type List a = Empty | Node a (Lazy (List a))

cons : a -> Lazy (List a) -> Lazy (List a)
cons first rest =
Lazy.lazy <| \() -> Node first rest

unsafeTail : Lazy (List a) -> Lazy (List a)
unsafeTail ll = case Lazy.force ll of
Empty -> Debug.crash "unsafeTail: empty lazy list"
Node _ t -> t

map2 : (a -> b -> c) -> Lazy (List a) -> Lazy (List b) -> Lazy (List c)
map2 f ll lr = Lazy.map2 (\l r -> case (l,r) of
(Node lh lt, Node rh rt) -> Node (f lh rh) (map2 f lt rt)
) ll lr

-- lazy list you can index into, better speed
fib3 = cons 0 (cons 1 (map2 (+) fib3 (unsafeTail fib3)))

所以 fib3是一个包含所有斐波那契数列的惰性列表。因为它在内部使用 fib3 本身,所以它将使用相同的(缓存的)惰性值并且不需要进行太多计算。

关于elm - 有没有办法在 elm 中缓存函数结果?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30971123/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com