为什么没有使用FingerTree来实现稳定的实现？

Question

不久之前,我遇到了一篇关于FingerTrees的文章(另见附带的Stack Overflow问题),并提出了这个想法.我终于找到了使用它们的理由.

我的问题是,Data.FingerTree软件包似乎在边缘有点腐烂.此外,Containers包中的Data.Sequence使用数据结构重新实现(可能更好)版本,但不导出它.

由于理论上这个结构似乎很有用,但它似乎没有得到很多实际使用或关注.有人发现FingerTrees作为一个实际问题没有用处,或者这是一个不够关注的案例？

---

进一步说明:

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

我还想借用Data.Vector借用切片而无需使用(偏移,长度)操作进行复制.Data.Text.Text内置于数据类型,但仅用于高效的uncons和unsnoc opperations.在FingerTree中,这些信息很容易成为v树的注释或注释.

Answer 1

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

该Data.Sequence实现专门出于性能原因,并不像fingertree包提供的完整接口那样通用.这就是它不出口的原因; 它不是真的可以用于除了a之外的任何东西Sequence.

我还怀疑许多程序员对如何实际使用monoidal注释感到茫然,因为它背后是一个相当重要的抽象障碍.很多人不会使用它,因为与其他数据类型相比,它们看不出它是如何有用的.

我真的不明白,直到我读仲杰山对博客系列字号码(第2部分,第三部分,第四部分).这证明了这个想法绝对可以用在实际的代码中.

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

您可能对我的splaytree包感兴趣,它提供带有幺半群注释的splay树,并在它们上构建了几个不同的结构.除了splay树本身,Set和RangeSet模块具有或多或少的完整API,该Sequence模块主要是我用于测试的骨架.这不是一个"电池包含"的解决方案,你正在寻找的东西(同样,@ informatikr的答案提供了那些),但如果你想尝试monoidal注释它可能比更有用Data.FingerTree.请注意,如果您按顺序遍历所有元素(或连续snoc到末尾或相似),则splay树可能会失去平衡,但如果追加和查找是交错的,则性能可能非常好.

Answer 2

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

广泛的总结是:

• Data.Sequence有很大的常数因子和渐近因子:它几乎和[]访问列表前面时一样快(两个数据结构都有O(1)渐近),而且列表中其他地方的速度要快得多(Data.Sequence对数渐近渐近[]线性的线性)渐近).

• 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的specialiser没有处理好(1,2).这意味着,为了在度量类型上获得足够的专业化,我们需要大量的INLINE编译指示,这会导致GHC生成大量代码.

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

Answer 3

忽略你的手指树问题,只回应你的进一步解释:你是否看过Data.Text.Lazy.Builder,或者,特别是建立HTML,blaze-html？

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