15

不久前，我看到一篇关于 FingerTrees 的文章（另请参阅随附的 Stack Overflow Question）并将这个想法归档。我终于找到了使用它们的理由。

我的问题是Data.FingerTree 包的边缘似乎有点腐烂。此外，使用数据结构的 Containers 包中的Data.Sequence重新实现了一个（可能更好的）版本，但不导出它。

尽管这种结构在理论上看起来很有用，但它似乎并没有得到很多实际使用或关注。有没有人发现FingerTrees作为一个实际的东西没有用，或者这是一个不够重视的案例？

进一步解释：

我有兴趣构建一个包含具有良好连接属性的文本的数据结构。考虑从各种片段构建 HTML 文档。大多数预构建的解决方案都使用字节串，但我真的想要一些能正确处理 Unicode 文本的东西。我目前的计划是将 Data.Text 片段分层到 FingerTree 中。

我还想借用 Data.Vector 的技巧，即在不使用 (offset,length) 操作进行复制的情况下获取切片。Data.Text.Text 已将此内置到数据类型中，但仅将其用于有效的 uncons 和 unsnoc 操作。在 FingerTree 中，此信息很容易成为v树的注释或注释。

4

3 回答 3

17

要特别回答您关于手指树的问题，我认为问题在于它们与数组相比具有相对较高的恒定成本，并且比实现有效连接的其他方法更复杂。一个 Builder 有一个更有效的界面来附加块，它们通常很容易获得（参见@informatikr 答案中的链接）。假设这Data.Text.Lazy是使用块的链接列表实现的，并且您正在Data.Text.Lazy从构建器创建一个。除非您有很多块（可能超过 50 个），或者重复访问列表末尾附近的数据，否则手指树的高固定成本可能不值得。

出于性能原因，该Data.Sequence实现是专门的，并不像fingertree包提供的完整接口那样通用。这就是它不被导出的原因；它实际上不可能用于除Sequence.

我还怀疑许多程序员对于如何实际使用 monoidal 注释不知所措，因为它存在相当大的抽象障碍。很多人不会使用它，因为他们看不到它与其他数据类型相比有何用处。

直到我阅读了 Chung- jieh Shan 的关于字数的系列博客（part2 , part3 , part4 ），我才真正明白了这一点。这证明了这个想法绝对可以在实际代码中使用。

在您的情况下，如果您需要检查部分结果并进行有效的附加，则使用手指树可能比构建器更好。根据构建器的实现，您最终可能会在转换为时进行大量重复工作Text，向构建器添加更多内容，Text再次转换为等。但这取决于您的使用模式。

你可能对我的splaytree包感兴趣，它提供了带有 monoidal 注释的 splay 树，并在它们之上构建了几种不同的结构。除了 splay 树本身，SetandRangeSet模块具有或多或少完整的 API，该Sequence模块主要是我用于测试的骨架。它不是您正在寻找的“包含电池”的解决方案（同样，@informatikr 的答案提供了这些），但是如果您想尝试使用 monoidal 注释，它可能比Data.FingerTree. 请注意，如果您按顺序遍历所有元素（或不断地 snoc 到最后，或类似的），展开树可能会变得不平衡，但如果追加和查找是交错的，则性能可能会非常好。

于 2012-06-22T10:16:52.937 回答
9

除了 John Lato 的回答之外，我还会添加一些关于手指树性能的具体细节，因为我过去花了一些时间来研究它。

大致的总结是：

  • Data.Sequence具有很大的常数因子和渐近线：它几乎与[]访问列表前面时一样快（两个数据结构都具有 O(1) 渐近线），并且在列表中的其他地方快得多（其中Data.Sequence的对数渐近线 trounce[]的线性渐近线）。

  • Data.FingerTree具有与 相同的渐近Data.Sequence性，但要慢一个数量级。

就像列表一样，手指树的每个元素的内存开销也很高，因此应该将它们与分块结合使用，以更好地使用内存和缓存。事实上，有几个包可以做到这一点（yi，trifecta，rope）。如果Data.FingerTree可以Data.Sequence在性能上接近，我希望看到一种Data.Text.Sequence类型，它实现了一个Data.Text值的手指树。这种类型会失去 的流式传输行为Data.Text.Lazy，但会受益于改进的随机访问和连接性能。（同样，我想看到Data.ByteString.Sequence和Data.Vector.Sequence。）

现在实现这些的障碍是不存在手指树的有效和通用实现（请参阅下面我进一步讨论的地方）。为了产生Data.Text.Sequence一个有效的实现，必须完全重新实现手指树，专门用于Text- 就像Data.Text.Lazy完全重新实现列表，专门用于Text. 不幸的是，手指树比列表复杂得多（尤其是串联！），所以这是一个相当大的工作量。

所以在我看来，答案是：

  • 专门的手指树很棒，但是要实现很多工作
  • 分块手指树（例如Data.Text.Sequence）会很棒，但目前性能不佳Data.FingerTree意味着它们在常见情况下不是分块列表的可行替代方案
  • 构建器和分块列表实现了分块手指树的许多好处，因此它们足以满足常见情况
  • 在构建器和分块列表不够用的罕见情况下，我们咬紧牙关忍受分块指树（例如在 yi 和 trifecta 中）的不良常数因子。

高效通用手指树的障碍

Data.Sequence和之间的大部分性能差距Data.FingerTree是由于以下两个优化Data.Sequence：

  • 度量类型专门用于Int，因此度量操作将编译为有效的整数运算，而不是

  • 度量类型被解包到Deep构造函数中，它将指针解引用保存在树操作的内部循环中。

可以在一般情况下应用这些优化，即Data.FingerTree通过使用数据族进行通用解包并利用 GHC 的内联和专用程序 - 请参阅我的fingertree-unboxed 包，它使通用手指树的性能几乎达到Data.Sequence. 不幸的是，这些技术存在一些重大问题：

  • 通用解包的数据族对用户来说是不愉快的，因为它们必须定义很多实例。这个问题没有明确的解决方案。

  • 手指树使用多态递归，GHC 的专业人士不能很好地处理（1、2）。这意味着，为了在度量类型上获得足够的专业化，我们需要大量的INLINEpragma，这会导致 GHC 生成大量代码。

由于这些问题，我从未在 Hackage 上发布过这个包。

于 2012-06-23T02:03:41.177 回答
7

忽略您的手指树问题，只回应您的进一步解释：您是否查看过 Data.Text.Lazy.Builder或专门用于构建 HTML 的blaze-html？

两者都允许快速连接。对于切片，如果这对解决您的问题很重要，那么它们可能没有理想的性能。

于 2012-06-22T09:03:50.690 回答