手指树（Data.Sequence）与绳索（Data.Rope）（Haskell，或一般情况）

Question

手指树之间的主要区别是什么(Data.Sequence) 和一根绳子 (Data.Rope) (爱德华Kmett 的版本 还是 Pierre-Etienne Meunier 的版本

在 Haskell 库中，Data .Sequence 有更多的功能，我认为绳索可以更有效地处理“块”，

例如处理 700 万个字符的序列，我需要（a）在任何地方插入，（b）剪切和粘贴。段（拼接），（c）搜索和替换子字符串，哪个更有效？

针对 ehird 的澄清：

1. 我的算法的大部分正在运行数千个搜索替换操作，例如s/(ome)?reg[3]x/blah$1/g，重复改变数据，所以我需要有效的正则表达式模式匹配（可能是regex-tdfa？）以及拼接 (data[a: b] = newData)，其中不一定(length(newData) == b-a+1)

2. 惰性字节字符串可能没问题，但是拼接怎么样？拼接 ByteString 是 O(dataSize / chunkSize) 线性时间（用于搜索），加上（也许？）维护恒定大小块的开销。 （后半部分可能有误）；与 FingerTree 的 O(log(dataSize)) 相比。

3. 我的“containee”数据类型抽象地是一个有限字母表。它可以具体表示为 Char 或 Byte 或 Word8 甚至类似于假设的 Word4 的东西（蚕食）。 ** 我有一个相关问题，关于如何有效地使用 newtype 或 data 以便我的代码可以引用抽象字母表，但编译后的程序仍然可以高效。 （我应该单独发布这个问题。）

4. 性能问题：也许 Seq 比 ByteString 差得多（按 q 重要常量因子）。在简单的测试中，将 7MB 读取到严格的 ByteString 中，然后将其打印到控制台，实际内存使用量达到 60MB 峰值（根据 Windows 进程管理器），但将该内容加载到 Seq Char 中code>然后打印使用400MB！ （我应该单独发布这个问题，并附上代码和分析详细信息。）

5. 平台问题：我正在使用 EclipseFP 和 Haskell 平台。我的机器上安装了 Text，我想尝试一下，但是我的 Eclipse 环境找不到它。每当我使用cabal install时，我都会遇到严重的麻烦（安装了不兼容版本的软件包，--user与--global混淆），所以我想坚持使用 EclipseFP 可以找到的平台包。我认为 Text 将进入下一版本的 Platform，所以这会很好。

6. Trifecta：我短暂地看到了 Trifecta，这让我更加困惑。 （为什么它有自己已经发布的通用数据结构的新实现？它们更好吗？太多几乎相同的选项！）

编辑提供更多详细信息和改进的链接。

这个问题问得很大了。

@ehird 的总结是主要的要点。字节串或向量的绳索或手指树加上一个小的自定义幺半群。无论哪种方式，我都必须编写一个简单的正则表达式实现来粘合。

鉴于所有这些信息，我会推荐绳索或建筑 您自己的结构及其所基于的 Fingertree 包（而不是 比 Seq 更好，这样你就可以正确地实现长度之类的东西 测量类型类 — 请参阅 Monoids 和 Finger Trees），带有叶子 数据分块到未装箱的向量中。当然后者更 工作，但可以让您专门针对您的用例进行优化。无论哪种方式， 肯定将其包装在一个抽象接口中。

我今天晚些时候会回来并提出新的问题。我会把底层的技术问题理清，然后再回来进行整体比较。 我将更改问题标题以更好地反映我真正关心的问题“哪些 Haskell 模块提供或支持我有效需要的序列操作操作？”感谢 ehird 和其他回复者。

Answer 1

对于这个答案的其余部分，我假设您实际上是在尝试存储原始字节，而不是字符。如果你想存储字符，那么你应该考虑使用 text （相当于 ByteString 对于 Unicode 文本）或基于它编写您自己的基于指树的结构。您还可以将 ByteString 与 Data.ByteString.UTF8 模块rel="noreferrer">utf8-string 包；我认为这最终会更高效，但它的功能远不如 Unicode 文本的 Text 全面。

好吧，您链接的 Rope 包仅存储 ByteString 的等效项，而 Seq 是通用的，可以处理任何类型的数据；前者对于存储字节串可能更有效。

我怀疑这是相同的基本树结构，因为 Rope 实现了“字节串的指树”，而 Seq 是一个 2-3 指树；它依赖于（因此可能使用） fingertree 包，该包本质上与 Data 相同。顺序但更一般。绳子很可能将数据打包成短的 ByteString，这是 Seq 不可能做到的（不破坏 length 等操作） 。

总而言之，如果您存储字节字符串数据，绳索似乎是一个更好的结构，并且它似乎具有用于“注释”字符串段的奇特功能；然而，它最后一次更新是在 7 月份，新的 trifecta 解析器组合器库由同一作者 (首次发布于 8 月）包含其 自己的集合绳索模块，因此在其上建立新代码可能是不明智的。当然，对 trifecta 所做的更改可能与一般用途无关，并且将它们拆分为新版本的 rod 可能不会太困难；也许他们没有这样做的唯一原因是因为 trifecta 已经有大量的依赖项:)

但是，如果您在处理过程中的任何时候需要通用容器类型（例如将字节解析为更丰富的表示序列），或者想要坚持 Haskell 平台中的内容，那么您需要使用 Seq。

您确定 ByteString 或 Text （因为您提到了字符）不适合您正在做的事情吗？它们存储偏移量和长度字段，因此获取子字符串不会导致任何复制。如果您的插入操作足够不频繁，那么它就可以解决。某种基于 IntMap 的结构也可能值得考虑。

---

回答您更新的问题：

1. 自定义字符串类型的正则表达式：请记住，要将现有的正则表达式实现与“不寻常”的字符串类型一起使用，您必须自己实现支持来粘合将其添加到现有的 regex-tdfa 代码中。我不确定最终的性能会如何。
2. 与惰性ByteStrings拼接：请注意，惰性ByteString默认使用64 KiB块，您可以使用任意大小的块手动使用 fromChunks 。但你是对的，手指树可能更合适；这只是更多的工作要做，而惰性 ByteString 已经为您处理好了。
3. 有限字母表： OK；我建议您抽象出（使用 newtype）表示该字母表序列的类型。这样，您可以尝试各种实现，同时希望本地化必须完成的工作，这样您就可以根据真实的性能数据而不是猜测进行选择:)当然，编写新的实现仍然需要前期成本。至于您的附加问题，newtype 在编译时被删除，因此 newtype 具有与其包装的类型相同的运行时表示形式。简而言之：不用担心将东西包装在 newtype 中。
4. Seq 性能： 嗯，这并不奇怪。 Seq Char 是完全惰性且装箱的，并且不会像 Rope 那样将 Char 一起“分块”；它的内存效率可能比 String 还要低。像 Seq ByteString 这样的东西可能会表现得更好很多，但是除非你的块是恒定大小的，否则你将失去获得有意义的长度等的能力，而无需遍历整个事情。
5. EclipseFP 包问题： 我不会根据这样的简单工具问题来选择使用哪种表示形式；我建议提出一个新问题。
6. 三连胜：我认为三连胜与您的问题无关；它与 Rope 是由同一作者编写的，这就是为什么它与 Rope 的持续发展相关。它只是一个像 Parsec 这样的解析器组合器库，它更关注诊断等而不是性能，所以我不认为它可以取代你的正则表达式。

就 #3 而言，您可能需要考虑一个 未装箱的 ByteString，而不是 ByteString 向量；这样，您就可以使用抽象字母类型，而不是侵入 ByteString 的基于 Word8 的界面。

鉴于所有这些信息，我建议使用 Rope，或者使用 构建自己的结构它基于的 Fingertree 包（而不是 Seq），以便您可以使用 Measured 类型类正确实现诸如 length 之类的东西— 参见幺半群和手指树），叶子数据分块为一个未装箱的Vector。当然，后者需要更多工作，但可以让您针对您的用例进行专门优化。不管怎样，一定要把它包装在一个抽象接口中。

顺便说一句，正则表达式在 Haskell 生态系统中并没有得到应有的良好支持；如果有任何选择的话，可能值得考虑使用其他东西。但这在很大程度上取决于您的程序的具体细节，无法给出具体的建议。