syn*_*pse 6 language-agnostic string language-design
有些语言(C#或Java)具有不可变字符串,而其他语言(例如Ruby)具有可变字符串.这些设计选择背后的原因是什么？
不可变字符串好的一个原因是它使Unicode支持更容易.现代Unicode无法再有效地适应固定大小的数据单元,这会破坏字符串索引和内存地址之间的一对一对应关系,从而为可变字符串提供优势.
过去,大多数西方应用程序使用单字节字符(各种基于ASCII的编码,或EBCDIC ......),因此您通常可以通过将字符串视为字节缓冲区(如传统的C应用程序)来有效地处理它们.
当Unicode相当新时,对前16位之外的任何东西都没有太多要求,因此Java对其Strings(和StringBuffers)使用了双字节字符.这使用了两倍的内存,并忽略了超出16位的Unicode扩展可能出现的任何问题,但当时很方便.
现在Unicode并不是那么新,虽然最常用的字符仍然适合16位,但你无法真正摆脱假装基本多语言平面的存在.如果您想诚实地声称支持Unicode,则需要可变长度字符或更大(32位？)的字符单元格.
对于可变长度字符,您不能再在O(1)时间内索引到任意长度的字符串 - 除非有其他信息,您需要从头开始计算以确定第N个字符是什么.这也破坏了可变字符串缓冲区的主要优点:能够无缝地修改子字符串.
幸运的是,大多数字符串操作实际上并不需要这种就地修改功能.词汇表,解析和搜索都是从头到尾按顺序迭代进行的.由于替换字符串的长度不必与原始字符串相同,因此一般搜索和替换从未就位.
连接大量子串实际上并不需要就地修改以提高效率.但是,你确实需要更加小心,因为(正如其他人已经指出的那样)通过为N个部分子串中的每一个分配一个新字符串,一个简单的连接循环很容易就是O(N ^ 2)...
避免幼稚连接的一种方法是提供可变StringBuffer或ConcatBuffer对象,以便有效地进行连接.另一种方法是包含一个不可变的字符串构造函数,它将迭代器放入一系列字符串中(有效地)连接起来.
但是,更一般地说,可以编写一个通过引用有效连接的不可变字符串库.这种字符串通常被称为" 绳索 "或"绳索",表明它至少比它组成的基本字符串更重要,但是为了连接目的,它更有效,因为它不需要完全重新复制数据!
上面的维基百科链接说"绳索"数据结构是连接的O(log N),但是Okasaki 的开创性论文" Purely Functional Data Structures "显示了如何在O(1)时间内进行连接.