手指树(Data.Sequence)与绳索(Data.Rope)(Haskell,或一般)

Question

手指树(Data.Sequence)和绳子(Data.Rope)之间的主要区别是什么(Edward Kmett的版本或Pierre-Etienne Meunier的版本？

在Haskell库中,Data.Sequence具有更多功能.我认为绳索可以更有效地处理"块".

作为程序员考虑效率处理,比如一个700万个字符的序列,我需要做的事情(a)插入任何地方,(b)剪切和粘贴段(拼接),(c)搜索和替换子串,这是更高效？

澄清回应ehird:

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

2. 懒惰的ByteStrings可能没关系,但是拼接怎么样？拼接ByteString是O(dataSize/chunkSize)线性时间(用于搜索),加上(可能是？)开销用于维护恒定大小的块.(后一部分可能是错的); 对于FingerTree,vs O(log(dataSize)).

3. 我的"容器"数据类型抽象地是有限字母表.它可以具体地表示为Chars或Bytes或Word8s或甚至类似于假设的Word4s(半字节).**我有一个相关的问题,关于如何有效地使用一个newtype或data多个我的代码可以引用抽象字母表,但编译的程序仍然可以是有效的.(我应该单独发布这个问题.)

4. 性能问题:也许Seq远比ByteString差(通过q显着的常数因子).在简单的测试中,将7MB读入严格ByteString,然后将其打印到60MB真实内存使用的控制台峰值(根据Windows Process Manager),但将该内容加载到a Seq Char然后打印使用400MB!(我应该单独发布这个问题,包括代码和分析详细信息.)

5. 平台问题:我正在使用EclipseFP和Haskell平台.我在我的机器上安装了Text,我想尝试一下,但我的Eclipse环境找不到它.我得到了很大的麻烦,每当我用cabal install(包的不兼容版本得到安装,--userVS --global混乱),所以我要坚持用平台软件包EclipseFP可以找到.我认为Text将进入下一版本的平台,所以这将很好.

6. Trifecta:我简单地看到了Trifecta,这加剧了我的困惑.(为什么它有自己的已经发布的一般数据结构的新实现？它们更好吗？太多几乎相同的选项!)

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

这个问题很重要.

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

鉴于所有这些信息,我建议使用Rope,或使用它所基于的fingertree包构建自己的结构(而不​​是Seq,以便您可以使用Measured类类正确实现长度 - 请参阅Monoids和Finger Trees) ,将叶数据分块为未装箱的Vector.当然,后者是更多的工作,但让你专门针对你的用例进行优化.无论哪种方式,绝对将它包装在一个抽象的界面中.

我今天晚些时候会回来并分成新的问题.我将整理出低级技术问题,然后再回到整体比较中.我将更改问题标题以更好地反映我真正关心的问题"哪些Haskell模块提供或支持我需要的序列操作操作？" 谢谢你去ehird和其他响应者.

Answer 1

对于这个答案的其余部分,我假设你实际上是在尝试存储原始字节,而不是字符.如果要存储字符,则应考虑使用文本(相当于ByteStringUnicode文本)或基于它编写自己的基于fingertree的结构.您还可以使用utf8-string包中ByteString的Data.ByteString.UTF8模块; 我认为最终可以提高效率,但它的功能远不如Unicode文本.Text

那么,你链接的绳子包只存储了ByteStrings 的等价物,而是Seq通用的,可以处理任何类型的数据; 前者可能更有效地存储字符串.

我怀疑它是相同的基本树结构,因为绳子实现了"字节串的Seq指尖",并且是一个2-3指树; 它取决于(并因此可能使用)fingertree包,它与Data.Sequence基本相同,但更通用.很可能绳索将数据打包成短ByteStrings,这是不可能的Seq(不破坏操作length等).

总而言之,如果您存储字节串数据,则rope似乎是一个更好的结构,并且它似乎具有用于"注释"字符串段的奇特功能; 然而,它最后一次更新是在7月份,同一作者(最初于8月发布)的新三连词解析器组合库包含自己的一组绳索模块,因此在其上建立新代码可能是不明智的.当然,对三连胜所做的改变可能与一般用途无关,将它们作为一种新版本的绳索拆分可能并不太难; 也许他们没有去过的唯一原因是因为三连已经有很多依赖:)

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

你确定ByteString或者Text(因为你提到的角色)不适合你正在做的事情吗？它们存储偏移量和长度字段,因此获取子字符串不会导致任何复制.如果你的插入操作很少,那么它可能会成功.一个IntMap某种形式的基于结构可能是值得考虑了.

回答您的更新问题:

1. 自定义字符串类型的正则表:请记住,要使用具有"异常"字符串类型的现有正则表达式实现,您必须自己实现支持以将其粘贴到现有的regex-tdfa代码.我不确定最终的表现会是什么.
2. 使用lazy ByteStrings进行拼接:请注意,ByteString默认情况下,lazy 使用64 KiB块,您可以fromChunks手动使用尽可能大的块.但你是对的,手指树可能更适合; 只有更多的工作才能做到这一点已经为懒惰ByteStrings 处理了.
3. 有限字母:好的; 我建议你抽象出newtype一个代表这个字母表序列的类型.这样,您可以尝试各种实现,同时希望本地化必须完成的工作,这样您就可以根据实际性能数据而不是猜测来选择:)当然,编写新实现仍然需要预付成本.至于你的附加问题,newtypes在编译时被删除,所以a newtype具有与它包装的类型相同的运行时表示.简而言之:不要担心用newtypes 包装东西.
4. Seq表现:嗯,这并不奇怪.Seq Char是完全懒惰和盒装,并不会Char像所有人一样"分块" Rope; 它可能比内存效率更低String.喜欢的东西Seq ByteString可能会进行很多更好,但除非你的块是固定大小的,您将无法获得一个有意义的长度等,而无需遍历整个事情的能力.
5. EclipseFP包问题:我不会根据这样的简单工具问题选择使用哪种表示; 我建议问一个新问题.
6. Trifecta:我不认为三连词与你的问题有关; 它只是由绳索的同一作者写的,这就是为什么它与绳子的持续发展有关.它只是像Parsec这样的解析器组合库,它更侧重于诊断等而不是性能,所以我认为它不能取代你的正则表达式.

就#3而言,ByteString你可能想要考虑一个未装箱的Vector ; 这样,你就可以使用你的抽象字母表类型,而不是将事情搞砸到基于ByteStrings Word8的界面中.

鉴于所有这些信息,我建议使用它所基于Rope的fingertree包构建您自己的结构(而不是Seq,以便您可以length使用Measured类型类实现正确的类型 - 请参阅Monoids和Finger Trees)数据分块为未装箱的Vector.当然,后者是更多的工作,但让你专门针对你的用例进行优化.无论哪种方式,绝对将它包装在一个抽象的界面中.

顺便说一下,Haskell生态系统中的正则表达式并不像它们那样得到良好支持; 如果有任何选择,可能值得考虑使用其他东西.但是,它过分依赖于您的计划的具体细节来提供具体建议.