在Haskell中实现高效的字符串处理

Question

我目前正在自学Haskell，想知道在Haskell中处理字符串的最佳实践是什么。

Haskell中默认的字符串实现是Char列表。根据Real World Haskell，这对文件输入输出来说是低效的，因为每个字符都是单独分配的（我认为这意味着String在Haskell中基本上是一个链表，但我不确定）。

但是，如果默认的字符串实现对文件I/O来说是低效的，那么在内存中处理字符串也是低效的吗？为什么或为什么不是？C使用char数组表示字符串，我认为这将是大多数语言中默认的做法。

据我所见，String的列表实现会占用更多的内存，因为每个字符都需要开销，并且迭代所需的时间也更长，因为需要进行指针解引用才能获取下一个字符。但是，到目前为止我喜欢玩Haskell，所以我想相信默认实现是高效的。

- Rob

---

默认实现是最方便处理小字符串和常见操作的。对于您想要基本视为字节块的大字符串，它并不高效；请使用Data.ByteString或Data.ByteString.Lazy。 - ShreevatsaR

Answer 1

除了String/ByteString之外，现在还有Text库，它结合了两者的优点——它使用Unicode并且在内部基于ByteString，因此您可以获得快速、正确的字符串。

- Porges

Answer 2

在Haskell中，处理字符串的最佳实践基本上是：使用Data.ByteString/Data.ByteString.Lazy。

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

---

就Haskell中默认字符串实现的效率而言，它并不高。每个Char代表一个Unicode码点，这意味着每个Char至少需要21位。由于String只是Char的链表，这意味着String在内存中的引用局部性很差，并且String在内存中相对较大。最小占用空间为N * (21位 + M位)，其中N是字符串长度，M是指针大小（32位、64位等）。与其他语言使用不同结构（特别是控制流）的方式不同，Haskell在许多地方使用列表，编译器无法将String优化为循环等结构。虽然Char对应于一个码点，但Haskell 98报告在执行文件IO时没有指定任何编码，甚至没有默认值，更不用说改变它了。实际上，GHC提供了扩展来执行二进制IO，但这时你已经超出范围了。即使像将字符串前面添加字符这样的操作，String在实践中也不太可能击败ByteString。

- Logan Capaldo

---

+1 正是我要回答的包。ByteString 将字符串存储为字节数组的偏移量。Data.ByteString.Char8 允许您直接在 ByteString 中使用 Chars，因为它假定只有底部 8 位是重要的（即 ASCII）。ByteString 还提供了自己的高效 IO 函数。 - Chris Smith

由于指针和堆对象的头部，一个 char 占用 2 个字，一个列表节点占用 3 个字，每个字符占用 5 个字（https://wiki.haskell.org/GHC/Memory_Footprint）。在 64 位系统上，每个字符占用 40 个字节。 - Blaisorblade

Answer 3

答案比“使用惰性字节串”更复杂。

字节串仅存储每个值的8位，而String则保存实际的Unicode字符。因此，如果您想要使用Unicode，则必须始终转换为UTF-8或UTF-16，这比仅使用字符串更昂贵。不要犯认为程序只需要ASCII的错误。除非它只是一次性代码，否则总有一天会有人需要输入欧元符号（U+20AC）或带重音符号的字符，您漂亮快速的字节串实现将无法恢复。

字节串使某些事情变得更加昂贵，例如在字符串开头添加内容。

话虽如此，如果您需要性能并且可以纯粹地表示数据为字节串，则应该这样做。

- Paul Johnson

---

不要犯认为你的程序只需要ASCII的错误。即使如此，你最好使用Data.Text来存储Unicode编码的字符串，而不是字符链表。此外，从性能上讲，Unicode往往比ASCII更快，因为操作系统通常只处理Unicode文本，并且在处理ASCII时需要进行转换。 - Dmytro

Answer 4

基本答案是正确的，使用ByteString。但是，在我的回答之前，其余三个答案都存在不准确的地方。

关于UTF-8：是否会成为问题完全取决于您对字符串进行的处理方式。如果您只是将它们视为单个数据块（包括操作，例如连接，但不是分割），或者进行某些有限的基于字节的操作（例如，查找以字节为单位而不是以字符为单位的字符串长度），则不会遇到任何问题。如果您正在使用I18N，则会出现足够多的其他问题，仅使用String而不是ByteString将开始修复您遇到的问题中非常少的一部分。

在ByteString前面添加单个字节可能比在String中执行相同操作更昂贵。但是，如果您经常这样做，可能可以找到处理特定问题的方法，这些方法更便宜。

但最终结果是，对于原始问题的发布者来说，Haskell中的Strings效率低下，但非常方便。如果您担心效率，请使用ByteStrings，并将它们视为Char8或Word8数组，具体取决于您的目的（ASCII / ISO-8859-1与某种Unicode或任意二进制数据）。通常，除非您知道为什么需要非lazy字节字符串（通常涉及对延迟评估性能方面的欣赏），否则请使用Lazy ByteStrings（在其字符串开头增加元素实际上是非常快的操作）。

值得一提的是，我正在完全使用Haskell构建自动交易系统，我们需要做的一件事是非常快速地解析我们通过网络连接收到的市场数据源。我可以处理每秒300条消息的读取和解析，并且CPU负载可以忽略不计；就处理这些数据而言，GHC编译的Haskell表现得与C相当接近，因此它根本没有进入我的问题列表。

- cjs