Haskell求解Codeforces 285C超时（Test#7），求优化方案

问题描述 #

我在解决Codeforces题目285C时，提交的Haskell代码在测试用例#7触发了TIME_LIMIT_EXCEEDED错误（时间限制1000ms）。以下是相关信息：

原代码 #

import Data.List
import Data.Int

(|>) a b = b a

main = do
    s1 <- getLine
    s2 <- getLine
    let n = s1 |> (read :: String -> Int64)
        a = s2 |> words |> map (read :: String -> Int64)
        r = sort a |> zipWith (\x y -> abs (x - y)) [1 .. n] |> sum
    print r

测试输出 #

Test: #7, time: 1000 ms., memory: 98516 KB, exit code: -1, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED

部分输入 #

300000
299996 65 64 63 62 61 60 59 58 70 53 79 88 97 106 115 124 133 142 45 151 160 169 178 187 196 ...

超时原因分析 #

1. 输入读取效率低：用getLine结合String处理30万级别的输入时，String的字符链表结构会带来大量内存开销和处理延迟，远不如二进制字节串高效。
2. 不必要的列表生成：[1 .. n]会生成一个包含30万个元素的完整列表，额外占用内存的同时，zipWith需要遍历两个列表，增加了遍历次数。
3. 惰性求值的性能损耗：原代码中sum等函数依赖惰性列表，会产生大量未求值的thunk，导致内存占用飙升，拖慢计算速度。

优化方案 #

优化后的代码 #

import Data.List
import Data.Int
import Data.ByteString.Char8 (readInt, words, getContents)
import Prelude hiding (words, getContents)
import Data.Foldable (foldl')

main = do
    input <- getContents
    let (n:rest) = map (fromIntegral . fst . (\Just x -> x) . readInt) $ words input
        sortedA = sort rest
        -- 用foldl'严格求值，同时跟踪索引，避免生成额外列表
        total = snd $ foldl' (\(idx, acc) num -> (idx + 1, acc + abs (num - idx))) (1, 0) sortedA
    print total

优化点说明 #

1. 高效输入处理：改用Data.ByteString.Char8的getContents和words读取输入，二进制字节串处理大文本的速度远快于String，同时readInt比read更高效。
2. 避免冗余列表生成：通过foldl'在遍历排序后的数组时直接维护索引，无需生成[1..n]列表，减少内存占用和遍历次数。
3. 严格求值：使用foldl'（严格版foldl）强制每一步都立即求值，避免惰性求值产生的thunk堆积，降低内存开销并提升计算速度。

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