如果字符串在。net中是不可变的，那么为什么子字符串需要O(n)时间?

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

也就是说，如果有的话，折衷是什么?

24907 次浏览
小开

确切地说，因为字符串是不可变的，.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(...)将其复制到新数组(以避免阻碍原始数组的垃圾收集)。

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

小开
最佳答案

更新:我非常喜欢这个问题，我刚刚把它写在博客上。看到字符串，不变性和持久性

简短的答案是:如果n不变大，O(n)等于O(1)大多数人从小字符串中提取小子字符串，所以复杂性如何渐近增长是完全无关紧要的。

长一点的答案是:

在实例上的操作允许重用原始数据的内存，只需要少量的复制或分配(通常是O(1)或O(lgn))，这种不可变数据结构被称为“持久的”不可变数据结构。.NET中的字符串是不可变的;你的问题本质上是“为什么它们不是持久的”?

因为当你观察。net程序中对字符串执行的通常操作时，在所有相关的方式中，一点也不差只是简单地创建一个全新的字符串。构建复杂持久数据结构的成本和难度并不足以收回成本。

人们通常使用“substring”来从一个较长的字符串(可能是几百个字符)中提取一个短字符串(比如10个或20个字符)。在逗号分隔的文件中有一行文本，您希望提取第三个字段，即姓氏。一行可能有几百个字符长，名字也有几十个。字符串分配和50字节的内存复制在现代硬件上是发展速度惊人。创建一个由指向现有字符串中间的指针加上一个长度组成的新数据结构的速度惊人地快是无关紧要的;“足够快”的定义就是足够快。

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

如果人们通常对字符串执行的子字符串操作完全不同，那么使用持久方法是有意义的。如果人们通常有百万字符的字符串，并提取成千上万个大小在十万字符范围内的重叠子字符串，并且这些子字符串在堆上存在很长时间，那么使用持久子字符串方法是完全有意义的;不这样做既浪费又愚蠢。但是大多数业务线程序员不会做任何类似的事情. net并不是一个为人类基因组计划的需要量身定制的平台;DNA分析程序员每天都要解决这些字符串使用特征的问题;很有可能你不知道。少数人会构建自己的持久数据结构，密切匹配他们的的使用场景。

例如，我的团队编写的程序可以在你输入的时候对c#和VB代码进行动态分析。其中一些代码文件是巨大的，因此我们不能做O(n)字符串操作来提取子字符串或插入或删除字符。我们已经构建了一堆持久的不可变数据结构，用于表示对文本缓冲区的编辑，这允许我们快速有效地重用现有字符串数据的大块而且，现有的词汇和语法分析。这是一个很难解决的问题，它的解决方案仅限于c#和VB代码编辑的特定领域。期望内置字符串类型为我们解决这个问题是不现实的。

小开

Java曾经引用更大的字符串，但是:

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

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

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

小开

这里没有一个答案解决了“括号问题”，也就是说。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-statement中赋值给char*，指针将指向0x48。)

这种结构允许快速查找字符串的长度(在许多上下文中很有用)，并允许指针在P/Invoke中传递给Win32(或其他)api，这些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>的间接方式，因此存在相同的区别-from-string。

之前的一些回答/评论谈到，当你继续谈论5个字符时，垃圾收集器不得不保留一个百万字符的字符串是一种浪费。这正是你可以用ReadOnlySpan<char>方法得到的行为。如果只是进行简短的计算，ReadOnlySpan方法可能更好。如果需要持久化它一段时间，并且只保留原始字符串的一小部分，那么使用适当的子字符串(以删除多余的数据)可能会更好。中间有一个过渡点，但这取决于您的具体用法。


提交答案