3

我在 lisp 语言家族中接受过一些培训，现在我正在学习一些 Haskell，以实现我自己的利益。在 lisp 中，函数式风格是可以的，但在少数情况下，命令式风格对于获得良好的性能是必要的，例如

  • 附加

    Append 很慢，因为它必须复制它的第一个参数（有时 x100 与成功摆脱它的版本一样慢）。一种补救方法是将第一个列表的最后一个指针移动到第二个列表的开头，而不是追加。当然，这是一种破坏性的操作。

  • 种类

    快速排序的功能版本创建了许多中间列表，这在某种程度上违背了算法的目的，即尽可能快。AFAIR，在 common lisp 中，sort 是唯一没有函数版本的破坏性函数。

  • 长度

    这在 lisp 中是一项代价高昂的操作，因为必须遍历整个列表才能获得其长度。不必如此，afaik clojure 以对数时间计算列表的长度。解决方案通常是在命令式循环中动态计算长度。

我的问题是，我们如何在 haskell 中处理这些问题？

4

2 回答 2

11

正如 delnan 所说，这些问题与使用错误的数据结构有关，例如当您需要向量时使用链表。

您的特定操作

  • append: cons 是 O(1)，所以我怀疑您指的是分配 cons 单元格、单元格上的模式匹配以及单元格的最终 GC 的行为。除非您优化列表，否则这是不可避免的，这在某些情况下确实会发生。

  • sort：我建议你看看 ST monad，它允许你在纯上下文中使用需要突变的算法。有关示例，请参见vsort实现。

  • 长度：当然，获取链表长度的唯一方法是遍历链表。如果您经常需要长度，请考虑使用 Set、Map 或 Vector - 所有这些都记录了可以在 O(1) 中访问的总大小。

一般来说

  • 研究ST可变性。
  • 为正确的问题使用正确的数据结构。了解 Hackage 提供的结构（向量、数组、哈希图、哈希表、bloomfilter 等）。
于 2013-08-04T18:08:42.140 回答
3

append不是通用的东西。追加到双端队列与追加到 cons 列表不同。破坏性追加与追加复制不同。根据您的标准，您可以针对速度慢、线程安全或简单性进行优化，并且您对“问题”的定义将会改变。

正如 delnan 和 Thomas DuBuisson 提到的，如果您选择正确的数据类型，Haskell 将拥有所有这些选项。

因此，如果您有想要优化的特定算法，可能有一种方法可以将其转换为快速的非破坏性版本，可以选择以通常乘法log(n)减速的方式模拟破坏，或者可以选择以参照透明的方式运行以附加的持续减速造成的破坏。

有关此翻译问题的良好示例，请查看持久联合查找算法或功能图形库。

于 2013-08-04T21:17:33.347 回答