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

Dado que las cadenas son inmutables en .NET, me pregunto por qué se han diseñado de forma que string.Substring() tome O ( substring.Length ) en vez de O(1) ?

es decir, ¿cuáles fueron las compensaciones, si las hubo?

ACTUALIZACIÓN: Me gustó tanto esta pregunta que acabo de publicarla. Ver cadenas, inmutabilidad y persistencia


La respuesta corta es: O (n) es O (1) si n no crece. La mayoría de las personas extrae subcadenas pequeñas de cadenas diminutas, por lo que la forma en que la complejidad crece asintóticamente es completamente irrelevante .

La respuesta larga es:

Una estructura de datos inmutables construida de manera tal que las operaciones en una instancia permiten la reutilización de la memoria del original con solo una pequeña cantidad (típicamente O (1) u O (lg n)) de copia o asignación nueva se denomina “persistente” estructura de datos inmutables. Las cadenas en .NET son inmutables; su pregunta es esencialmente “¿por qué no son persistentes”?

Porque cuando nos fijamos en las operaciones que normalmente se realizan en cadenas en progtwigs .NET, es en todos los sentidos apenas peor en absoluto para hacer una cadena completamente nueva. El gasto y la dificultad de construir una estructura de datos persistente compleja no se amortiza.

La gente generalmente usa “subcadena” para extraer una cadena corta, digamos, diez o veinte caracteres, de una cadena algo más larga, tal vez un par de cientos de caracteres. Tiene una línea de texto en un archivo separado por comas y desea extraer el tercer campo, que es un apellido. La línea tendrá quizás unos doscientos caracteres, el nombre será un par de docenas. La asignación de cadenas y la copia de memoria de cincuenta bytes es asombrosamente rápida en hardware moderno. Que hacer una nueva estructura de datos que consiste en un puntero a la mitad de una cadena existente más una longitud también es asombrosamente rápido es irrelevante; “suficientemente rápido” es por definición lo suficientemente rápido.

Las subcadenas extraídas son típicamente pequeñas en tamaño y de corta duración; el recolector de basura va a reclamarlos pronto, y no ocuparon mucho espacio en el montón en primer lugar. Entonces, usar una estrategia persistente que alienta la reutilización de la mayor parte de la memoria tampoco es una ganancia; todo lo que has hecho es que tu recolector de basura sea más lento porque ahora tiene que preocuparse por manejar los indicadores interiores.

Si las operaciones de subcadena que la gente normalmente hacía en cadenas de caracteres fueran completamente diferentes, entonces tendría sentido seguir con un enfoque persistente. Si las personas tuvieran típicamente cadenas de caracteres de millones y estuvieran extrayendo miles de subcadenas superpuestas con tamaños en el rango de cien mil caracteres, y esas subcadenas vivieran durante mucho tiempo en el montón, entonces tendría mucho sentido ir con una subcadena persistente. enfoque; sería un desperdicio y una tontería no hacerlo. Pero la mayoría de los progtwigdores de línea de negocio no hacen nada, ni siquiera vagamente como ese tipo de cosas . .NET no es una plataforma que se adapte a las necesidades del Proyecto del Genoma Humano; Los progtwigdores de análisis de ADN tienen que resolver problemas con esas características de uso de cadenas todos los días; las probabilidades son buenas de que no. Los pocos que construyen sus propias estructuras de datos persistentes que coinciden estrechamente con sus escenarios de uso.

Por ejemplo, mi equipo escribe progtwigs que realizan análisis sobre la marcha del código C # y VB a medida que lo escribe. Algunos de esos archivos de código son enormes y, por lo tanto, no podemos realizar la manipulación de cadenas O (n) para extraer subcadenas o insertar o eliminar caracteres. Hemos construido un conjunto de estructuras de datos permanentes e inmutables para representar ediciones en un búfer de texto que nos permite reutilizar rápida y eficientemente la mayor parte de los datos de cadena existentes y los análisis léxicos y sintácticos existentes en una edición típica. Este fue un problema difícil de resolver y su solución se adaptó estrechamente al dominio específico de edición de código C # y VB. Sería poco realista esperar que el tipo de cadena incorporada nos solucione este problema.

Precisamente porque las cadenas son inmutables, .Substring debe hacer una copia de al menos una parte de la cadena original. Hacer una copia de n bytes debería tomar O (n) el tiempo.

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


EDITAR: Mehrdad sugiere no copiar la cadena en absoluto, pero manteniendo una referencia a una parte de ella.

Considere en .Net, una cadena de varios megabytes, en la que alguien llama a .SubString(n, n+3) (para cualquier n en el medio de la cadena).

Ahora, la cadena ENTERA no puede ser recogida de basura solo porque una referencia se mantiene en 4 caracteres. Eso parece una ridícula pérdida de espacio.

Además, hacer un seguimiento de las referencias a subcadenas (que incluso pueden estar dentro de subcadenas) e intentar 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 modelo directo e inmutable.


EDITAR: Aquí hay una 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 que 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 conjunto de caracteres utilizado internamente con el objeto String original, que luego con un new String(...) puede copiar a un nuevo conjunto, si es necesario (para evitar obstaculizar la recolección de elementos no utilizados del original) uno).

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

Java solía hacer referencia a cadenas más grandes, pero:

Java también modificó su comportamiento para copiar , para evitar pérdidas de memoria.

Sin embargo, creo que se puede mejorar: ¿por qué no hacer la copia de forma condicional?

Si la subcadena tiene al menos la mitad del tamaño del elemento primario, se puede hacer referencia al elemento primario. De lo contrario, uno solo puede hacer una copia. Esto evita la pérdida de mucha memoria sin dejar de proporcionar un beneficio significativo.

Ninguna de las respuestas abordaba el “problema de horquillado”, que 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 “Hola” se representa como

 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 está asignado a un char* en una statement fixed el puntero apunta 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 API de P / Invoke a Win32 (u otra) que esperan una cadena terminada en nulo.

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


A veces, sin embargo, realmente quieres hablar sobre “el centro de la cadena”, y no necesariamente te importa el comportamiento P / Invocar. La estructura ReadOnlySpan recientemente agregada se puede usar para obtener una subcadena sin copia:

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

La subcadena ” ReadOnlySpan ” 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 / Invoque, no hay mucha diferencia (a menos que la API a la que desea llamar no tenga una sobrecarga ReadOnlySpan ).

ReadOnlySpan no se puede usar como el campo de un tipo de referencia, por lo que también hay ReadOnlyMemory ( s.AsMemory(0, 5) ), que es una forma indirecta de tener un ReadOnlySpan , por lo que las mismas diferencias -from- string existe.

Algunas de las respuestas / comentarios en las respuestas anteriores hablaban sobre el desperdicio de tener al recolector de basura para mantener una cadena de un millón de caracteres mientras usted continúa hablando de 5 caracteres. Ese es precisamente el comportamiento que puede obtener con el enfoque ReadOnlySpan . Si solo hace cálculos cortos, el enfoque ReadOnlySpan es probablemente mejor. Si necesita persistir por un tiempo y va a mantener solo un pequeño porcentaje de la cadena original, hacer una subcadena apropiada (para recortar el exceso de datos) es probablemente mejor. Hay un punto de transición en el medio, pero depende de tu uso específico.