我可以利用惰性评估来引用未来的值而不会 space 泄漏吗?
Can I exploit lazy evaluation to reference future values without space leaks?
我想尝试 运行 在大量输入上使用一个成本适中的函数,使用该函数的部分输出作为其输入之一。代码 运行s 正如预期的那样,不幸的是它在进程中消耗了大量内存(堆上略低于 22GiB,最大驻留略高于 1GiB)。这是我的意思的一个简化示例:
{-# LANGUAGE OverloadedStrings #-}
import Data.List (foldl')
import qualified Data.Text as T
import qualified Data.Text.Lazy as TL
import qualified Data.Text.Lazy.IO as TL
import qualified Data.Text.Lazy.Builder as TB
main :: IO ()
main = TL.putStr $ TB.toLazyText showInts
showInts :: TB.Builder
showInts = foldMap fst shownLines
where
shownLines = map (showInt maxwidth) [0..10^7]
maxwidth = foldl' (\n -> max n . snd) 0 shownLines
showInt :: Int -> Int -> (TB.Builder, Int)
showInt maxwidth n = (builder, len)
where
builder = TB.fromText "This number: "
<> TB.fromText (T.replicate (maxwidth - len) " ") <> thisText
<> TB.singleton '\n'
(thisText, len) = expensiveShow n
expensiveShow :: Int -> (TB.Builder, Int)
expensiveShow n = (TB.fromText text, T.length text)
where text = T.pack (show n)
请注意,在showInts
的where子句中,showInt
将maxwidth
作为参数,其中maxwidth
本身取决于运行的输出宁showInt maxwidth
在整个名单上。
另一方面,如果我做了天真的事情,将 maxwidth
的定义替换为 foldl' max 0 $ map (snd . expensiveShow) [0..10^7]
,那么最大驻留空间将降至 44KiB。我希望像这样的性能可以在没有预计算 expensiveShow
然后用列表 [0..10^7]
.
压缩它的变通方法的情况下实现
我尝试严格使用列表(使用 foldl
包),但这并没有改善情况。
我正在尝试既要吃蛋糕又要吃:利用懒惰,同时也使事情足够严格,以至于我们不会堆积如山。这可能吗?或者是否有更好的技术来实现这一点?
你不能这样做。
问题是你的 showInts
必须遍历列表两次,第一次是找到最长的数字,第二次是用必要的格式打印数字。这意味着列表必须在第一遍和第二遍之间保存在内存中。这不是未评估的 thunk 的问题;很简单,完整评估的整个列表被遍历了两次。
唯一的解决办法是生成同一个列表两次。在这种情况下,这是微不足道的;只有两个 [0..10^7]
值,一个用于最大长度,第二个用于格式化它们。我怀疑在您的实际应用程序中您是从文件或其他东西中读取它们,在这种情况下您需要读取文件两次。
我想尝试 运行 在大量输入上使用一个成本适中的函数,使用该函数的部分输出作为其输入之一。代码 运行s 正如预期的那样,不幸的是它在进程中消耗了大量内存(堆上略低于 22GiB,最大驻留略高于 1GiB)。这是我的意思的一个简化示例:
{-# LANGUAGE OverloadedStrings #-}
import Data.List (foldl')
import qualified Data.Text as T
import qualified Data.Text.Lazy as TL
import qualified Data.Text.Lazy.IO as TL
import qualified Data.Text.Lazy.Builder as TB
main :: IO ()
main = TL.putStr $ TB.toLazyText showInts
showInts :: TB.Builder
showInts = foldMap fst shownLines
where
shownLines = map (showInt maxwidth) [0..10^7]
maxwidth = foldl' (\n -> max n . snd) 0 shownLines
showInt :: Int -> Int -> (TB.Builder, Int)
showInt maxwidth n = (builder, len)
where
builder = TB.fromText "This number: "
<> TB.fromText (T.replicate (maxwidth - len) " ") <> thisText
<> TB.singleton '\n'
(thisText, len) = expensiveShow n
expensiveShow :: Int -> (TB.Builder, Int)
expensiveShow n = (TB.fromText text, T.length text)
where text = T.pack (show n)
请注意,在showInts
的where子句中,showInt
将maxwidth
作为参数,其中maxwidth
本身取决于运行的输出宁showInt maxwidth
在整个名单上。
另一方面,如果我做了天真的事情,将 maxwidth
的定义替换为 foldl' max 0 $ map (snd . expensiveShow) [0..10^7]
,那么最大驻留空间将降至 44KiB。我希望像这样的性能可以在没有预计算 expensiveShow
然后用列表 [0..10^7]
.
我尝试严格使用列表(使用 foldl
包),但这并没有改善情况。
我正在尝试既要吃蛋糕又要吃:利用懒惰,同时也使事情足够严格,以至于我们不会堆积如山。这可能吗?或者是否有更好的技术来实现这一点?
你不能这样做。
问题是你的 showInts
必须遍历列表两次,第一次是找到最长的数字,第二次是用必要的格式打印数字。这意味着列表必须在第一遍和第二遍之间保存在内存中。这不是未评估的 thunk 的问题;很简单,完整评估的整个列表被遍历了两次。
唯一的解决办法是生成同一个列表两次。在这种情况下,这是微不足道的;只有两个 [0..10^7]
值,一个用于最大长度,第二个用于格式化它们。我怀疑在您的实际应用程序中您是从文件或其他东西中读取它们,在这种情况下您需要读取文件两次。