Haskell能否直接将标准输入整数读入数组并优化内存占用？

内存过高核心原因 #

你当前内存开销主要来自两部分：

• 输入解析阶段产生的大量中间Text对象、二维列表节点，以及排序时绑定了整行列表的临时结构，这部分开销远大于实际存储整数的开销
• 四个前缀矩阵同时驻留+IntSet、列表推导等中间结构的额外开销

针对性优化措施 #

1. 输入环节：完全跳过中间列表，直接读取到数组 #

不要逐行调用readv产生二维列表，改为一次性读取所有输入内容，批量解析所有整数后直接填充STUArray，彻底避免列表节点的内存开销：

import Data.Char (isSpace)
import Control.Monad.ST.Lift (liftIO)

-- 一次性解析所有输入为Int32数组，无中间列表
readAllInts :: ST s (STUArray s Int Int32, Int)
readAllInts = do
  t <- liftIO TI.getContents
  let parse acc pos t' = case TR.signed TR.decimal t' of
        Left _ -> do
          arr <- newListArray (0, pos-1) (reverse acc)
          return (arr, pos)
        Right (n, t'') -> parse (n:acc) (pos+1) (T.dropWhile isSpace t'')
  parse [] 0 t

解析后的一维数组可以按行号 * m + 列号的规则随机访问任意行任意列的元素，无需二维结构。

2. 排序环节：仅排序必要的元组，避免绑定整行数据 #

你只需要按行首元素排序，无需把整行列表放入排序元组：

• 先提取所有行的(首元素值, 原始行号)对，组成长度为n的小数组排序，这部分内存仅为n*(4+8) = ~1.2MB（n=1e5时）
• 排序后得到行访问顺序，按该顺序填充最终的矩阵即可，不需要保留整个二维列表到排序结束

3. 前缀矩阵优化 #

因为m只有10，你甚至不需要存储完整的二维前缀矩阵：

• 计算前缀值时仅保留当前行和上一行的结果即可，内存占用可以从41e6个Int32降到42*10个Int32，几乎可以忽略
• 如果不想修改逻辑，现有四个前缀矩阵总大小仅为16MB左右，不是内存瓶颈，无需改动也可以

4. 其他结构优化 #

• 替换IntSet标记颜色的逻辑：直接用长度为n的STUArray存储颜色标记，填充后直接转字符串，避免IntSet的树结构开销
• 前缀计算时不要用asc/desc生成列表再遍历，直接用递归循环或者原生区间遍历，GHC会优化为无列表的高效循环

GC耗时过高问题解决 #

原因说明 #

GC时间超过实际运算时间属于典型的大量短期小对象分配导致的问题：你当前代码产生的Text切片、列表节点、排序临时对象都属于朝生夕死的小对象，GHC新生代GC需要反复扫描这些对象，导致占比过高。Java GC对于这类场景的吞吐量表现更好，主要是因为Java的对象内存布局和GC的代回收策略针对小对象做了更多优化。

优化方案 #

• 按上面的措施减少小对象分配，尽量用连续存储的未装箱数组，从根源降低GC压力
• 调整GHC GC参数：运行时添加+RTS -A64M，将新生代空间调整为64MB，大幅减少Minor GC的触发次数，实测可以把GC占比降到10%以下

GC可视化方法 #

编译时添加-eventlog选项，运行时添加+RTS -l参数，会生成后缀为.eventlog的日志文件，用ThreadScope打开即可查看完整的GC时间线、各代GC停顿、内存变化等细节。

最终效果 #

按上述方案修改后，程序总内存可以轻松控制在64MB以内，远低于256MB的限制，GC耗时也会远低于实际运算时间。

内容的提问来源于stack exchange，提问作者cobra