天真的Haskell功能实现比"更智能"的解决方案更快？

Question

所以我是Haskell的新手,我想弄清楚为什么我的天真实现实际上比我认为更智能的解决方案更快.

我正在尝试编写一个函数,给定一个String将返回一个Bool指示String是否使用一个且恰好是一个元音的函数.以下是我天真的实现:

singleVowel :: Maybe String -> Bool
singleVowel Nothing = False
singleVowel (Just s) = singleVowel (Just s) = length (nub $ filter (`elem` "aeiouyAEIOUY") s) == 1

请注意,我过滤掉了元音集中没有的所有元素.然后,我使用该nub函数进行另一次传递,从筛选列表中删除重复项,并查看列表中是否只有1个元音.然后在最坏的情况下,此解决方案将使用O(n)内存和时间,因为它必须为筛选列表分配内存.

现在对于我的另一个解决方案,我决定使用递归并在每次递归调用时传递一个字符,以便在看到当前元音时跟踪当前元音.

singleVowelFaster :: Maybe String -> Bool
singleVowelFaster Nothing = False
singleVowelFaster (Just s) = singleVowelHelper s Nothing

singleVowelHelper :: String -> Maybe Char -> Bool
singleVowelHelper [] Nothing = False
singleVowelHelper [] _ = True
singleVowelHelper (x:xs) Nothing = if x `elem` "aeiouyAEIOUY"
  then singleVowelHelper xs (Just x)
  else singleVowelHelper xs Nothing
singleVowelHelper (x:xs) (Just c) =
  (x `elem` "aeiouyAEIOUY" && c == x) && singleVowelHelper xs (Just c)

但由于一些奇怪的原因,"天真"的实施比"更智能"的解决方案运行得更快.

可能是由于Haskell是懒惰的,所以(xelem "aeiouyAEIOUY" && c == x)没有被评估,所以一旦达到基本情况就会评估所有的thunk,从而导致比'naive'实现更慢？

如果是这种情况,那么为什么会出现这种情况呢？当我将(xelem "aeiouyAEIOUY" && c == x)放入if语句强制评估时,函数的性能是相似的？

我是否也可以说第二个功能O(1)随着O(n)时间的推移有空间使用？

Answer 1

最简单的解决方法是颠倒您第一次&&通话的顺序,==在昂贵的elem支票之前执行便宜的检查.

这将使你的功能运行得更快......但它仍然是不正确的!你基本上断言,在第一个元音之后,所有后面的字符都是完全相同的元音; 你打算做的是断言所有后面的元音都是同一个元音.我会这样写:

(x == c || not (x `elem`vowels)) && singleVowelHelper xs (Just c)

或者,实际上,我会以不同的方式编写整个函数,但上面是使您的实现工作的最简单的更改.这是我要编写的实现,从更通用的基于谓词的函数开始,然后专注于元音:

exactlyOne :: Eq a => (a -> Bool) -> [a] -> Bool
exactlyOne pred [] = False
exactlyOne pred (x:xs)
  |    pred x = not . any pred . filter (/= x) $ xs
  | otherwise = exactlyOne pred xs

exactlyOneVowel :: String -> Bool
exactlyOneVowel = exactlyOne (`elem` "aeiouAEIOU")