如何優化列表過濾

Question

要學習Haskell我一直在解決編程挑戰。在嘗試解決在Hackerrank中發現的一個過濾千位元素列表中的元素的問題時，我一直無法通過時間測試。

的問題陳述是：從元素列表過濾那些出現次數大於ķ倍，並在其出現的順序打印出來。

到目前爲止，我已經來最好的是這樣的代碼：

import qualified Data.ByteString.Char8 as BSC 
import Data.Maybe (fromJust) 
import Data.List (intercalate, elemIndices, foldl') 
import qualified Data.Set as S 

-- Improved version of nub 
nub' :: (Ord a) => [a] -> [a] 
nub' = go S.empty 
    where go _ [] = [] 
     go s (x:xs) | S.member x s = go s xs 
        | otherwise = x : go (S.insert x s) xs 

-- Extract Int from ByteString  
getIntFromBS :: BSC.ByteString -> Int 
getIntFromBS = fst . fromJust . BSC.readInt 

{- 
    Parse read file: 

    a k1 
    n1 n2 n3 n4 ... 
    c k2 
    m1 m2 m3 m4 ... 

    into appropriate format: 

    [(k1, [n1,n2,n3,n4]), (k2, [m1,m2,m3,m4])] 
-} 
createGroups :: [BSC.ByteString] -> [(Int, [Int])] 
createGroups [] = [] 
createGroups (p:v:xs) = 
    let val = getIntFromBS $ last $ BSC.split ' ' p 
     grp = foldr (\x acc -> getIntFromBS x : acc) [] $ BSC.split ' ' v 
    in (val, grp) : createGroups xs 

solve :: (Int, [Int]) -> String 
solve (k, v) = intercalate " " $ if null res then ["-1"] else res 
    where 
     go n acc = 
      if length (elemIndices n v) > k 
       then show n : acc 
       else   acc 
     res = foldr go [] (nub' v) 

fullSolve :: [BSC.ByteString] -> [String] 
fullSolve xs = foldl' (\acc tupla -> acC++ [solve tupla]) [] $ createGroups xs 

main = do 
    BSC.getContents >>= mapM_ putStrLn . fullSolve . drop 1 . BSC.lines 

我想知道我在哪裏可以改進此代碼。我已經嘗試了很多使用地圖，向量，解析的變體，並且不從文件解析讀取的字符串到Int，但顯示的代碼是我擁有的最好的代碼。

Answer 1

儘管在開始時我曾嘗試使用Data.Map，但它缺少關於使用摺疊與地圖的註釋中指出的優化，並且也缺少所需的輸出順序（按出現順序） 。最終的解決方案如下：

{-# OPTIONS_GHC -O2 #-} 
import Control.Monad (liftM, replicateM_) 
import Data.Maybe (fromJust) 
import Data.List (foldl', sort, unwords) 
import qualified Data.Map.Strict as M 
import qualified Data.ByteString.Char8 as BSC 

getIntFromBS :: BSC.ByteString -> Int 
getIntFromBS = fst.fromJust.BSC.readInt 

solve :: Int -> [Int] -> String 
solve k = unwords . map snd . sort . map finalPair . filter hasHighFreq . M.toList . foldl' insMap M.empty . zip [0..] 
    where 
     f _ _ (i, old_value) = (i, old_value + 1) 
     insMap m' (i, x) = M.insertWithKey f x (i,1) m' 
     hasHighFreq (_, (_, freq)) = freq >= k 
     finalPair (val, (i, freq)) = (i, show val) 

main = do 
    n <- liftM getIntFromBS BSC.getLine 
    replicateM_ n $ do 
     [_, k] <- liftM (map getIntFromBS . BSC.words) BSC.getLine 
     vals <- liftM (map getIntFromBS . BSC.words) BSC.getLine 
     let res = solve k vals 
     putStrLn (if null res then "-1" else res) 

Answer 2

如果我必須解決這個問題，我可能會先嚐試使用Data.Map.Strict隱藏在一個Control.Monad.State.Strict單子轉換的操作（O（日誌ñ）修改）。

import Data.Map.Strict 
import Control.Monad.State.Strict 

type SIO x = StateT (Map String Int) IO x 

incCount :: String -> Int -> Int -> Int 
incCount _ _ old_val = 1 + old_val 

incAndGetCount :: String -> SIO Int 
incAndGetCount s = fmap unMaybe $ state $ insertLookupWithKey incCount s 1 
    where unMaybe (Just x) = x + 1 
      unMaybe Nothing = 1 

processKey :: String -> SIO() 
processKey s = do 
    ct <- incAndGetCount s 
    if ct == 5 then lift (putStrLn s) else return() 

process :: [String] -> IO() 
process list = evalStateT (mapM_ processKey list) empty 

雖然我覺得這個代碼是更優雅我不知道它是否是沒有實際看到的測試數據的速度更快的方式。在任何情況下，這相當於一個命令循環，它將字符串放入一個字典中，檢索它迄今爲止所看到的次數，然後如果該數字是5，則將該字符串打印到標準輸出。

當然，您需要將其與適當的main方法結合使用。

Answer 3

編輯：哎呀，這是錯誤的。所產生的訂單是「如發現的」，但應該是「如最初列表中所見」。這可以通過索引和排序來調整......不幸的是，這意味着它不再具有生產力。

可以使該功能更有效率，避免任何需要建立索引和排序也與

import qualified Data.IntMap.Strict as M 
import Data.List 

-- mapAccumL :: (acc -> x -> (acc, y)) -> acc -> [x] -> (acc, [y]) 

solve :: Int -> [Int] -> [Int] 
solve k ns = concat . snd $ mapAccumL g M.empty ns 
    where 
    g m n = case u of   -- for each n in ns, with updating m, 
       Nothing -> (M.insert n 1 m, [n | k==1]) 
       Just c -> (m2, [n | c==k-1]) 
    where 
     (u,m2) = M.updateLookupWithKey (\n c-> Just (c+1)) n m 

只要ķ元素的個例輸入列表中遇到，我們可以生產它。最終的頻率圖將被忽略。

最好讓你的功能更專注。在製作了Int的列表後，您可以將其傳遞給unwords . map show或您有什麼。

Data.IntMap.Strict說：「...基準測試表明[IntMap]是...（多少）的插入和刪除更快相比，一個普通大小均衡地圖實現」。