主页 / coding / 问题 / 77922852
Accepted
salferdez
Asked: 2024-02-02 03:25:02 +0800 CST

提高斯特林数计算效率

  • 772

我一直在尝试探索Haskell中递归的可能性，但在面对大递归时如何提高效率我不太了解。今天，我想做一个计算第二类斯特林数的函数：

factorial :: Integer -> Integer
factorial n = helper n 1
    where
        helper 1 a = a
        helper n a = helper (n-1) (a*n)


stirling :: Integer -> Integer -> Integer
stirling n 1 = 1
stirling n 2 = ((2 ^n)- 2) `div` 2
stirling n k
    | k > n      = 0
    | k == n     = 1
    | k == (n-1) = (factorial n) `div` (factorial 2 * (factorial(n-2)))
    | otherwise  = stirling (n-1) (k-1) + k *(stirling (n-1) k)

我一直在尝试创建一个辅助函数，就像阶乘定义中一样，可以避免 Haskell 的惰性求值占用过多内存资源带来的不便。我想做同样的事情，在每次调用中计算乘积

k *(stirling (n-1) k)

递归，但我没有掌握它的窍门。有任何想法吗？

PD：代码已经运行得相当不错，但我是 Haskell 的新手，我仍然不知道可能性是什么。欢迎任何改进（尽管我认为不使用任何库；我想在进入之前学习基础知识）。

performance

2 个回答

  1. 我现在无法写出非常详细的解释，但您可以通过以下方式使其更快：

    • 使用数学简化一些公式
    • 使用移位代替除法
    • 用于Int输入而不是Integer

    然后你会得到这个：

    import Data.Bits

stirling :: Int -> Int -> Integer
stirling n 1 = 1
stirling n 2 = (1 `unsafeShiftL` (n - 1)) - 1
stirling n k
    | k > n        = 0
    | k == n       = 1
    | k == (n - 1) = fromIntegral ((n * (n - 1)) `unsafeShiftR` 1)
    | otherwise    = stirling (n - 1) (k - 1) + fromIntegral k * stirling (n - 1) k

    我接下来要尝试的是动态编程以避免冗余计算。

    并且您使用累加器样式使非尾递归调用之一成为尾递归，就像在此博客文章中所做的那样：https ://www.haskell.org/ghc/blog/20190728-free-variable-traversals.html

    • 0
  2. Best Answer

    至少在我的测试中，您的实现似乎已经具有相当的内存效率。例如：

    % time ./test salferdez 32 16
1194461517469807833782085
11.50user 0.00system 0:11.48elapsed 100%CPU (0avgtext+0avgdata 8704maxresident)k
0inputs+0outputs (0major+1267minor)pagefaults 0swaps

    更改参数（向上或向下）似乎不会对 8MB 驻留发生太大变化，因此我预计这只是 Haskell 程序的最低启动成本。另一方面，它似乎很慢。参数甚至比我在这里使用的参数稍大一些——比如，将它们都加倍——花费的时间比我愿意等待的时间还要长。直接直接实现维基百科中的公式似乎要快得多，同时保留良好的内存配置文件：

    % time ./test dmwit 32 16
1194461517469807833782076
0.00user 0.00system 0:00.01elapsed 16%CPU (0avgtext+0avgdata 4352maxresident)k
0inputs+0outputs (0major+206minor)pagefaults 0swaps
% time ./test dmwit 10000 5000
<snip'd very very long output>
10.62user 0.02system 0:10.62elapsed 100%CPU (0avgtext+0avgdata 16716maxresident)k
0inputs+0outputs (1major+26643minor)pagefaults 0swaps

    （我没有在这些运行和之前的运行之间重新编译，因此您可以确定我们都获得了相同级别的优化。）

    另一方面，我得到的答案确实与你略有不同。也许您可以在我们的一个或另一个代码中发现错误。无论如何，这是来自维基百科*的公式，这是我对其最直接翻译的看法：

    stirling n k = sum [(-1)^(k-i)*i^n`div`(product [1..k-i]*product[1..i]) | i <- [0..k]]

    不要忘记使用 GHC 进行编译-O2，并让 GHC 完成所有思考如何使其快速且内存高效的肮脏工作。

    * StackOverflow 确实有一种直接包含图像而不是链接图像的机制，但它似乎对我不起作用。不知道为什么！

    • 0

相关问题