Несколько обновлений в ST-Monad
Я хочу учиться, используя 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
К сожалению, он не компилируется, и сообщение об ошибке ничего не говорит мне. У меня есть два вопроса:
- Почему он не компилируется? Как правильно извлечь запись?
- Как опытный Haskell-Programm решит эту проблему при условии, что ему придется работать с 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
Сбой, загруженные модули: нет.
1 ответ
Решение
2. Как опытный Haskell-Programm решит эту проблему при условии, что ему придется работать с 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 -s Original.exe: недостаточно памяти
Мы обмениваемся 100000 от 10000:
221476 488 байт, выделенных в куче. 21 566 328 байт, скопированных во время GC. 172813 068 байт, максимальная резидентность (9 выборок). 4 434 480 байт, максимальный спад 210 МБ общей используемой памяти (5 МБ потеряно из-за фрагментации). Общее время (истекло). 0 378 кол., 0 пар 0,41 с 0,43 с 0,0011 с 0,0024 с Gen 1 9 кол., 0 пар 0,36 с 0,37 с 0,0409 с 0,1723 с Время INIT 0,00 с (истекшее значение 0) Время MUT 0,28 с (прошедшее время 0,60 с) Время GC 0,77 с (истек 0,80 с) время ВЫХОДА 0,00 с (истекшее 0,02 с) общее время 1,05 с (истекшее 1,42 с) % время GC 73,1% (истекло 56,4%) Скорость выделения 787 471 957 байт / мин. Производительность 26,9% от общего числа пользователей, 19,8% Всего прошло
Несмотря на то, что программа довольно быстрая (в конце концов, 1 с), объем памяти в 210 МБ весьма ощутим. Кроме того, необходимая память растет в квадрате, для ограничения в 20000 потребуется около 800 МБ, для 20000 - около 1,9 ГБ.
Вариант ST
$ .\ST.exe +RTS -s > $null
300 728 400 байт, выделенных в куче
89 696 288 байт, скопированных во время GC
Максимальная резидентность 13 628 272 байта (10 выборок)
Максимальный спад 292 972 байта
38 МБ общей используемой памяти (0 МБ потеряно из-за фрагментации)
Общее время (прошедшее) Средняя пауза Макс пауза
Генерал 0 565 строк, 0 пар 0,14 с 0,14 с 0,0002 с 0,0008 с
Gen 1 10 colls, 0 par 0.09s 0.08s 0.0076s 0.0223s
Время INIT 0.00s (прошло 0.00s)
Время MUT 0,11 с (истекшее время 0,16 с)
Время GC 0,23 с (прошедшее 0,21 с)
Время выхода 0,00 с (истекшее значение 0,00 с)
Общее время 0,34 с (прошло 0,38 с)
% Времени GC 68,2% (истекло 56,6%)
Скорость выделения 2 749 516 800 байт в секунду MUT
Производительность 31,8% от общего числа пользователей, 28,9% от общего числа прошедших
Всего 38 МБ, что составляет ~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
237 323 392 байта выделено в куче
63 304 856 байт скопировано во время GC
Максимальная резидентность 13 628 276 байт (7 выборок)
138 636 байт, максимальный отстой
34 МБ общей используемой памяти (0 МБ потеряно из-за фрагментации)
Общее время (прошедшее) Средняя пауза Макс пауза
Gen 0 447 colls, 0 par 0.12s 0.09s 0.0002s 0.0008s
Gen 1 7 colls, 0 par 0,05 с 0,06 с 0,0087 с 0,0224 с
Время INIT 0.00s (прошло 0.00s)
Время MUT 0,11 с (истекшее время 0,18 с)
Время GC 0,17 с (истекшее время 0,16 с)
Время выхода 0,00 с (истекшее значение 0,00 с)
Общее время 0,30 с (прошло 0,34 с)
% Времени GC 57,9% (истек 45,9%)
Скорость выделения 2 169 813 869 байт в секунду MUT
Производительность 42,1% от общего числа пользователей, 36,9% от общего количества прошедших Почему он не компилируется?
- Почему он не компилируется? Как правильно извлечь запись?
В некотором смысле, вы извлекаете правильно (см. Выше, это почти тот же код, который вы использовали), но предполагаемый тип для update неправильно, так как вы используете не правильно. Например update должен работать в ST монада, и поэтому вы бы использовали его с mapM не map, Кроме того, есть некоторые другие вещи, например, вы определяете doUpdate но никогда не используйте это.