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

Question

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

c#.netstringsubstringtime-complexity

470

考虑到在.NET中字符串是不可变的，我在想为什么设计中string.Substring()的时间复杂度是O(substring.Length)，而不是O(1)？

也就是说，是否存在任何权衡取舍？

- user541686

3

@Mehrdad: 我喜欢这个问题。你能告诉我如何在 .Net 中确定给定函数的 O() 吗？是应该计算还是有其他方法？谢谢。 - odiseh

1

@odiseh：有时候（比如这种情况），很明显字符串正在被复制。如果不确定，你可以查看文档、进行基准测试或尝试查看.NET Framework源代码来弄清楚它是什么。 - user541686

5个回答

123

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

你认为如何在常数时间内复制一堆字节？

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

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

现在，整个字符串不能被垃圾回收，仅因为有一个引用持有4个字符？这似乎是一种荒谬的浪费空间。

此外，跟踪对子字符串（甚至可能在子字符串内部）的引用，并尝试在最佳时间进行复制以避免破坏GC（如上所述），使概念成为一场噩梦。更简单、更可靠的方法是在.SubString上进行复制，并维护直观的不可变模型。

编辑：这里有一篇不错的文章，关于在较大的字符串中保留子字符串的引用可能会带来的危险。

- abelenky

5

+1：恰好是我的想法。内部可能使用的是memcpy，它仍然是O(n)的。 - leppie

7

我猜可能根本不需要复制它？它已经存在了，为什么还要复制呢？ - user541686

2

@Mehrdad：如果你追求性能，那么在这种情况下就去使用unsafe。然后你就可以获得一个char*子字符串。 - leppie

9

@Mehrdad，你可能期望过高了，它被称为"StringBuilder"，它擅长于构建字符串。它并不被称为"StringMultiPurposeManipulator"。 - MattDavey

3

在.NET中，字符串不是以NULL作为结尾的。如Lippert的文章所解释的那样，前4个字节包含了字符串的长度。这就是为什么，正如Skeet指出的那样，它们可以包含\0字符的原因。 - Elideb

显示剩余19条评论

33

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

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

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

- sll

50

你称之为“灵活性”，我则称之为“一种意外引入难以诊断的错误（或者性能问题）到软件中，因为我没有意识到我必须停下来思考所有可能调用这段代码的地方（包括那些可能只在下一个版本中被引入的地方），仅仅是为了从字符串的中间获取4个字符”。 - Nir

3

取消了踩（downvote）…… 经过仔细的代码浏览，似乎Java中的子字符串引用了一个共享数组，至少在openjdk版本中是这样的。如果你想确保得到一个新的字符串，有一种方法可以做到。 - Don Roby

11

@Nir：我称之为“现状偏见”。对你来说，Java的做法似乎充满风险，而.Net的方式是唯一明智的选择。但对于Java程序员来说，情况恰恰相反。 - Michael Borgwardt

7

我强烈偏爱.NET，但这听起来是Java做对的一件事。允许开发者访问真正的O(1)子字符串方法很有用（而不是自己编写字符串类型，这会妨碍与每个其他库的互操作性，并且不如内置解决方案高效）。不过，Java的解决方案可能是低效的（至少需要两个堆对象，一个用于原始字符串，另一个用于子字符串）；支持切片的语言有效地使用栈上的一对指针替换了第二个对象。 - Qwertie

10

自JDK 7u6以来，不再是这样了 - 现在Java总是为每个.substring(...)复制String内容。 - Grzegorz Rożniecki

显示剩余4条评论

12

Java过去使用引用较大的字符串，但:

Java也改变了其行为，采取了复制方式以避免泄漏内存。

不过我认为这可以改进：为什么不根据情况有选择地进行复制呢？

如果子串至少是父串长度的一半，就可以引用父串。否则只需进行复制即可。这样可以避免泄漏大量内存，同时仍然提供重要的好处。

- user541686

始终使用复制允许您删除内部数组。这将减少堆分配的数量，节省短字符串的内存。这也意味着您不需要为每个字符访问跳过额外的间接层。 - CodesInChaos

2

我认为从中需要理解的重要事情是，Java实际上从使用相同基础的char[]（具有不同的指向开头和结尾的指针）转变为创建一个新的String。这清楚地表明，成本效益分析必须显示出对创建新的String的偏好。 - Phylogenesis

6

这里没有解决“括号问题”，即在.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

(如果在一个fixed语句中分配给char*，则指针将指向0x48。)

该结构允许快速查找字符串的长度（在许多上下文中很有用），并允许将指针传递到需要空终止字符串的Win32（或其他）API的P/Invoke中。

当您执行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方法可能更好。如果你需要将其持久化一段时间，并且只保留原始字符串的一小部分，则进行适当的子字符串（以修剪多余的数据）可能更好。在中间有一个转换点，但它取决于你的具体用途。

- bartonjs

1

48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 这一部分只有一个 6C 00，所以实际上应该是 "Helo there" 而不是 "Hello there"。 - Pang

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eric Lippert · Accepted Answer

更新：我非常喜欢这个问题，所以我写了一篇博客。请参见字符串、不变性和持久性

简短的回答是：如果n不会增长很大，那么O(n)就等同于O(1)。大多数人从小字符串中提取小子串，因此复杂度是如何渐进性增长的完全无关紧要。

长的回答是：

如果一个不可变数据结构被建立起来，使得对该实例的操作只需要进行少量（通常是O(1)或O(lg n)）的复制或新分配便能重用原始内存，则称之为“持久”不可变数据结构。在.NET中，字符串是不可变的；你的问题本质上是“为什么它们不是持久的”？

因为当你查看.NET程序中通常对字符串执行的操作时，与其简单地创建一个全新的字符串相比，在每一个相关方面，它本质上几乎没有更差的表现。因此，构建一个复杂的持久化数据结构的费用和难度并没有得到回报。

人们通常使用“子字符串”来提取短字符串——比如十或二十个字符——从稍长的字符串中——也许是几百个字符。你有一个包含逗号分隔文件中的一行文本，你想要提取第三个字段，即姓氏。该行可能有几百个字符，名字可能有几十个。在现代硬件上，字符串分配和内存复制50个字节非常快。构建一个由指向现有字符串中间的指针加上长度组成的新数据结构同样非常快，但这是不相关的；“足够快”在定义上就是足够快的。

提取的子字符串通常很小且生命周期短暂；垃圾回收器将很快回收它们，并且它们一开始就没有占用堆中太多空间。因此，采用鼓励大部分内存重复使用的持久化策略也不是一个胜利；你所做的只是使你的垃圾回收器变慢，因为现在它必须担心处理内部指针。

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

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