목록의 필터링을 최적화하는 방법

Question

하스켈을 배우려면 프로그래밍 문제를 해결해 왔습니다. Hackerrank에서 발견 된 한 가지 문제를 해결하기 위해 1000 개 요소 목록의 요소를 필터링하는 동안 시간 테스트를 통과하지 못했습니다.

문제 문은입니다 : 요소의 목록 이상 K 번 표시 자들을 필터링 및 외관의 순서대로 인쇄에서. 나는이 코드를 개선 할 수있는 알고 싶습니다

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 

:

지금까지 왔어요 가장

이 코드입니다. map, vector, 구문 분석을 사용하여 많은 변종을 시도해 보았습니다. 파일에서 읽은 문자열을 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 (O를 위해 (N) 변경 로그)를 Control.Monad.State.Strict 모나드 변압기와 운영에 숨겨진.

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

편집 : 죄송합니다, 이것은 잘못된 것입니다. 생산 된 주문은 "발견 된 그대로"이지만 "원래 목록에서 처음 본 것"이어야합니다. 이것은 색인 생성 및 정렬을 통해 조정될 수 있습니다 ... 불행히도 이것은 결국 생산성이 떨어지는 것을 의미합니다.

당신은 즉시 요소의 K 번째 인스턴스가 입력 목록에서 우리가 할 수있는 발생으로

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] (훨씬) 빠른 삽입과 삭제에 대한 일반적인 크기 균형 맵 구현에 비해 ... 것을 보여"말한다.