爲什麼頭尾模式比索引匹配快得多？

Question

我今天正在研究一個HackerRank問題，最初是用索引編寫的，而且它對於大多數測試用例來說都非常慢，因爲它們非常龐大。然後我決定將它切換到head:tail模式匹配，它只是放大。這種差別絕對是晝夜，但我無法弄清楚它是如何改變效率的。下面是引用的代碼，如果它是在與索引的所有有用的

最有效的嘗試

count :: Eq a => Integral b => a -> [a] -> b 
count e [] = 0 
count e (a:xs) = (count e xs +) $ if a == e then 1 else 0 

fullCheck :: String -> Bool 
fullCheck a = prefixCheck 0 (0,0,0,0) a (length a) && (count 'R' a == count 'G' a) && (count 'Y' a == count 'B' a) 

prefixCheck :: Int -> (Int, Int, Int, Int) -> String -> Int -> Bool 
prefixCheck n (r',g',y',b') s l 
    | n == l = True 
    | otherwise = 
    ((<= 1) $ abs $ r - g) && ((<= 1) $ abs $ y - b) 
    && prefixCheck (n+1) (r,g,y,b) s l 
     where c = s !! n 
      r = if c == 'R' then r' + 1 else r' 
      g = if c == 'G' then g' + 1 else g' 
      y = if c == 'Y' then y' + 1 else y' 
      b = if c == 'B' then b' + 1 else b' 

run :: Int -> IO() 
run 0 = putStr "" 
run n = do 
    a <- getLine 
    print $ fullCheck a 
    run $ n - 1 

main :: IO() 
main = do 
    b <- getLine 
    run $ read b 

head:tail模式匹配嘗試

count :: Eq a => Integral b => a -> [a] -> b 
count e [] = 0 
count e (a:xs) = (count e xs +) $ if a == e then 1 else 0 

fullCheck :: String -> Bool 
fullCheck a = prefixCheck (0,0,0,0) a && (count 'R' a == count 'G' a) && (count 'Y' a == count 'B' a) 

prefixCheck :: (Int, Int, Int, Int) -> String -> Bool 
prefixCheck (r,g,y,b) [] = r == g && y == b 
prefixCheck (r',g',y',b') (h:s) = ((<= 1) $ abs $ r - g) && ((<= 1) $ abs $ y - b) 
    && prefixCheck (r,g,y,b) s 
     where r = if h == 'R' then r' + 1 else r' 
      g = if h == 'G' then g' + 1 else g' 
      y = if h == 'Y' then y' + 1 else y' 
      b = if h == 'B' then b' + 1 else b' 

run :: Int -> IO() 
run 0 = putStr "" 
run n = do 
    a <- getLine 
    print $ fullCheck a 
    run $ n - 1 

main :: IO() 
main = do 
    b <- getLine 
    run $ read b 

僅供參考爲好，問題是

給你一系列N四種顏色的球：紅色，綠色，y橢圓形和藍色。當且僅當滿足以下所有條件時，該序列才充滿色彩：

• 有和綠球一樣多的紅球。
• 藍球有很多黃球。在序列的每個前綴的紅球和綠球數之間
• 區別是在序列的每個前綴黃球和藍色球數之間至多爲1
• 差爲1

當一個字符串的前綴是從開始的任意字符串到m其中m小於字符串

Answer 1

的大小你已經得到的，爲什麼名單索引線進行評論的答案。但是，如果您對the Hackerrank problem your referring to的Haskell樣式解決方案感興趣，甚至不需要頭尾模式匹配。更高性能的解決方案可與右摺疊來完成：

import Control.Applicative ((<$>)) 
import Control.Monad (replicateM_) 

solve :: String -> Bool 
solve s = foldr go (\r g y b -> r == g && y == b) s 0 0 0 0 
    where 
    go x run r g y b 
    | 1 < abs (r - g) || 1 < abs (y - b) = False 
    | x == 'R' = run (r + 1) g y b 
    | x == 'G' = run r (g + 1) y b 
    | x == 'Y' = run r g (y + 1) b 
    | x == 'B' = run r g y (b + 1) 

main :: IO() 
main = do 
    n <- read <$> getLine 
    replicateM_ n $ getLine >>= print . solve