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

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

作为参考,问题是

您将获得N4种颜色的球序列:红色,绿色,黄色和蓝色.当且仅当满足以下所有条件时,序列才会充满颜色:

• 绿球和红球一样多.
• 蓝球和黄球一样多.
• 序列的每个前缀中的红球和绿球的数量之差最多为1.
• 序列的每个前缀中的黄球数和蓝球数之间的差异最多为1.

其中字符串的前缀是从开头到mwhere的任何子字符串m小于字符串的大小

Answer 1

您已经在注释中得到了答案,为什么列表索引执行线性.但是,如果您对您所提到的Hackerrank问题的更多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