Haskell中的高效字符串实现

在haskell中使用字符串的最佳实践基本上是:使用data.bytestring/data.bytestring.lazy。

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

就Haskell中默认字符串实现的效率而言,它不是。各 Char 表示一个Unicode码位,这意味着每个码位至少需要21位 烧焦 .

自从A String 只是 [Char] ,这是一个链接列表 烧焦 这意味着 弦 S的参考位置不好,这又意味着 弦 S在内存中相当大,至少 N * (21bits + Mbits) 其中n是字符串的长度,m是指针的大小(32,64,what has you),与haskell使用列表的许多其他地方不同,其他语言可能使用不同的结构(我在这里特别考虑控制流)。 弦 S不太可能被编译器优化为循环等。

而一个 烧焦 对应于一个代码点,haskell 98报告没有指定任何关于在执行文件IO时使用的编码的内容,甚至没有指定一个默认值,更不用说更改它的方法了。实际上,ghc提供了一个扩展,例如二进制IO,但无论如何,您还是要离开预定位置。

即使是像在字符串前面做准备这样的操作,也不太可能 弦 将打败 ByteString 在实践中。

除了字符串/字节字符串,现在还有 Text 库,它结合了两个世界中最好的一个,它与Unicode一起工作,同时在内部基于字节串,所以您可以得到快速、正确的字符串。

答案比“使用懒惰的字节串”要复杂一些。

• 字节字符串每个值只存储8位,而字符串包含真正的Unicode字符。因此,如果您想使用Unicode,那么您必须始终转换为和从UTF-8或UTF-16进行转换,这比仅使用字符串更昂贵。不要误以为你的程序只需要ASCII码。除非它只是一个一次性的代码,否则有一天,有人需要输入一个欧元符号(U+20AC)或重音字符,而您漂亮的快速字节数实现将被无可挽回地破坏。
• 字节字符串会使一些事情变得更昂贵,比如在字符串的开头做准备。

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

给出的基本答案(使用bytestring)是正确的。也就是说,我之前的三个答案都不准确。

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

在字节串前面预处理单个字节可能比为字符串做相同的操作要贵。然而,如果你做了很多这样的事情,你可能会找到更便宜的方法来解决你的问题。

但最终的结果是,对于最初问题的海报:是的,字符串在haskell中效率很低,尽管非常方便。如果您担心效率问题,请使用字节串,并根据您的目的(ASCII/ISO-8859-1对Unicode的某种类型,或只是任意的二进制数据)将它们视为char8或word8的数组。一般来说,使用懒惰的字节串(在字符串开始前的预处理实际上是一个非常快速的操作),除非您知道为什么需要非懒惰的字节串(这通常是为了感谢懒惰评估的性能方面)。

值得一提的是,我正在哈斯克尔建立一个完全自动化的交易系统,我们需要做的一件事就是快速解析通过网络连接接收到的市场数据馈送。我可以用一个可忽略的CPU处理每秒300条消息的读取和解析;就处理这些数据而言,ghc编译的haskell的性能与c非常接近,几乎无法进入我的显著问题列表。