6

如果我用错了标题中的大词，请原谅我；我对他们不太了解，但希望他们能描述我的问题。我编写了一个精心设计的方案来尝试根据这些要求对字符串进行编码。对于长度为 10^4 或更高的字符串，我编写的代码非常慢，我想知道 - 因为它一次处理 200 个块（尽管有时只向前移动一个字符来获取下一个块），可以吗？修改为更快或更线性地输出结果（例如，每处理 200 个字符立即输出结果）。任何有关该优化或其他明显优化的帮助将不胜感激。

根据电话的建议，我简化了我的示例：

encode xs = encode' xs [] where
  encode' []     result = result
  encode' (z:zs) result
    | null test = encode' zs (result ++ [z])
    | otherwise = encode' (drop numZsProcessed zs) (result ++ processed)
   where test = ..some test
         toProcess = take 200 (z:zs)
         processed = ..do something complicated with toProcess
         numZsProcessed = ..number of z's processed
4

1 回答 1

6

Haskell 和尾递归不像其他函数式语言和尾递归那样相处。让我们对一些非常简单的代码进行手动缩减，看看尾递归发生了什么。这是一个尾递归的实现map (1+)。

go [] r = r
go (x:xs) r = go xs (r ++ [1+x])

我们还必须牢记 的定义(++)：

[] ++ ys = ys
(x:xs) ++ ys = x : (xs ++ ys)

现在让我们减少go [1,2,3,4,5] []. 请记住，这[x,y,z]是x:(y:(z:[]))或简称的符号x:y:z:[]。

go [1,2,3,4,5] []
go [2,3,4,5] ([] ++ [2])   -- 2 here is actually the thunk 1+1, but
                           -- for compactness I am reducing earlier
go [3,4,5] (([] ++ [2]) ++ [3])
go [4,5] ((([] ++ [2]) ++ [3]) ++ [4])
go [5] (((([] ++ [2]) ++ [3]) ++ [4]) ++ [5])
go [] ((((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6])
(((([] ++ [2]) ++ [3]) ++ [4]) ++ [5]) ++ [6]
((([2] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(((2:([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
((2:(([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
(2:((([] ++ [3]) ++ [4]) ++ [5]) ++ [6]
2:(((([] ++ [3]) ++ [4]) ++ [5]) ++ [6])    -- first observable output
2:((([3] ++ [4]) ++ [5]) ++ [6])
2:((3:([] ++ [4]) ++ [5]) ++ [6])
2:(3:(([] ++ [4]) ++ [5]) ++ [6])
2:3:((([] ++ [4]) ++ [5]) ++ [6])           -- second observable output
2:3:(([4] ++ [5]) ++ [6])
2:3:(4:([] ++ [5]) ++ [6])
2:3:4:(([] ++ [5]) ++ [6])                  -- third observable output
2:3:4:([5] ++ [6])
2:3:4:5:([] ++ [6])                         -- fourth observable output
2:3:4:5:6:[]                                -- final output

看看输出中的每个项目需要如何从深度嵌套的一系列括号中向外工作？这导致它需要输入大小的二次时间才能获得所有输出。您还将看到前几个项目产生缓慢的行为，并且当您到达列表末尾时它变得越来越快。这种减少解释了这一点。

这里的主要性能问题是将新元素附加到列表的末尾，这所花费的时间与您要附加到的列表的大小成正比。更好的方法是在前面使用cons ，这是一个恒定时间的操作。这将导致输出反转，因此您需要反转结果。

go [] r = reverse r
go (x:xs) r = go xs ((1+x):r)

reverse xs = rev xs []      -- roughly from the report prelude
rev [] r = r
rev (x:xs) r = rev xs (x:r)

而且，让我们减少：

go [1,2,3,4,5] []
go [2,3,4,5] [2]
go [3,4,5] [3,2]
go [4,5] [4,3,2]
go [5] [5,4,3,2]
go [] [6,5,4,3,2]
reverse [6,5,4,3,2]
rev [6,5,4,3,2] []
rev [5,4,3,2] [6]
rev [4,3,2] [5,6]
rev [3,2] [4,5,6]
rev [2] [3,4,5,6]
rev [] [2,3,4,5,6]
[2,3,4,5,6]          -- first and all observable output!

所以这显然比第一个版本少。这是 Scheme 和 ML 等严格语言中使用的样式，因为它具有良好的内存性能。但是，它有一些缺点：

  • 在产生任何输出之前，必须消耗所有输入。事实上，整个计算是在产生任何结果之前执行的。
  • 因此，当给定一个无限列表时，它不会产生任何输出。
  • 它涉及reverse，这需要额外的O(n)时间并且与我们正在做的事情无关（反转与向每个元素添加一个并保持顺序有什么关系？）。

在像 Haskell 这样的惰性语言中，我们可以做得更好。奇怪而美妙的是，我们的做法是写得更天真。

go [] = []
go (x:xs) = (1+x):go xs

并减少：

go [1,2,3,4,5]
2:(go [2,3,4,5])     -- first observable output
2:3:(go [3,4,5])     -- second observable output
2:3:4:(go [4,5])     -- third observable output
2:3:4:5:(go [6])     -- fourth observable output
2:3:4:5:6:(go [])    -- fifth observable output
2:3:4:5:6:[]         -- final output

它需要更少的工作，甚至在查看列表的其余部分之前就开始产生输出，因此它在流计算中具有良好的性能并且可以处理无限输入。并且实现与您希望的一样简单明了。

我希望这能让你对 Haskell 中尾递归的工作方式有一些直觉。对于您的示例，我建议删除尾递归并以类似于我们 final 的朴素风格重写go，使用我希望我从这篇文章中建议的直觉来产生“尽可能大的输入前缀，尽快”（请注意，即使需要做更多的计算工作，x:xs立即返回也会产生- 这就是（非）行动中的懒惰。xxs

于 2013-06-03T17:53:51.223 回答