时间戳

首页 > 解决方案 > Haskell - 我如何编写一个惯用且有效的循环？

haskell - Haskell - 我如何编写一个惯用且有效的循环？

问题描述

我对 Haskell 比较陌生，所以我正在解决一些旧的代码出现问题以熟悉该语言。

但是，我在 2017 年第 17 天，第二部分卡住了。我已经尝试了三种解决方案来解决这个问题。

（编辑：将代码块简化为更清晰的示例）

以下解决方案是我希望能够适度有效地工作的东西：

run :: IO()
run = do
    print "Starting:"
    print (iteration''' 0 1 3 0 50000000)

iteration''' :: Int -> Int -> Int -> Int -> Int -> (Int, Int, Int, Int)
iteration''' cp cv ss zv 0 = (cp, cv, ss, zv)
iteration''' cp cv ss zv count = iteration''' ncp ncv ss nzv (count - 1)
    where
        ncp = ((cp + ss) `mod` cv) + 1
        nzv = if ncp == 1 then cv else zv
        ncv = cv + 1

问题是这三个都非常低效，无论是在内存方面还是在 CPU 方面。等效的 C 代码将类似于以下内容（非常快速地完成）。

int stepSize = 3;
int zv = 0;
int position = 0;
for (int i = 0; i < 50000000; i++) {
    position = (position + stepSize) % i;
    if (position == 0) zv = i;
}

我认为iteration'''可以编译成类似的东西——但它会消耗千兆字节的内存并循环很长时间。

总结我的问题 - 在 Haskell 中“有效解决这个问题”的惯用方法是什么？当不需要实际的对象转换时，为什么它会占用这么多的堆空间？

我正在使用 ghc (cabal) 进行编译。

标签： haskell

解决方案

为了完整起见，正如 Daniel Wagner 和 chi 所回答的：

所述代码中的问题是严格性（隐含大量惰性求值的整数会导致大量开销）。

这种方法要快很多（添加表BangPatterns头）

iteration''' :: Int -> Int -> Int -> Int -> Int -> (Int, Int, Int, Int)
iteration''' !cp !cv !ss !zv 0 = (cp, cv, ss, zv)
iteration''' !cp !cv !ss !zv !count = iteration''' ncp ncv ss nzv (count - 1)
    where
        ncp = ((cp + ss) `mod` cv) + 1
        nzv = if ncp == 1 then cv else zv
        ncv = cv + 1

我认为这意味着这也是编写（一些）高性能代码的惯用方式！

推荐阅读