Si las cadenas son inmutables in.NET, entonces, ¿por qué la subcadena toma O (n) tiempo?

Precisamente debido a que las cadenas son inmutables, .Substring debe hacer una copia de al menos una porción de la cadena original. Hacer una copia de n bytes debe tomar O(n) tiempo.

¿Cómo crees que sería copiar un montón de bytes en constante tiempo?

EDIT: Mehrdad sugiere no copiar la cadena en absoluto, sino mantener una referencia a una parte de ella.

Considere en. Net, una cadena multi-megabyte, en la que alguien llama .SubString(n, n+3) (para cualquier n en el medio de la cuerda).

Ahora, la cadena COMPLETA no se puede recoger basura solo porque una referencia está sosteniendo 4 caracteres? Eso parece un ridículo desperdicio de espacio.

Además, rastrear referencias a subcadenas (que incluso pueden estar dentro de subcadenas), y tratar de copiar en momentos óptimos para evitar derrotar al GC (como se describió anteriormente), hace que el concepto sea una pesadilla. Es mucho más simple, y más confiable, copiar en .SubString, y mantener el sencillo inmutable modelo.

EDITAR: Aquí hay un buena lectura sobre el peligro de mantener referencias a subcadenas dentro de cadenas más grandes.

Java (a diferencia de.NET) proporciona dos formas de hacer Substring(), puede considerar si desea mantener solo una referencia o copiar una subcadena completa a una nueva ubicación de memoria.

El simple .substring(...) comparte el array char utilizado internamente con el objeto String original, que luego con new String(...) puede copiar a un nuevo array, si es necesario (para evitar obstaculizar la recolección de basura del original).

Creo que este tipo de flexibilidad es la mejor opción para un desarrollador.

Java se utiliza para hacer referencia a cadenas más grandes, pero:

Java cambió su comportamiento a copiando también, para evitar fugas de memoria.

Sin embargo, siento que se puede mejorar: ¿por qué no hacer la copia condicionalmente?

Si la subcadena es al menos la mitad del tamaño del padre, se puede hacer referencia al padre. De lo contrario, uno puede hacer una copia. Esto evita la pérdida de una gran cantidad de memoria, mientras que todavía proporciona un beneficio significativo.

Ninguna de las respuestas aquí aborda "el problema de los corchetes", es decir que las cadenas en.NET se representan como una combinación de un BStr (la longitud almacenada en la memoria "antes" del puntero) y un CStr (la cadena termina en un '\0').

La cadena "Hello there" se representa como{[15]]}

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

(si se asigna a un char* en una instrucción fixed, el puntero apuntaría al 0x48.)

Esta estructura permite una búsqueda rápida de la longitud de una cadena (útil en muchos contextos) y permite que el puntero se pase en una P / Invoke a Win32 (u otras) API que esperan una cadena terminada en null.

Cuando haces Substring(0, 5) la regla "oh, pero prometí que habría un carácter nulo después del último carácter" dice que necesitas hacer una copia. Incluso si tienes la subcadena al final, entonces no habría lugar para poner la longitud sin corromper las otras variables.

A veces, sin embargo, realmente quieres hablar de " la mitad de la cadena", y no necesariamente te importa el comportamiento P / Invoke. La estructura ReadOnlySpan<T> recientemente añadida se puede usar para obtener una subcadena sin copia:

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

La "subcadena" ReadOnlySpan<char> almacena la longitud de forma independiente, y no garantiza que haya un '\0' después del final del valor. Se puede usar de muchas maneras "como una cadena", pero no es "una cadena" ya que no tiene características BStr o CStr (mucho menos ambas). Si nunca (directamente) P/Invoca entonces no hay mucho de una diferencia (a menos que la API que desea llamar no tenga una sobrecarga ReadOnlySpan<char>).

ReadOnlySpan<char> no se puede utilizar como el campo de un tipo de referencia, por lo que también hayReadOnlyMemory<char> (s.AsMemory(0, 5)), que es una forma indirecta de tener un ReadOnlySpan<char>, por lo que existen las mismas diferencias-de-string.

Algunas de las respuestas/comentarios en las respuestas anteriores hablaban de que era un desperdicio que el recolector de basura tuviera que mantener una cadena de millones de caracteres mientras se continúa hablando de 5 caracteres. Eso es precisamente el comportamiento que se puede obtener con el enfoque ReadOnlySpan<char>. Si solo estás haciendo cálculos cortos, el enfoque ReadOnlySpan es probablemente mejor. Si necesita persistirlo por un tiempo y va a mantener solo un pequeño porcentaje de la cadena original, hacer una subcadena adecuada (para recortar el exceso de datos) es probablemente mejor. Hay un punto de transición en algún lugar en el medio, pero depende de su uso específico.