Haskell线性时间在线算法

Question

Haskell线性时间在线算法

6

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

按照Tel的建议，我简化了我的示例：

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

- גלעד ברקן

2

在Haskell中编写常数时间、常数空间的在线算法是非常可能的。不过，用一个更简单的例子来解释这些机制会更容易些。你能否创建一个简单的问题实例？或者将问题移至代码审查板块。 - J. Abrahamson

@tel 谢谢您的建议。我尝试简化了我的例子。现在看起来怎么样？ - גלעד ברקן

1

很明显，上述代码(a)是尾递归的，它建立了一个累加器，只有在消耗完所有输入后才会被传递，并且(b)计算了一个左嵌套的++应用程序塔，这会导致速度变慢，因为++需要与其第一个参数的长度成线性关系的时间。尝试让您的代码尽可能快地提供尽可能大的输入前缀，将递归调用放在++右侧。 - pigworker

一个尾递归的列表函数必须在输出任何内容之前消耗所有输入。你所经历的缓慢可能来自于左嵌套的 (++) 链。 - luqui

@luqui 谢谢，现在它按预期工作了！我已经习惯了编写“尾递归”形式，但没有理解它的影响。谢谢！ - גלעד ברקן

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- luqui · Accepted Answer

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)时间，并且与我们正在做的事情无关（将每个元素加1并保留顺序与翻转有什么关系？）。

在像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中的尾递归有些直觉。对于你的示例，建议删除尾递归并以类似我们最终的“go”的朴素风格重写，使用我希望从本文中提供的直觉，“尽可能快地产生尽可能大的输入前缀”（请注意，即使还有一些工作要做来计算xs，返回x:xs也会立即产生x - 这是惰性的（非）行动）。