V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
mofe
V2EX  ›  问与答

Haskell 运算斐波那契数列怎么这么慢,比 JS 慢多了。。

  •  
  •   mofe · 2022-03-12 20:40:25 +08:00 · 1939 次点击
    这是一个创建于 747 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Haskell 代码

    fib :: (Integral a) => a -> a
    fib 0 = 0
    fib 1 = 1
    fib n = fib(n-1) + fib(n-2)
    
    main :: IO()
    
    main = do
      print (fib 40)
    

    M1 Max CPU 上足足跑了 25 秒

    JS 代码

    function fib(n){
        switch(n) {
            case 0: return 0;
            case 1: return 1;
            default: return fib(n-1) + fib(n-2);
        }
    }
    
    console.time('fib'); fib(40); console.timeEnd('fib');
    

    JS 里只需要 1 秒

    12 条回复    2022-03-13 08:31:25 +08:00
    Buges
        1
    Buges  
       2022-03-12 20:50:11 +08:00 via Android
    你这个 fib 是个纯函数,结果又忽略了,估计直接被优化没了。
    mofe
        2
    mofe  
    OP
       2022-03-12 20:57:41 +08:00
    ![]( https://mofe.io/2022/0312/MgeZTedJUJry-HSCmIfjm.png)

    测试过了,加了 `console.log` 速度没差别
    xiaopc
        3
    xiaopc  
       2022-03-12 21:06:47 +08:00 via iPhone
    ghc 开优化呢
    mofe
        4
    mofe  
    OP
       2022-03-12 21:44:11 +08:00
    ![]( https://mofe.io/2022/0312/zyom0llV0weKRYKiyAH0R.png)


    @xiaopc 开了优化之后 3.4 秒,的确快了很多,但还是比 nodejs 慢

    ![]( https://mofe.io/2022/0312/5ZhTUUyerKhkk51-pV5kt.png)
    mofe
        5
    mofe  
    OP
       2022-03-12 21:44:58 +08:00
    使用 `ghc -O2 --make fib.hs`这个参数,还有什么优化方法吗?
    @xiaopc
    secondwtq
        6
    secondwtq  
       2022-03-12 21:48:35 +08:00   ❤️ 2
    GHC 默认的 class constraint 实现是传一个类似于 vtable 的东西进去,相当于 Java 泛型(真不是黑 Java ...
    并且默认所有的值都是 boxed
    就是说你每加一次都是调个函数

    你可以把 class constraint 去掉改成 Int 加优化,或者直接用 unboxed 不开优化也可以。离 C 差点,干掉 JS 还是问题不大的
    wlh233
        7
    wlh233  
       2022-03-12 21:49:38 +08:00   ❤️ 2
    类型写成 fib :: Int -> Int 就快了
    mofe
        8
    mofe  
    OP
       2022-03-12 21:56:47 +08:00
    ```haskell
    fib :: Int -> Int
    fib n =
    if n < 2 then
    n
    else
    fib (n - 1) + fib (n - 2)

    main :: IO()
    main = do
    print (fib 40)
    ```

    @wlh233
    @secondwtq

    真的是,代码改成这样只需要 0.46s 就运行完了。。。果然 haskell 更快些。。。


    ```haskell
    fib :: Int -> Int
    fib 0 = 0
    fib 1 = 1
    fib n = fib(n-1) + fib(n-2)

    main :: IO()
    main = do
    print (fib 40)
    ```
    这个版本和上面慢一丢丢。。0.48s 左右
    wlh233
        9
    wlh233  
       2022-03-12 22:01:59 +08:00
    我觉得是因为 haskell 里有 Int 和 Integer 两种整数类型,你那么写它用的类型应该是 Integer ,相当于用了个大数类
    mofe
        10
    mofe  
    OP
       2022-03-12 22:47:41 +08:00
    @wlh233 的确是 Integer 的锅,
    ```haskell
    fib :: Integer -> Integer
    fib 0 = 0
    fib 1 = 1
    fib n = fib(n-1) + fib(n-2)

    main :: IO()
    main = do
    print (fib 40)
    ```

    这段代码跑了 3.33 秒
    ![]( https://mofe.io/2022/0312/FX3bYI2n2il4K7HD515rj.png)
    7S5cVx
        11
    7S5cVx  
       2022-03-12 22:50:05 +08:00
    歪个楼,不想开 `O2` 的可以这么写

    ```haskell
    {-# LANGUAGE MagicHash #-}

    import GHC.Exts

    fib' :: Int# -> Int#
    fib' 0# = 0#
    fib' 1# = 1#
    fib' n = fib' (n -# 1#) +# fib' (n -# 2#)
    {-# INLINE fib' #-}

    main :: IO ()
    main = print $ I# (fib' 40#)
    ```

    换个形式写可能还会更快 ( :doge:
    mofe
        12
    mofe  
    OP
       2022-03-13 08:31:25 +08:00
    @7S5cVx 这啥编程语言啊,还有魔法。。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4669 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 05:36 · PVG 13:36 · LAX 22:36 · JFK 01:36
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.