performance - 手指树(Data.Sequence)与绳索(Data.Rope)(Haskell，或一般情况下)

Question

Finger Tree (Data.Sequence) 之间的主要区别是什么？和一根绳子(Data.Rope)( Edward Kmett's version 或 Pierre-Etienne Meunier's version ？

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

作为一个程序员考虑处理效率，比如说一个 700 万个字符的序列，我需要在其中执行 (a) 在任何地方插入，(b) 剪切和粘贴段 (splice)，(c) 搜索和替换子字符串，这是更高效？

对 ehird 的澄清:

我的大头算法正在运行数以千计的搜索替换操作 , 喜欢 s/(ome)?reg[3]x/blah$1/g , 重复变异数据。所以我需要高效的正则表达式模式匹配(也许形式 regex-tdfa ？)以及拼接 (data[a:b] = newData)，其中不一定 (length(newData) == b-a+1)

Lazy ByteStrings 可能没问题，但是拼接怎么办 ?拼接一个 ByteString 是 O(dataSize/chunkSize) 线性时间(用于搜索)，加上(也许？)维护恒定大小块的开销。 (后半部分可能有误)；相对于 FingerTree 的 O(log(dataSize))。

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

性能问题 : 也许 Seq 远比 ByteString 差(q 显着常数因子)。在简单的测试中，将 7MB 读入严格的 ByteString然后将其打印到控制台的峰值为 60MB 实际内存使用量(根据 Windows 进程管理器)，但将该内容加载到 Seq Char然后打印使用400MB! (我应该单独发布这个问题，包括代码和分析细节。)

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

三连胜 :我短暂地看到了 Trifecta，这让我更加困惑。 (为什么它有自己已经发布的通用数据结构的新实现？它们更好吗？有太多几乎相同的选项!)

编辑了更多细节和改进的链接。

这个问题变大了。

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

Given all this information, I would recommend either Rope, or building your own structure with the fingertree package it's based on (rather than Seq, so that you can implement things like length properly with the Measured type-class — see Monoids and Finger Trees), with the leaf data chunked into an unboxed Vector. The latter is, of course, more work, but lets you optimise specially for your use-case. Either way, definitely wrap it up in an abstract interface.

我今天晚些时候会回来，并分解成新的问题。我会把低级的技术问题整理一下，然后再回到整体比较。
我将更改问题标题以更好地反射(reflect)我真正关心的问题“哪些 Haskell 模块提供或支持我需要有效的序列操作操作？”感谢 ehird 和其他响应者。

Answer 1

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

嗯，你链接的rope包只存储了ByteString的等价物s，而 Seq是通用的，可以处理任何类型的数据；前者可能更有效地存储字节串。

我怀疑它是相同的基本树结构，因为绳子实现了“字节串的指树”，而 Seq是一棵 2-3 指的树；它取决于(因此大概使用)fingertree包，本质上与 Data.Sequence 相同，但更通用。很可能绳子将数据打包成短ByteString s，这是不可能的 Seq (没有中断操作，如 length 等)。

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

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

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

针对您更新的问题:

自定义字符串类型的正则表达式:请记住，要使用具有“不寻常”字符串类型的现有正则表达式实现，您必须implement the support yourself将其粘贴到现有的 regex-tdfa 代码中。我不确定最终的表现会是什么。

懒人拼接ByteString s:注意懒惰ByteString默认情况下使用 64 KiB 块，您可以使用 fromChunks 使用任意大的块。手动。但你是对的，手指树可能更适合；还有更多的工作要做，已经用懒惰的方式为您处理了 ByteString s。

有限字母表:好的;我建议你抽象出(用 newtype )代表这个字母表序列的类型。这样，您可以尝试各种实现，同时希望对必须完成的工作进行本地化，这样您就可以根据实际性能数据而不是猜测进行选择:) 当然，编写新实现仍然需要前期成本。至于你的附加问题，newtype s 在编译时被删除，所以 newtype具有与其包装的类型相同的运行时表示。简而言之:不用担心将东西包裹在 newtype 中s。

序列性能:嗯，这并不奇怪。 Seq Char完全懒惰和装箱，不会“分块”Char一起喜欢 Rope将;它可能比 String 的内存效率更低.类似 Seq ByteString可能会表现得更好，但除非你的块是恒定大小的，否则你将失去获得有意义长度等的能力，而无需遍历整个事物。

EclipseFP 包问题:我不会根据这样的简单工具问题来选择使用哪种表示；我建议提出一个新问题。

三连冠:我认为三连胜与您的问题无关；它只是由与rope 相同的作者编写的，这就是为什么它与rope 的持续发展相关。它只是一个像 Parsec 这样的解析器组合器库，它更侧重于诊断等而不是性能，所以我认为它不能取代你的正则表达式。

就 #3 而言，而不是 ByteString ，您可能需要考虑 unboxed Vector ;这样，您就可以使用您的抽象字母类型而不是将东西改写成 ByteString的 Word8基于界面。

鉴于所有这些信息，我会推荐 Rope ，或使用 fingertree 构建您自己的结构打包它基于(而不是 Seq ，以便您可以使用 length 类型类正确实现诸如 Measured 之类的东西——参见 Monoids and Finger Trees )，叶数据被分块成一个未装箱的 Vector .当然，后者需要更多的工作，但可以让您专门针对您的用例进行优化。无论哪种方式，一定要把它包装在一个抽象接口(interface)中。

顺便说一句，正则表达式在 Haskell 生态系统中并没有得到应有的支持。如果有任何选择，可能值得考虑使用其他东西。但是它过多地依赖于你的程序的具体细节来给出具体的建议。