Haskell：このコードを最適化できますか？

Question

私は次のコードを持っています。私はそれがより速く動くように最適化できる方法があるかどうかを知りたい。

私はSegmentTreeを使って解決したいと思っていましたが、私はハスケルに精通していません。そのため、以下のリスト（非ツリー）のアプローチを取ったのです。

-- Program execution begins here 
main :: IO() 
main = do 
    _ <- getLine 
    arr <- map (read :: String -> Integer) . words <$> getLine 
    queryList <- readData 
    let queries = map (read :: String -> Integer) queryList 
    putStrLn "" 
    mapM_ print $ compute queries arr 

-- Construct a sublist 
sublist :: Integer -> Integer -> [Integer] -> [Integer] 
sublist start end list = take (fromInteger end - fromInteger start) . drop (fromInteger start) $ list 

-- Calculate the resulting list 
compute :: [Integer] -> [Integer] -> [Integer] 
compute [_] [_] = [] 
compute [_] [] = [] 
compute [_] (_:_) = [] 
compute [] (_:_) = [] 
compute [] [] = [] 
compute (x1:x2:xs) list = result : compute xs list where 
    result = frequency $ sublist x1 x2 list 

-- Read query list, end at terminating condition 
readData :: IO [String] 
readData = do 
    x <- getLine 
    if x == "0" 
    then return [] 
    else do xs <- readData 
      return (words x ++ xs) 

-- Return count of the most frequent element in a list 
frequency :: [Integer] -> Integer 
frequency list = toInteger (snd $ maximumBy (compare `on` snd) counts) where 
    counts = nub [(element, count) | element <- list, let count = length (filter (element ==) list)] 

ありがとうございました。

Answer 1

リストの各プレフィックスの頻度を事前に計算します。サブリストの頻度を計算するには、サブリストの両端で終了する2つのプレフィックスの頻度を減算します。これにより、各クエリのコストがO（n^2）からO（n）に削減されます。頻度を計算するには、カウントソートを使用します。これにより、O（n^2）からO（n log n）までの事前計算のコストが削減されます。