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

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

作为引用，问题是

You are given a sequence of N balls in 4 colors: red, green, yellow and blue. The sequence is full of colors if and only if all of the following conditions are true:

• There are as many red balls as green balls.
• There are as many yellow balls as blue balls.
• Difference between the number of red balls and green balls in every prefix of the sequence is at most 1.
• Difference between the number of yellow balls and blue balls in every prefix of the sequence is at most 1.

Where a prefix of a string is any substring from the beginning to m where m is less than the size of the string

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