Haskell中的高效字符串实现

我现在正在教自己Haskell,我想知道在Haskell中处理字符串时最好的做法是什么.

Haskell中的默认字符串实现是Char列表.根据Real World Haskell的说法,这对于文件输入输出是低效的,因为每个字符都是单独分配的(我认为这意味着String基本上是Haskell中的链表,但我不确定.)

但是如果默认字符串实现对于文件i/o来说效率低下,那么在内存中使用字符串是否效率低下呢？为什么或者为什么不？C使用char数组来表示String,我认为这将是大多数语言中默认的处理方式.

正如我所看到的,String的列表实现将占用更多内存,因为每个字符都需要开销,并且还有更多时间进行迭代,因为需要指针解引用才能到达下一个char.但到目前为止我喜欢和Haskell一起玩,所以我想相信默认的实现是有效的.

除了String/ByteString之外,现在还有一个文本库,它结合了两者的优点 - 它与Unicode一起工作,同时在内部基于ByteString,因此您可以获得快速,正确的字符串.

在Haskell中使用字符串的最佳实践基本上是:使用Data.ByteString/Data.ByteString.Lazy.

http://hackage.haskell.org/packages/archive/bytestring/latest/doc/html/

就默认字符串实现的效率在Haskell中而言,它不是.每个Char代表一个Unicode代码点,这意味着它至少需要21比特Char.

由于a String只是[Char],这是一个链表Char,它意味着Strings具有较差的引用位置,并且再次意味着Strings在内存中相当大,至少它是N * (21bits + Mbits)N是字符串的长度而M是大小一个指针(32,64,你有什么),不像Haskell使用其他语言可能使用不同结构的列表的许多其他地方(我在这里特别考虑控制流),Strings不太可能被优化编译器到循环等.

虽然a Char对应于代码点,但Haskell 98报告并没有指定执行文件IO时使用的编码,甚至没有指定默认值,更不用说更改它了.在实践中,GHC提供了扩展,例如二进制IO,但无论如何你都会在预订时离开.

即使像前面的字符串那样的操作也不太可能在实践中String击败a ByteString.

答案比"使用延迟字节串"更复杂一些.

字节字符串每个值只存储8位,而String包含真正的Unicode字符.因此,如果您想使用Unicode,那么您必须始终转换为UTF-8或UTF-16,这比仅使用字符串更昂贵.不要错误地认为你的程序只需要ASCII.除非它只是一次性代码,否则有一天有人需要输入一个欧元符号(U + 20AC)或重音字符,你的快速字节串实现将无可挽回地破坏.

字节字符串会产生一些东西,比如在字符串的开头加上,更昂贵.

也就是说,如果您需要性能并且您可以纯粹以字节串表示您的数据,那么就这样做.

给出的基本答案是使用ByteString,这是正确的.也就是说,我之前的所有三个答案都有不准确之处.

关于UTF-8:这是否会成为一个问题完全取决于你对字符串的处理方式.如果您只是将它们视为单个数据块(包括连接操作,但不包括拆分),或者执行某些有限的基于字节的操作(例如,以字节为单位查找字符串的长度,而不是以字节为单位的长度)你不会有任何问题.如果你正在使用I18N,那么就有足够的其他问题只需使用String而不是ByteString开始只修复你遇到的极少数问题.

将单个字节预先添加到ByteString的前面可能比为String执行相同操作更昂贵.但是,如果您正在做很多这样的事情,那么可能找到处理更便宜的特定问题的方法.

但最终的结果是,对于原始问题的海报:是的,字符串在Haskell中效率低下,虽然相当方便.如果您担心效率,请使用ByteStrings,并将它们视为Char8或Word8的数组,具体取决于您的目的(ASCII/ISO-8859-1与某种类型的Unicode,或只是任意二进制数据).通常,使用Lazy ByteStrings(其中前置字符串的开头实际上是一个非常快速的操作),除非你知道为什么你想要非懒惰的(通常包含在对延迟评估的性能方面的评价).

对于它的价值,我正在构建一个完全在Haskell中的自动交易系统,我们需要做的一件事就是快速解析我们通过网络连接收到的市场数据源.我可以使用可忽略不计的CPU来处理每秒300条消息的读取和解析; 就处理这些数据而言,GHC编译的Haskell与C的表现足够接近,以至于它无法进入我的重要问题列表.