在此编程问题中,输入是一个n\xc3\x97m整数矩阵。通常,n\xe2\x89\x88 10 5和m\xe2\x89\x88 10。官方解决方案(1606D,教程)非常必要:它涉及一些矩阵操作、预计算和聚合。为了好玩,我把它当作 STUArray 实现练习。
我已经设法使用 STUArray 来实现它,但该程序仍然占用比允许的更多的内存(256MB)。即使在本地运行,最大驻留集大小也>400 MB。在分析中,从标准输入读取似乎占据了内存占用的主导地位:
\n\n函数readv和readv.readInt负责解析整数并将它们保存到 2D 列表中,大约占用 50-70 MB,而不是大约 16 MB = (10 6 个整数) \xc3\x97 (每个整数 8 个字节 + 每个链接 8 个字节) 。
我是否希望总内存低于 256 MB?我已经在使用Text包进行输入。也许我应该完全避免列表并直接将整数从标准输入读取到数组。我们怎样才能做到这一点?或者,问题出在其他地方吗?
{-# OPTIONS_GHC -O2 #-}\nmodule CF1606D where\nimport qualified Data.Text as …Run Code Online (Sandbox Code Playgroud) Run Code Online (Sandbox Code Playgroud)type Traversal' a b = forall f . Applicative f => (b -> f b) -> (a -> f a) type Lens' a b = forall f . Functor f => (b -> f b) -> (a -> f a)请注意,Lens' 和 Traversal' 之间的唯一区别是类型类约束。“镜头”具有函子约束,“遍历”具有应用约束。这意味着任何 Lens' 也自动成为有效的 Traversal'(因为 Functor 是 Applicative 的超类)。
我只是不遵循这里的逻辑顺序。我们知道每个Applicative都是一个Functor。由此看来,如果有的话,难道不应该得出每个Traversal'都是 a 吗Lens'?然而,本教程得出了相反的结论。
我对编程问题的两次提交仅在一个表达式上有所不同(其中anchors是一个非空列表,(getIntegrals n)是一个状态单子):
提交1.replicateM (length anchors - 1) (getIntegrals n)
提交 2 .sequenceA $ const (getIntegrals n) <$> tail anchors
我想,这两个表达式的等价性在编译时本身应该很容易看出。然而,相对而言,速度sequenceA较慢,更重要的是,占用 >10 倍的内存:
| 代码 | 时间 | 记忆 |
|---|---|---|
| 复制M一 | 732 毫秒 | 22200 KB |
| 序列A一 | 1435 毫秒 | 262100 KB |
(第二个条目出现“测试 4 超出内存限制”错误,因此情况可能更糟)。
为什么会这样呢?
预测哪些优化是自动的、哪些不是自动的变得非常困难!
编辑:按照建议,粘贴下面的提交 1代码。在这个交互问题中,“服务器”有一个大小为 的隐藏树n。我们的代码的工作是通过最少数量的 形式的查询来找出该树? k。宽松地说,服务器的响应是树的邻接距离矩阵中? k节点对应的行。我们的选择是:最初,然后从 获得一堆节点。kk1getAnchors
{-# LANGUAGE Safe #-}
{-# OPTIONS_GHC -O2 #-} …Run Code Online (Sandbox Code Playgroud) 我如何理解该声明return 1 getLine?它通过了类型检查,并且看起来与1. getLine和如何return相互“抵消”?这对我来说根本没有意义。
Prelude> :t return 1
return 1 :: (Monad m, Num a) => m a
Prelude> :t return 1 getLine -- why is it not a type error?
return 1 getLine :: Num t => t
Prelude> return 1 getLine
1 -- whatever happened to getLine?
Run Code Online (Sandbox Code Playgroud)
另外,为什么最终产品是“纯”的,即使它涉及一个getLine?
给定三个已排序的数组,我需要m从它们中挑选出总和最小的元素。一个额外的限制是它们中的至少r一个必须来自前两个。这是我的尝试:
solve :: [Int]->[Int]->[Int]->Int->Int->Int
solve xs ys zs m r = mini [ (xs'!!i) + (ys'!!j) + (zs'!!k) |
i <- [max' (len ys - m) .. len xs],
j <- [max' (r-i) .. len ys],
k <- [max' (m-i-j) .. len zs],
i+j+k == m,
i+j>=r
] where
mini ws = if null ws then (-1) else minimum ws
[xs',ys',zs'] = map (scanl (+) 0) [xs, ys, zs]
max' x = max x 0
len …Run Code Online (Sandbox Code Playgroud) 考虑这个关于和 的玩具练习:我们需要根据一组预定义的规则过滤数据包列表。我们还需要根据另一组规则记录一些数据包。现在考虑两个增强功能:WriterWriterT
WriterT w IO)我已经实现了 1,但我坚持将其扩展为 2。首先,下面是 1 的代码。该merge函数处理当前数据包,但将潜在的日志条目传递到下一步,该步骤将决定是否打印它或合并它:
import Control.Monad
import Data.List
import Control.Monad.Writer
type Packet = Int
data Log = Log {
packet :: Packet,
acceptance :: Bool,
bulk :: Int
} deriving Show
instance Eq Log where
(==) a b = packet a == packet b
incr :: Log -> Log
incr x = x {bulk = 1 + bulk x}
shouldAccept :: …Run Code Online (Sandbox Code Playgroud) haskell ×6
monads ×3
arrays ×2
performance ×2
applicative ×1
functor ×1
haskell-lens ×1
iteration ×1
list ×1
memory ×1
optimization ×1
return ×1
stdin ×1
sum ×1