ST Monad的多次更新

Question

我想学习使用ST Monad。因此，我想重写一些代码计算，为每个整数——直到一个极限——它的所有适当除数的列表。结果应该是一个数组，索引"n"的条目应该是它的适当除数列表。

它是通过为每个整数"n"计算其倍数的列表"l"，并将索引"m"处的"l"中的每个倍数"m"的除数"n"添加到列表中来完成的。

这是我想修改的代码：

properDivisorsOf' :: forall a. (Integral a, Ix a) => a -> Array a [a]
properDivisorsOf' limit =
let generate :: (Integral a, Ix a) => a -> Array a [a] -> Array a [a]
generate n acc
| n > (limit `div` 2) = acc
| otherwise           =
let acc' = acc // [(i, n : (acc ! i)) | i <- [2*n, 3*n .. limit]]
in  generate (n + 1) acc'
in generate 1 (array (1, limit) [(i, [])| i <- [1..limit]])

我就是这样尝试的：

properDivisorsOf :: forall a. (Integral a, Ix a) => a -> Array a [a]
properDivisorsOf limit =
let result :: ST s (STArray s a [a])
result = newArray (1, limit) [] -- In the beginning for every number: no divisors known (empty list) 
update (index, divisor) = do
l <- readArray result index -- extracting list of divisors of number 'index'
let u = divisor : l
writeArray result index u   -- and adding 'divisor' to the list
content :: [(a, a)]
content = do
n <- [1 .. (limit `div` 2)]
multiple <- [2*n, 3*n .. limit]
return (multiple, n)
doUpdate = map update content -- update result for all multiples (in content)

在runSTArray结果中

不幸的是，它没有编译，错误消息也没有对我说什么。我有两个问题：

1. 为什么不编译？如何正确提取条目
2. 一个经验丰富的Haskell程序如何在他必须与ST Monad合作的限制下解决这个问题(出于效率目的)

EDIT：编译器消息

Couldn't match expected type `[t0]'
with actual type `STArray i0 a [a]'
In the second argument of `(:)', namely `l'
In the expression: divisor : l
In an equation for `u': u = divisor : l

失败，已加载模块：无。

Answer 1

解决方案

2.一个经验丰富的Haskell程序在必须与ST Monad合作的限制下(出于效率目的)如何解决这个问题？

我绝不是一个经验丰富的Haskell程序员，但我会使用下面的代码命令式代码，但这里是从您的代码的直接转换：

properDivisorsOf :: forall a. (Integral a, Ix a) => a -> Array a [a]
properDivisorsOf limit =
runSTArray $ do
result <- newArray (1, limit) []
mapM_ (update result) content
return result
where
content :: [(a, a)]
content = do
n <- [1 .. (limit `div` 2)]
multiple <- [2*n, 3*n .. limit]
return (multiple, n)
update arr (index, divisor) = do
l <- readArray arr index -- extracting list of divisors of number 'index'
let u = divisor : l
writeArray arr index u   -- and adding 'divisor' to the list

比较非ST段与ST段：

非ST变体

您原来的功能：

main = print $ properDivisorsOf' 100000

$。\Original.exe+RTS-sOriginal.exe：内存不足

我们用10000:交换100000

堆中分配的221476488字节GC期间复制了21566328字节172813068字节最大驻留时间(9个样本)4434480字节最大斜率使用中的总内存为210 MB(由于碎片而丢失5 MB)总时间(经过)平均暂停最大暂停Gen 0 378 colls，0 par 0.41s 0.43s 0.0011s 0.0024sGen 1 9 colls，0 par 0.36s 0.37s 0.0409s 0.1723sINIT时间0.00s(经过0.00s)MUT时间0.28s(经过0.60s)GC时间0.77s(经过0.80s)退出时间0.00s(经过0.02s)总时间1.05s(经过1.42s)%GC时间73.1%(56.4%)分配速率787471957字节/MUT秒生产力占总用户的26.9%，占总运行时间的19.8%

尽管程序速度很快(毕竟是1秒)，但210MB的内存占用非常明显。此外，所需的内存也在增长，对于20000的限制，您需要大约800MB，对于20000大约1.9GB。

ST变体

$。\ST.exe+RTS-s>$null堆中分配的300728400字节GC期间复制了89696288个字节13628272字节最大驻留时间(10个样本)最大斜率为292972字节正在使用的总内存为38 MB(由于碎片而丢失0 MB)总时间(经过)平均暂停最大暂停Gen 0 565 colls，0 par 0.14s 0.14s 0.0002s 0.0008sGen 1 10 colls，0 par 0.09s 0.08s 0.0076s 0.0223sINIT时间0.00s(经过0.00s)MUT时间0.11s(经过0.16s)GC时间0.23s(经过0.21s)退出时间0.00s(经过0.00s)总时间0.34s(0.38s)%GC时间68.2%(56.6%)分配速率每MUT秒2749516800字节生产力占总用户的31.8%，占总运行时间的28.9%

只有38 MB，约为原始实现的17%，但计算出的值是原来的10倍(10000比100000)。

强制性变体

如果你扔掉content，你会得到以下程序：

import Data.Array (Array(..), Ix)
import Data.Array.ST (newArray, readArray, writeArray, runSTArray)
import Control.Monad (forM_)
properDivisorsOf :: (Integral a, Ix a) => a -> Array a [a]
properDivisorsOf limit =
runSTArray $ do
result <- newArray (1, limit) []
forM_ [1.. (limit `div`2)] $ n -> do
forM_ [2*n, 3*n .. limit] $ index -> do
l <- readArray result index
writeArray result index (n:l)
return result
main = print $ properDivisorsOf 100000

$。\Imperative.exe+RTS-s>$null堆中分配了237323392个字节GC期间复制63304856字节13628276字节最大驻留时间(7个样本)138636字节最大斜率正在使用的总内存为34 MB(由于碎片而丢失0 MB)总时间(经过)平均暂停最大暂停Gen 0 447 colls，0 par 0.12秒0.09秒0.0002秒0.0008秒Gen 1 7 colls，0 par 0.05秒0.06秒0.0087秒0.0224秒INIT时间0.00s(经过0.00s)MUT时间0.11s(经过0.18s)GC时间0.17s(经过0.16s)退出时间0.00s(经过0.00s)总时间0.30s(经过0.34s)%GC时间57.9%(经过45.9%)分配速率每MUT秒2169813869字节生产力占总用户的42.1%，占总运行时间的36.9%

为什么不编译

1. 为什么不编译？如何正确提取条目

从某种意义上说，您提取的代码是正确的(请参阅上文，这与您使用的代码几乎相同)，但推断出的update类型是错误的，因为您的使用不正确。例如，update应该在STmonad中工作，因此您应该将其与mapM一起使用，而不是与map一起使用。此外，还有一些其他的问题，例如，您定义了doUpdate，但从未使用过它