如何优化列表过滤

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]是...（多少）的插入和删除更快相比，一个普通大小均衡地图实现”。