问题标签 [finger-tree]

我想要一个具有快速连接和编辑操作的字符串表示。我已经阅读了论文“绳索：弦乐的替代品”，但自 1995 年以来，该领域是否有任何重大改进？

编辑：我之前考虑过的一种可能性是使用带有字符串作为叶子的2-3 指树，但我没有对此进行详细分析；这会在末端和对数（以较小字符串的块数）连接上提供摊销的恒定时间添加/删除，而对于绳索则相反。

Clojure 的新 contrib 库组有一个手指树 库。clojure 中手指树的用例是什么？何时应该使用手指树而不是 clojure 的其他持久数据结构之一：向量、集合、映射、持久队列等。

Clojure的喜悦提到手指树可用于需要廉价插入和删除的索引集合。它们也被描述为“数据结构的瑞士军刀”。这方面的例子将不胜感激。

我一直在研究此链接中描述的树数据结构（靠近底部）：

http://sigpipe.macromates.com/2009/08/13/maintaining-a-layout/

提到这个数据结构可以是一个手指树。然而，在对手指树进行更多研究后，我发现这缺少使手指树成为手指树的“手指”。相反，这似乎只是一个带注释的二叉树（用子树大小注释）。

您是否知道该数据结构的现有实现（任何语言），我可以将其用作我自己实现的参考（尽管，最好不是函数式编程语言的实现）？

或者，将子树大小注释改造成现有树数据结构的最佳方法是什么？

谢谢！

昨天的Wikibender以这个关于 Comonads 的 stackoverflow 问题开始，最终出现在MarkCC关于手指树的文章中。

在文章中，他广泛使用了Reduce类型类。他写这个 typeclass 好像它是一个非常常见和经常使用的库，但我在 hackage 上找不到它，也找不到足够的文档来真正理解代码。

有人可以帮我理解Reduce类型类在做什么，(-<)and(>-)运算符是如何工作的，以及文章中的代码应该告诉我什么（复制如下）？

正确完成手指树的代码清单（我希望）：

清单 1：Node 的实例声明

清单 2：FingerTree 的实例声明

清单 3：数据类型

我在我的书以及互联网上的几个网站上搜索了高低，但我并不完全确定我的答案。

关于存在的反转数量，我需要给出 InsertionSort 和 FingerTreeSort（基于 RB-Trees）的渐近运行时。InsertionSort 运行时间为 O(n+INV)，FingerTreeSort 运行时间为 O(n+n*lg(INV/n+1)。我需要给出 INV = 0、n、n^1.5 和 n^2/ 的渐近运行时4.

我自己想出的是 InsertionSort 运行在：O(n)、O(n)、O(n^2) 和 O(n^2)

这个对吗？为什么不？（我特别不确定 INV = n 和 n^1.5）

对于 FingerTreeSort：O(n*lg(n))、O(n*lg(n))、O(n*lg(sqrt(n))) 和 O(n*lg(n^2))

我对 FingerTreeSort 中的所有内容都存有疑问，但我认为它们应该是这样的。如何找到正确的渐近运行时？例如对于 FingerTreeSort 和 n^1.5，我认为它会通过插入通用运行时给出 O(n+n*lg(n^1.5/n+1) 并简化： O(n+n*lg (sqrt(n)+1) 并且看到它是渐近的，我可以忽略 +1 和 +n 等较低的数字给我 O(n*lg(sqrt(n)))。这是正确的做法吗?

提前感谢那些回答这个问题的人。我非常喜欢它:)

附言。用java编写，这对问题并不重要。

不久前，我看到一篇关于 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树的注释或注释。

显然Seq渐近地执行与所有可能的操作相同或更好[]的操作。但是由于它的结构比列表更复杂，对于小尺寸，它的恒定开销可能会使其变慢。我想知道多少钱，特别是：

1. <|相比慢了:多少？
2. Seq与折叠/遍历相比，折叠/遍历慢了多少[]（不包括折叠/遍历函数的成本）？
3. \xs x -> xs ++ [x]变慢的大小（大约）是|>多少？
4. ++变慢的大小（大约）是><多少？
5. viewl与列表上的模式匹配相比，结果上的调用和模式匹配的成本是多少？
6. 与-元素列表相比，-元素占用n多少内存？（不计算元素占用的内存，只计算结构。）Seqn

我知道这很难衡量，因为Seq我们谈论的是摊销复杂性，但我想至少知道一些粗略的数字。

我正在寻找一种持久的顺序数据结构，它允许有效的随机插入和删除。我发现了以下实现：

• clojure.data.finger-tree (counted-double-list 实现)
• wgjo.data.cljs
• flexvec

由于过去两年在 clojure.data.finger-tree 中没有太多活动，而其他活动相对较新，我想知道是否有人在生产中使用过这些中的任何一个，以及我是否有其他选择被忽视了。

Finger Tree 论文： http: //www.soi.city.ac.uk/~ross/papers/FingerTree.html 是 Data.Sequence 库的基础：https ://www.haskell.org/ghc/docs /7.6.1/html/libraries/containers-0.5.0.0/Data-Sequence.html#g:10

但该库似乎只提供尺寸注释手指树的功能。它不允许客户端提供其他注释来使用。特别是，排序函数返回另一个 Seq，而不是“SortSeq”。

是否存在提供本文中描述的所有功能的 FingerTrees 的现有 haskell 实现？

I've googled a bit and found a paper on Finger Trees, which can be used to implement a priority queue with proper asymptotic complexity, but they're quite complicated, but still about the simplest thing I could find.

Is there a simple data structure that allows to implement a fast priority queue in Haskell? Think simple as in you could explain it to a novice programmer.