如果字符串在.NET中不可变，那么为什么子字符串需要O（n）次？
鉴于字符串在.NET中是不可变的，我想知道为什么它们被设计成string.Substring()需要O（ substring.Length ）时间，而不是O(1) ？
即什么是权衡，如果有的话？
更新：我非常喜欢这个问题，我只是博客。 请参阅字符串，不变性和持久性
简短的回答是： 如果n不增长，则O（n）为O（1）。 大多数人从细小的字符串中提取细小的子串，所以复杂性如何逐渐增长是完全不相关的。
长的答案是：
一个不可变的数据结构，使得实例上的操作允许只用少量（通常为O（1）或O（lg n））复制或重新分配的原始内存的重用被称为“持久性”不可变的数据结构。 .NET中的字符串是不可变的; 你的问题基本上是“为什么他们不坚持”？
因为当你查看通常在.NET程序中的字符串上执行的操作时，只需创建一个全新的字符串就可以使每个相关方式几乎不会变得更糟糕。 构建复杂的持久数据结构的开销和难度并不会为自己付出代价。
人们通常使用“substring”从一个稍长的字符串中提取一个短字符串 - 比如说十或二十个字符 - 可能是几百个字符。 您在逗号分隔的文件中有一行文本，并且您想要提取第三个字段，即姓。 该行可能长达几百个字符，名字将会是几十个字符。 在现代硬件上，五十个字节的字符串分配和存储器复制速度惊人地快。 这使得一个新的数据结构由一个指向现有字符串中间的指针加上一个长度组成，同样令人惊讶的快速是无关紧要的; “足够快”根据定义足够快。
提取的子串通常尺寸较小且寿命较短; 垃圾收集器很快就会收回它们，并且它们一开始并没有占用太多的空间。 因此，使用鼓励大部分内存重用的持续策略也不是赢家; 你所做的一切都让你的垃圾收集器变得更慢了，因为现在它不得不担心处理内部指针。
如果人们通常在字符串上做的子字符串操作完全不同，那么采用持久的方法是有意义的。 如果人们通常具有百万字符的字符串，并且提取了数以千计的重叠子字符串，其大小在十万字符的范围内，并且这些子字符串在堆上生活了很长时间，那么使用持久子字符串办法; 如果不这样做会是浪费和愚蠢的。 但是大多数业务线程编程人员甚至不会像这些事情那样做任何事情 。 .NET不是一个专门为人类基因组计划设计的平台; DNA分析程序员必须每天解决这些字符串使用特征的问题; 你不这样做的可能性很大。 少数几个人构建自己的持久数据结构，这些结构与他们的使用场景非常匹配。
例如，我的团队编写的程序可以在您输入C＃和VB代码时进行即时分析。 其中一些代码文件非常庞大，因此我们不能通过O（n）字符串操作来提取子字符串或插入或删除字符。 我们已经构建了一组持久不变的数据结构，用于表示对文本缓冲区的编辑，以便我们能够快速高效地重用大量现有字符串数据以及对典型编辑进行的现有词法和语法分析。 这是一个难以解决的问题，其解决方案仅针对C＃和VB代码编辑的特定领域。 期待内置的字符串类型为我们解决这个问题是不现实的。
正是因为字符串是不可变的.Substring必须复制至少一部分原始字符串。 复制n个字节应该花费O（n）次。
你如何认为你会在一段时间内复制一堆字节？
编辑：Mehrdad建议不要复制字符串，但保留一个参考。
考虑使用.Net，一个数兆字节的字符串，某人在其上调用.SubString(n, n+3) （对于字符串中间的任何n）。
现在，仅仅因为一个引用持有4个字符，ENTIRE字符串不能被垃圾收集？ 这似乎是对空间的荒谬浪费。
此外，跟踪对子字符串（甚至可能在子字符串内）的引用，并且尝试在最佳时间进行复制以避免击败GC（如上所述），使得这个概念成为一场噩梦。 复制.SubString并维护简单的不可变模型要简单得多，而且更可靠。
编辑：这里有一个很好的一点阅读关于在更大的字符串中保持对子字符串的引用的危险。
Java（与.NET相对）提供了两种执行Substring() ，您可以考虑是仅保留一个引用还是将整个子字符串复制到新的内存位置。
简单的.substring(...)与原始String对象共享内部使用的char数组，如果需要，您可以使用new String(...)将其复制到新数组（如果需要）（以避免妨碍垃圾回收一）。
我认为这种灵活性对于开发者来说是最好的选择。
链接地址: http://www.djcxy.com/p/48415.html上一篇: If strings are immutable in .NET, then why does Substring take O(n) time?