Haskell线性时间在线算法

Question

如果我误用了标题中的大字,请原谅我; 我不太了解他们,但希望他们描述我的问题.我写了一个精心设计的方案来尝试根据这些要求对字符串进行编码.对于长度为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

Answer 1

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

看看输出中的每个项目如何从深层嵌套的括号中向外运行？这使得它在输入的大小上采用二次时间来获得所有输出.您还会看到前几个项目缓慢产生的行为,当您到达列表末尾时,它会变得越来越快.这种减少解释了这一点

这里的主要性能问题是将新元素附加到列表的末尾,这会占用与要附加的列表大小成比例的时间.更好的方法是在前面进行利弊,这是一个合理的时间操作.这将导致输出反转,因此您需要反转结果.

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