haskell - 快速计算列表中的已知元素

Question

我正在尝试为 Hackerrank 问题之一编写解决方案。挑战是对列表中的元素进行计数，元素从 0 到 99 不等，因此可以在线性时间内对它们进行计数。这是我得到的:

{-# LANGUAGE BangPatterns #-}
{-# OPTIONS_GHC -O3 #-}

module Main where

import Data.STRef
import Data.Foldable
import Control.Monad
import Control.Monad.ST

main = do

 line1 <- getLine
 line2 <- getLine

 let
    !ns = map read $ words line2 :: [Int]

    res = runST $ do

        refs <- forM [0..99] $ \i ->
            newSTRef (0 :: Int) 

        traverse_ (\x -> modifySTRef' (refs !! x) (+1) ) ns

        mapM (\ref -> readSTRef ref) refs

 putStrLn . unwords . map show $ res

这段代码可以工作，但速度不够快，无法通过最后一个测试用例。有人可以建议对其进行改进吗？ (link to the problem)

Answer 1

这可以通过使用 accumArray 来完成来自Data.Array 。类似 accumArray (+) 0 (0,99) . zip values $ repeat 1哪里values是输入。

它似乎仍然不够快，这有点令人烦恼。 accumArray或多或少地尽可能高效地完成它所做的事情。对我的系统进行的测试表明，即使不进行编译，处理 1,000,000 个输入值的时间也约为 1 秒，并且该时间主要由生成随机输入决定。这与测试站点上的 5 秒相差甚远。我不得不想知道该系统的过载程度如何。