为什么头尾模式比索引匹配快得多？

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