快速統計列表中的已知元素

我正在嘗試爲其中一個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）

來源

2013-11-10 ivan_a

您遇到的一個問題是您正在查找您的STRef s列表，這意味着您必須遍歷每個查找和修改的O(n)步驟。這可以通過使用諸如Data.Map.Map之類的具有O(log(n))查找和修改時間的東西來緩解。

您還可以在ST monad中使用可變的Array或Vector代替O(1)查找/修改時間。這可能是最快的方法。

來源

2013-11-10 01:26:10

我試圖使用MVectors。它確實將我其他測試案例的時間提高了30％，但仍然不夠快。 –

它工作。我只是使用未分析的字符串作爲Map鍵，如「0」「1」..「99」。它使整件事運行速度提高了7倍。 –

哦，我甚至沒有想到！字符串幾乎總是會成爲瓶頸。如果你想快速解析，看看'attringarsec' over'bytestring'。 –

這可以通過使用accumArray從Data.Array作爲一個單行來完成。類似accumArray (+) 0 (0,99) . zip values $ repeat 1其中values是輸入。

它似乎仍然不夠快，這有點令人煩惱。對於它所做的事情，accumArray或多或少是儘可能高效的。在我的系統上測試顯示，即使沒有編譯它，處理1,000,000個輸入值的時間大約爲1秒，並且該時間由生成隨機輸入所支配。這與測試網站上的5秒相差甚遠。我不得不知道系統是多麼的過載。

來源

2013-11-10 02:32:06 Carl

快速統計列表中的已知元素

回答

相關問題