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