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

更新：我非常喜欢这个问题，我只是写了博客。请参阅Strings, immutability and persistence

简短的回答是：如果 n 没有变大，则 O(n) 是 O(1)。大多数人从微小的字符串中提取微小的子字符串，因此复杂性如何渐近增长完全无关紧要。

长答案是：

一个不可变的数据结构使得一个实例上的操作允许重新使用原始内存，只需要少量（通常为 O(1) 或 O(lg n)）的复制或新分配，称为“持久”不可变的数据结构。 .NET 中的字符串是不可变的；您的问题本质上是“他们为什么不坚持不懈”？

因为当您查看通常在 .NET 程序中对字符串执行的操作时，简单地创建一个全新的字符串在所有相关方面都几乎没有更糟。构建复杂的持久性数据结构的费用和难度并不能收回成本。

人们通常使用“子字符串”来提取一个短字符串——比如说，十个或二十个字符——从一个稍长的字符串中——可能是几百个字符。您在逗号分隔的文件中有一行文本，并且您想要提取第三个字段，即姓氏。该行可能有几百个字符长，名称将是几十个。在现代硬件上，五十字节的字符串分配和内存复制速度惊人。制作一个由指向现有字符串中间的指针加上长度组成的新数据结构也非常快是无关紧要的。 “足够快”顾名思义就是足够快。

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

如果人们通常对字符串执行的子字符串操作完全不同，那么采用持久方法是有意义的。如果人们通常有数百万个字符的字符串，并且正在提取数千个大小在十万个字符范围内的重叠子字符串，并且这些子字符串在堆中存在很长时间，那么使用持久子字符串将是非常有意义的方法;不这样做是浪费和愚蠢的。但是大多数业务线程序员甚至不做任何类似这类事情的事情。 .NET 不是为人类基因组计划的需求量身定制的平台； DNA 分析程序员每天都必须解决这些字符串使用特性的问题；你不这样做的可能性很大。少数确实构建了与他们的使用场景密切匹配的持久数据结构的人。

例如，我的团队编写的程序可以在您键入 C# 和 VB 代码时对其进行即时分析。其中一些代码文件非常庞大，因此我们不能进行 O(n) 字符串操作来提取子字符串或插入或删除字符。我们构建了一堆持久的不可变数据结构，用于表示对文本缓冲区的编辑，使我们能够快速有效地重用大量现有字符串数据以及对典型编辑的现有词法和句法分析。这是一个很难解决的问题，它的解决方案是针对 C# 和 VB 代码编辑的特定领域量身定制的。期望内置的字符串类型为我们解决这个问题是不现实的。

---

正是因为字符串是不可变的，.Substring 必须至少复制原始字符串的一部分。制作 n 个字节的副本需要 O(n) 时间。

您认为如何在恒定时间内复制一堆字节？

编辑：Mehrdad 建议根本不复制字符串，而是保留对其中一部分的引用。

考虑在 .Net 中，一个多兆字节的字符串，有人在其上调用 .SubString(n, n+3)（对于字符串中间的任何 n）。

现在，不能仅仅因为一个引用保留 4 个字符就对整个字符串进行垃圾收集吗？这似乎是一种荒谬的空间浪费。

此外，跟踪对子字符串的引用（甚至可能在子字符串内），并试图在最佳时间复制以避免击败 GC（如上所述），使这个概念成为一场噩梦。在 .SubString 上复制并保持简单的不可变模型要简单得多，也更可靠。

编辑：这是一个关于在较大字符串中保留对子字符串的引用的危险的good little read。

---

Java（与 .NET 相对）提供了两种执行 Substring() 的方法，您可以考虑是只想保留引用还是将整个子字符串复制到新的内存位置。

简单的 .substring(...) 与原始 String 对象共享内部使用的 char 数组，然后您可以在需要时使用 new String(...) 将其复制到新数组（以避免妨碍原始数组的垃圾收集）。

我认为这种灵活性是开发人员的最佳选择。

---

Java 曾经引用较大的字符串，但是：

Java 也将其行为更改为复制，以避免内存泄漏。

我觉得它可以改进：为什么不只是有条件地进行复制呢？

如果子字符串的大小至少是父字符串的一半，则可以引用父字符串。否则只能复制一份。这避免了泄漏大量内存，同时仍然提供了显着的好处。

---

这里的答案都没有解决“括号问题”，也就是说.NET中的字符串表示为BStr（指针“之前”存储在内存中的长度）和CStr（字符串以a结尾）的组合'\0'）。

因此，字符串“Hello there”表示为

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

（如果在 fixed 语句中分配给 char*，则指针将指向 0x48。）

这种结构允许快速查找字符串的长度（在许多情况下很有用），并允许在 P/Invoke 中将指针传递给期望以 null 结尾的字符串的 Win32（或其他）API。

当您执行 Substring(0, 5) 时，“哦，但我保证在最后一个字符之后会有一个空字符”规则说您需要制作副本。即使您在末尾得到子字符串，也没有地方可以放置长度而不破坏其他变量。

不过，有时您确实想谈论“字符串的中间”，而您不一定关心 P/Invoke 行为。最近添加的 ReadOnlySpan<T> 结构可用于获取无复制子字符串：

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

ReadOnlySpan<char>“子字符串”独立存储长度，不保证值结束后有'\0'。它可以“像字符串一样”以多种方式使用，但它不是“字符串”，因为它没有 BStr 或 CStr 特征（更不用说两者）。如果您从不（直接）P/Invoke，那么差别不大（除非您要调用的 API 没有 ReadOnlySpan<char> 重载）。

ReadOnlySpan<char> 不能用作引用类型的字段，因此还有 ReadOnlyMemory<char> (s.AsMemory(0, 5))，它是具有 ReadOnlySpan<char> 的间接方式，因此存在与 string 相同的差异。

对先前答案的一些答案/评论谈到让垃圾收集器在您继续谈论 5 个字符时必须保留一百万个字符的字符串是很浪费的。这正是您可以使用 ReadOnlySpan<char> 方法获得的行为。如果您只是进行简短的计算，则 ReadOnlySpan 方法可能会更好。如果您需要将其保留一段时间并且只保留原始字符串的一小部分，那么做一个适当的子字符串（修剪掉多余的数据）可能会更好。中间某处有一个过渡点，但这取决于您的具体用法。

---