如果字符串在 .NET 中是不可变的，那么为什么 Substring 需要 O(n) 时间

更新:我非常喜欢这个问题，我只是在博客上写了下来.见Strings, immutability and persistence

简短的答案是:O(n) is O(1) if n does not grow large.大多数人从细小的字符串中提取细小的子串，所以复杂度渐近增长是completely irrelevant.

长长的答案是:

一种不可变的数据 struct 被称为"持久的"不可变数据 struct ，这种 struct 的构建使得实例上的操作只需少量(通常是O(1)或O(lg n))的复制或新分配，就可以重复使用原始数据的内存.插手.NET是不变的；你的问题本质上是"为什么它们不持久"？

因为当你看到在中对字符串所做的操作时.NET程序，以各种相关的方式简单地创建一个全新的字符串.The expense and difficulty of building a complex persistent data structure doesn't pay for itself.

人们通常使用"子字符串"从一个稍长的字符串中提取一个短字符串——比如说，十个或二十个字符——可能是几百个字符.在一个逗号分隔的文件中有一行文本，需要提取第三个字段，即姓氏.这行可能有几百个字符长，名字可能有几十个.在现代硬件上，50字节的字符串分配和内存复制是astonishingly fast字节.让一个指向现有字符串中间的指针加上一个长度的新数据 struct 速度惊人地快是不相关的；"足够快"的定义是足够快.

提取的子串通常尺寸小，生命周期 短；垃圾收集者很快就会回收它们，而它们一开始并没有占用堆上太多的空间.因此，使用鼓励重用大部分内存的持久性策略也不是一种胜利；你所做的只是让你的垃圾收集器变慢，因为现在它不得不担心处理内部指针.

如果人们通常对字符串执行的子字符串操作完全不同，那么使用持久性方法是有意义的.如果人们通常有一百万个字符串，并且提取了成千上万个大小在十万个字符范围内的重叠子字符串，并且这些子字符串在堆中存在很长时间，那么使用持久子字符串方法将是非常有意义的；不这样做既浪费又愚蠢.但是most line-of-business programmers do not do anything even vaguely like those sorts of things.NET并不是一个为人类基因组计划量身定制的平台；DNA分析程序员每天都要解决这些字符串使用特性的问题；你不这么做的可能性很大.少数人确实构建了自己的持久数据 struct ，与their种使用场景紧密匹配.

例如，我的团队编写的程序可以在键入C#和VB代码时对其进行动态分析.其中一些代码文件是enormous，因此我们不能进行O(n)字符串操作来提取子字符串或插入或删除字符.我们已经构建了一系列持久不变的数据 struct ，用于表示对文本缓冲区的编辑，这使我们能够快速有效地重新使用大量现有字符串数据，并在典型编辑的基础上进行现有的词汇和语法分析.这是一个很难解决的问题，其解决方案仅限于C#和VB代码编辑的特定领域.指望内置字符串类型为我们解决这个问题是不现实的.