是(反向,反向)有效吗？

Question

很多时候,我看到在列表头部运行的函数,例如:

trimHead ('\n':xs) = xs
trimHead xs        = xs

然后我看到了定义:

trimTail = reverse . trimHead . reverse

然后我看到:

trimBoth = trimHead . trimTail

他们是干净的,但trimTail和trimBoth效率？有没有更好的办法？

Answer 1

考虑这种替代实施

trimTail2 [] = []
trimTail2 ['\n'] = []
trimTail2 (x:xs) = x : trimTail2 xs

trimBoth2 = trimHead . trimTail2

这很容易确认trimTail,并trimBoth要求整个列表进行评估,而trimTail2和trimBoth2只需要评估名单之多.

*Main> head $ trimTail ('h':undefined)
*** Exception: Prelude.undefined
*Main> head $ trimBoth ('h':undefined)
*** Exception: Prelude.undefined
*Main> head $ trimTail2 ('h':undefined)
'h'
*Main> head $ trimBoth2 ('h':undefined)
'h'

这意味着如果不需要整个结果,您的版本效率会降低.

Answer 2

从某种意义上讲,流式传输是不可能的,因为需要对整个列表进行评估以获得单个元素.但是更好的解决方案很难,因为您需要评估列表的其余部分以了解是否要修剪换行符.一种稍微有效的方法是展望是否要修剪换行并做出适当的反应:

trimTail, trimHead, trimBoth :: String -> String
trimTail ('\n':xs) | all (=='\n') xs = ""
trimTail (x:xs)                      = x : trimTail xs

trimHead = dropWhile (=='\n')

trimBoth = trimTail . trimHead

如果要修剪换行符,上面的解决方案只评估字符串中所需的数量.一种更好的方法是结合知识,即下一个n个字符不被修剪.实现这一点留给读者练习.

更好(和更短)的写法trimTail是这样的(通过rotsor):

trimTail = foldr step [] where
  step '\n' [] = []
  step x xs = x:xs

一般来说,尽量避免reverse.通常有更好的方法来解决问题.

Answer 3

假设要评估整个列表(如果你不需要整个列表,为什么要修改结尾？),它的效率大约是你从不可变列表中获得的效率的一半,但它具有相同的渐近复杂度O (N).

新名单至少要求:

1. 你必须找到结束:n指针遍历.
2. 你必须修改结尾,从而指出结尾等等:用现有数据加上新指针.

reverse . trimHead . reverse 执行大约两次:

1. 第一个reverse执行n指针遍历和n cons.
2. trimHead 可能执行1次指针遍历.
3. 第二个reverse执行n指针遍历和n cons.

这值得担心吗？在某些情况下,也许吧.代码是否太慢,这是否被称为很多？在其他人,也许不是.基准!实现reverse很好,易于理解,这很重要.

有一个相当自然的递归逐步列表解决方案,它只会评估所消耗的输出量,所以在你不知道是否需要整个字符串的情况下,你可以节省一些评价.