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

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

此代码有效,但速度不够快,无法通过最后一个测试用例.有人可以推荐一项改进吗？(链接到问题)

Answer 1

这可以使用accumArrayfrom 作为单线程来完成Data.Array.喜欢的东西accumArray (+) 0 (0,99) . zip values $ repeat 1哪里values是输入.

它似乎仍然不够快,这有点令人烦恼.accumArray它的作用或多或少尽可能高效.在我的系统上进行测试显示处理1,000,000个输入值的时间约为1秒,即使没有编译也是如此,并且该时间主要是生成随机输入.这与测试网站上的5秒相差甚远.我不得不怀疑这个系统是多么重载.