小编cob*_*bra的帖子

Haskell:我可以直接将整数读入数组吗?

编程问题中,输入是一个n\xc3\x97m整数矩阵。通常,n\xe2\x89\x88 10 5m\xe2\x89\x88 10。官方解决方案(1606D,教程)非常必要:它涉及一些矩阵操作、预计算和聚合。为了好玩,我把它当作 STUArray 实现练习。

\n

问题

\n

我已经设法使用 STUArray 来实现它,但该程序仍然占用比允许的更多的内存(256MB)。即使在本地运行,最大驻留集大小也>400 MB。在分析中,从标准输入读取似乎占据了内存占用的主导地位:

\n

剖析

\n

函数readvreadv.readInt负责解析整数并将它们保存到 2D 列表中,大约占用 50-70 MB,而不是大约 16 MB = (10 6 个整数) \xc3\x97 (每个整数 8 个字节 + 每个链接 8 个字节) 。

\n

我是否希望总内存低于 256 MB?我已经在使用Text包进行输入。也许我应该完全避免列表并直接将整数从标准输入读取到数组。我们怎样才能做到这一点?或者,问题出在其他地方吗?

\n

代码

\n
{-# OPTIONS_GHC -O2 #-}\nmodule CF1606D where\nimport qualified Data.Text as …
Run Code Online (Sandbox Code Playgroud)

arrays performance stdin haskell

10
推荐指数
1
解决办法
590
查看次数

每个镜头都是一次穿越……怎么样?

Control.Lens.Tutorial说:

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) 
Run Code Online (Sandbox Code Playgroud)

请注意,Lens' 和 Traversal' 之间的唯一区别是类型类约束。“镜头”具有函子约束,“遍历”具有应用约束。这意味着任何 Lens' 也自动成为有效的 Traversal'(因为 Functor 是 Applicative 的超类)。

我只是不遵循这里的逻辑顺序。我们知道每个Applicative都是一个Functor。由此看来,如果有的话,难道不应该得出每个Traversal'都是 a 吗Lens'?然而,本教程得出了相反的结论。

haskell functor applicative haskell-lens

10
推荐指数
1
解决办法
647
查看次数

为什么replicateM (length xs) m 比sequenceA (fmap (const m) xs) 更高效?

我对编程问题的两次提交仅在一个表达式上有所不同(其中anchors是一个非空列表,(getIntegrals n)是一个状态单子):

提交1replicateM (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)

memory monads optimization performance haskell

7
推荐指数
1
解决办法
226
查看次数

Haskell:之前的返回被之后的单子取消。如何?

我如何理解该声明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

monads haskell type-inference return

6
推荐指数
2
解决办法
212
查看次数

高效迭代 Haskell 中多个数组/列表的前缀

给定三个已排序的数组,我需要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)

arrays iteration haskell sum list

2
推荐指数
1
解决办法
174
查看次数

没有因使用“tell”而产生 (MonadWriter [Log] IO) 的实例

考虑这个关于和 的玩具练习:我们需要根据一组预定义的规则过滤数据包列表。我们还需要根据另一组规则记录一些数据包。现在考虑两个增强功能:WriterWriterT

  1. 如果出现重复的连续数据包(满足记录标准),我们应该只创建 1 个日志条目,并打印重复计数。(目标是教授所谓的“延迟记录”技巧。)
  2. 我们需要为每个日志条目附加时间戳。(即使用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)

monads haskell monad-transformers

1
推荐指数
1
解决办法
122
查看次数