2

我正在尝试为其中一个 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

此代码有效，但速度不够快，无法通过最后一个测试用例。有人可以建议对其进行改进吗？（问题链接）

4

2 回答 2

6

accumArray这可以使用from以单行方式完成Data.Array。比如输入accumArray (+) 0 (0,99) . zip values $ repeat 1在哪里values。

它似乎仍然不够快，这有点令人烦恼。accumArray它的工作或多或少尽可能高效。在我的系统上进行的测试表明，处理 1,000,000 个输入值的时间约为 1 秒，即使没有编译它，而且该时间主要由生成随机输入决定。这与测试站点上的 5 秒相差甚远。我不得不怀疑该系统的过载程度。

于 2013-11-10T02:32:06.290 回答
3

您遇到的一个问题是您正在STRef列表中查找您的 s，这意味着您必须遍历O(n)每个查找和修改的步骤。Data.Map.Map这可以通过使用具有O(log(n))查找和修改时间的东西来缓解。

您还可以在monad中使用可变的Array或Vector用于O(1)查找/修改时间。ST这可能是最快的方法。

于 2013-11-10T01:26:10.990 回答