haskell - ST-Monad 中的多项更新

Question

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

这是通过为每个整数“n”计算其倍数的列表“l”，并将“l”中的每个倍数“m”添加到索引“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(出于效率目的)的限制下如何解决这个问题

编辑:编译器消息

    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. How would an experienced Haskell-Programm solve this problem under the restriction that he has to work with the ST-Monad (for efficiency purposes)?

我绝不是一个经验丰富的 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: out of memory

We exchange 100000 by 10000:

     221,476,488 bytes allocated in the heap      21,566,328 bytes copied during GC     172,813,068 bytes maximum residency (9 sample(s))       4,434,480 bytes maximum slop             210 MB total memory in use (5 MB lost due to fragmentation)                                    Tot time (elapsed)  Avg pause  Max pause  Gen  0       378 colls,     0 par    0.41s    0.43s     0.0011s    0.0024s  Gen  1         9 colls,     0 par    0.36s    0.37s     0.0409s    0.1723s  INIT    time    0.00s  (  0.00s elapsed)  MUT     time    0.28s  (  0.60s elapsed)  GC      time    0.77s  (  0.80s elapsed)  EXIT    time    0.00s  (  0.02s elapsed)  Total   time    1.05s  (  1.42s elapsed)  %GC     time      73.1%  (56.4% elapsed)  Alloc rate    787,471,957 bytes per MUT second  Productivity  26.9% of total user, 19.8% of total elapsed

Even though the program is pretty fast (1s after all), the memory footprint of 210MB is quite noticeable. Also, the memory needed grows squre, for a limit of 20000 you would need around 800 MB, for 20000 around 1.9GB.

ST variant

$ .\ST.exe +RTS -s > $null     300,728,400 bytes allocated in the heap      89,696,288 bytes copied during GC      13,628,272 bytes maximum residency (10 sample(s))         292,972 bytes maximum slop              38 MB total memory in use (0 MB lost due to fragmentation)                                    Tot time (elapsed)  Avg pause  Max pause  Gen  0       565 colls,     0 par    0.14s    0.14s     0.0002s    0.0008s  Gen  1        10 colls,     0 par    0.09s    0.08s     0.0076s    0.0223s  INIT    time    0.00s  (  0.00s elapsed)  MUT     time    0.11s  (  0.16s elapsed)  GC      time    0.23s  (  0.21s elapsed)  EXIT    time    0.00s  (  0.00s elapsed)  Total   time    0.34s  (  0.38s elapsed)  %GC     time      68.2%  (56.6% elapsed)  Alloc rate    2,749,516,800 bytes per MUT second  Productivity  31.8% of total user, 28.9% of total elapsed

Only 38 MB, which is ~17% of your original implementation, but calculates 10 times more values (10000 vs 100000).

Imperative variant

If you throw content away, you'll end up with the following program:

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     237,323,392 bytes allocated in the heap      63,304,856 bytes copied during GC      13,628,276 bytes maximum residency (7 sample(s))         138,636 bytes maximum slop              34 MB total memory in use (0 MB lost due to fragmentation)                                    Tot time (elapsed)  Avg pause  Max pause  Gen  0       447 colls,     0 par    0.12s    0.09s     0.0002s    0.0008s  Gen  1         7 colls,     0 par    0.05s    0.06s     0.0087s    0.0224s  INIT    time    0.00s  (  0.00s elapsed)  MUT     time    0.11s  (  0.18s elapsed)  GC      time    0.17s  (  0.16s elapsed)  EXIT    time    0.00s  (  0.00s elapsed)  Total   time    0.30s  (  0.34s elapsed)  %GC     time      57.9%  (45.9% elapsed)  Alloc rate    2,169,813,869 bytes per MUT second  Productivity  42.1% of total user, 36.9% of total elapsed

为什么不能编译？

1. Why doesn't it compile? How can I extract the entry correctly?

我感觉，您提取正确(见上文，这与您使用的代码几乎相同)，但是 update 的推断类型是错误的，因为您的用法不正确。例如，update 应该在 ST monad 中工作，因此您可以将其与 mapM 一起使用，而不是与 map 一起使用。此外，还有一些其他问题，例如您定义了 doUpdate 但从未使用它。