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

Question

鉴于字符串在.NET中是不可变的,我想知道为什么它们被设计为string.Substring()需要O(substring.Length)时间,而不是O(1)？

即,有什么权衡,如果有的话？

Answer 1

更新:我非常喜欢这个问题,我只是写了博客.请参阅字符串,不变性和持久性

简短的回答是:如果n不变大,则O(n)为O(1). 大多数人从微小的字符串中提取微小的子串,因此渐进式渐近增长的方式完全无关紧要.

答案很长的答案是:

构建一个不可变的数据结构,使得实例上的操作允许仅使用少量(通常为O(1)或O(lg n))复制或新分配来重复使用原始内存,称为"持久"不可变数据结构..NET中的字符串是不可变的; 你的问题基本上是"为什么他们不坚持"？

因为当你查看通常在.NET程序中对字符串进行的操作时,只需要创建一个全新的字符串,就会以各种相关的方式完全没有变得更糟.构建复杂的持久数据结构的费用和难度并不能为其付出代价.

人们通常使用"substring"来提取一个短字符串 - 比如十个或二十个字符 - 用一个稍长的字符串 - 可能是几百个字符.您在逗号分隔文件中有一行文本,并且您想要提取第三个字段,这是一个姓氏.该行可能是几百个字符长,名称将是几十个.在现代硬件上,50字节的字符串分配和存储器复制速度惊人地快.这使得一个新的数据结构由一个指向现有字符串中间的指针加上一个长度组成,这也是惊人的快速无关紧要; "足够快"的定义足够快.

提取的子串通常尺寸小,寿命短; 垃圾收集器很快就要收回它们,并且它们首先没有在堆上占用太多空间.因此,使用鼓励重用大部分内存的持久策略也不是一个胜利; 你所做的就是让你的垃圾收集器变慢,因为现在它不得不担心处理内部指针.

如果人们通常对字符串执行的子字符串操作完全不同,那么使用持久方法是有意义的.如果人们通常拥有百万字符的字符串,并且正在提取数千个大小在十万字符范围内的重叠子字符串,并且这些子字符串在堆上存在很长时间,那么使用持久子字符串将是完全合理的办法; 不要浪费和愚蠢.但是,大多数业务线程序员甚至都不会做任何事情..NET不是专为满足人类基因组计划需求而定制的平台; DNA分析程序员必须每天解决这些字符串使用特征的问题; 你不这样做的几率很高.少数人建立自己的持久数据结构,与他们的使用场景紧密匹配.

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

Answer 2

正因为字符串是不可变的,.Substring必须复制至少一部分原始字符串.制作n个字节的副本应该花费O(n)时间.

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

编辑:Mehrdad建议不要复制字符串,而是保留对它的一部分的引用.

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

现在,ENTIRE字符串不能仅仅因为一个引用持有4个字符而被收集垃圾？这似乎是一种荒谬的浪费空间.

此外,跟踪对子串的引用(甚至可能在子串内),并尝试在最佳时间复制以避免击败GC(如上所述),使得该概念成为一场噩梦.复制.SubString和维护直接的不可变模型要简单得多,也更可靠.

编辑: 这是一个很好的小读物,关于在较大的字符串中保持对子串的引用的危险.

Answer 3

Java(而不是.NET)提供了两种方法Substring(),您可以考虑是仅保留引用还是将整个子字符串复制到新的内存位置.

simple .substring(...)将内部使用的char数组与原始String对象共享,然后根据new String(...)需要将其复制到新数组(以避免阻碍原始数据集的垃圾收集).

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

Answer 4

Java用于引用更大的字符串,但是:

Java也将其行为改为复制,以避免泄漏内存.

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

如果子字符串至少是父字符串大小的一半,则可以引用父字符串.否则就可以复制一份.这样可以避免泄漏大量内存,同时仍能提供显着的优势.

Answer 5

这里的答案都没有解决“括号问题”，也就是说 .NET 中的字符串表示为 BStr（指针“之前”存储在内存中的长度）和 CStr（字符串以'\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

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

此结构允许快速查找字符串的长度（在许多上下文中很有用），并允许在 P/Invoke 中将指针传递给需要空终止字符串的 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))，这是拥有 a 的间接方式ReadOnlySpan<char>，因此存在相同的差异string。

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