Haskell：這個代碼可以優化嗎？

Question

我有以下代碼。我想知道是否有任何方法可以優化，以便運行得更快。

我想用SegmentTree來解決它，但我對Haskell並不熟悉，這就是爲什麼我採用以下列表（非樹）方法。

-- 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

預先計算列表中每個前綴的頻率。爲了計算子列表的頻率，減去在子列表兩端結束的兩個前綴的頻率。這會將每個查詢的成本從O（n^2）降低到O（n）。要計算頻率，請使用計數排序。這會將預計算的成本從O（n^2）降低到O（n log n）。