c# - una - Si las cadenas son inmutables en.NET, ¿por qué Substring lleva tiempo O(n)?
substring c# ejemplos (5)
ACTUALIZACIÓN: Me gustó mucho esta pregunta, acabo de bloguearla. Ver Cuerdas, inmutabilidad y persistencia.
La respuesta corta es: O (n) es O (1) si n no crece. La mayoría de las personas extraen pequeñas cadenas de cuerdas pequeñas, por lo tanto, cómo la complejidad crece de forma asintótica es completamente irrelevante .
La respuesta larga es:
Una estructura de datos inmutables construida de tal manera que las operaciones en una instancia permiten la reutilización de la memoria del original con solo una pequeña cantidad (generalmente O (1) u O (lg n)) de copia o nueva asignación se llama "persistente" Estructura de datos inmutables. Las cadenas en .NET son inmutables; su pregunta es esencialmente "¿por qué no son persistentes"?
Porque cuando observamos las operaciones que normalmente se realizan en cadenas en programas .NET, es mucho peor que simplemente crear una cadena completamente nueva. El gasto y la dificultad de construir una estructura de datos persistente compleja no se pagan por sí mismos.
La gente suele usar "subcadenas" para extraer una cadena corta, por ejemplo, diez o veinte caracteres, de una cadena algo más larga, tal vez unos doscientos 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á tal vez un par de cientos de caracteres, el nombre será un par de docenas. La asignación de cadenas y la copia de memoria de cincuenta bytes es sorprendentemente rápida en el hardware moderno. Que hacer una nueva estructura de datos que consiste en un puntero al medio de una cadena existente más una longitud también es sorprendentemente rápido y irrelevante; "Lo suficientemente rápido" es por definición lo suficientemente rápido.
Las subcadenas extraídas son típicamente pequeñas en tamaño y cortas en vida; el recolector de basura los recuperará pronto, y no ocuparon mucho espacio en el montón en primer lugar. Por lo tanto, usar una estrategia persistente que fomente la reutilización de la mayor parte de la memoria tampoco es una ganancia; todo lo que has hecho es hacer que tu recolector de basura se vuelva más lento porque ahora tiene que preocuparse por manejar los punteros interiores.
Si las operaciones de subcadena que las personas solían hacer en cadenas eran completamente diferentes, entonces tendría sentido ir con un enfoque persistente. Si las personas normalmente tuvieran cadenas de un millón de caracteres y extrajeran miles de subcadenas superpuestas con tamaños en el rango de los cien mil caracteres, y esas subcadenas vivieran mucho tiempo en el montón, entonces tendría mucho sentido ir con una subcadena persistente enfoque; Sería inútil y tonto no hacerlo. Pero la mayoría de los programadores de línea de negocio no hacen nada ni vagamente como ese tipo de cosas . .NET no es una plataforma que se adapte a las necesidades del Proyecto Genoma Humano; Los programadores de análisis de ADN tienen que resolver problemas con esas características de uso de cuerdas todos los días; las probabilidades son buenas que no lo hacen. Los pocos que sí construyen sus propias estructuras de datos persistentes que coinciden estrechamente con sus escenarios de uso.
Por ejemplo, mi equipo escribe programas que realizan análisis sobre la marcha de los códigos C # y VB a medida que los escribe. Algunos de esos archivos de código son enormes y, por lo tanto, no podemos realizar manipulaciones de cadenas O (n) para extraer subcadenas o insertar o eliminar caracteres. Hemos construido un montón de estructuras de datos persistentes e inmutables para representar las ediciones en un búfer de texto que nos permiten reutilizar rápida y eficazmente la mayor parte de los datos de cadenas 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 ajustó de manera limitada al dominio específico de la edición de código C # y VB. Sería poco realista esperar que el tipo de cadena incorporado resuelva este problema por nosotros.
Dado que las cadenas son inmutables en .NET, me pregunto por qué se diseñaron de manera tal que string.Substring() lleva tiempo O ( substring.Length ), en lugar de O(1) .
es decir, ¿cuáles fueron las compensaciones, en su caso?
Java (en lugar de .NET) proporciona dos formas de realizar Substring() , puede considerar si desea mantener solo una referencia o copiar una subcadena completa en una nueva ubicación de memoria.
La simple .substring(...) comparte la matriz char utilizada internamente con el objeto String original, que luego puede copiar con una nueva new String(...) en una nueva matriz, si es necesario (para evitar el obstáculo de la recolección de basura del original). uno).
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 para copiar también, 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 es al menos la mitad del tamaño del padre, se puede hacer referencia al padre. De lo contrario, uno puede simplemente hacer una copia. Esto evita la pérdida de una gran cantidad de memoria al tiempo que proporciona un beneficio significativo.
Ninguna de las respuestas aquí abordó "el problema de paréntesis", 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 así 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 se asigna a un char* en una declaración fixed el puntero apuntará 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 otras) que esperan una cadena terminada en nulo.
Cuando haces la Substring(0, 5) la regla de "oh, pero prometí que habría un carácter nulo después del último carácter" 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 "la mitad de la cadena", y no necesariamente te importa el comportamiento P / Invocar. La estructura ReadOnlySpan<T> recientemente agregada 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 las características BStr o CStr (mucho menos las dos). Si nunca (directamente) P / Invoke, entonces no hay mucha diferencia (a menos que la API a la que desea llamar no tenga una sobrecarga ReadOnlySpan<char> ).
ReadOnlySpan<char> no se puede usar como el campo de un tipo de referencia, por lo que también hay ReadOnlyMemory<char> ( s.AsMemory(0, 5) ), que es una forma indirecta de tener un ReadOnlySpan<char> , por lo que las mismas diferencias -desde- existen string .
Algunas de las respuestas / comentarios sobre respuestas anteriores mencionaron que es un desperdicio que el recolector de basura tenga que mantener una cadena de millones de caracteres mientras continúa hablando de 5 caracteres. Ese es precisamente el comportamiento que puede obtener con el enfoque ReadOnlySpan<char> . Si solo estás haciendo cálculos cortos, el enfoque ReadOnlySpan es probablemente mejor. Si necesita persistir por un tiempo y va a conservar solo un pequeño porcentaje de la cadena original, probablemente sea mejor hacer una subcadena adecuada (para eliminar el exceso de datos). Hay un punto de transición en algún punto intermedio, pero depende de su uso específico.
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) tiempo.
¿Cómo crees que copiarías un montón de bytes en tiempo constante ?
EDIT: Mehrdad sugiere no copiar la cadena en absoluto, pero mantener una referencia a una parte de ella.
Considere en .Net, una cadena de varios megabytes, en la que alguien llama .SubString(n, n+3) (para cualquier n en el medio de la cadena).
Ahora, ¿la cadena ENTIRE no puede ser recolectada como basura solo porque una referencia se aferra a 4 caracteres? Eso parece un ridículo desperdicio de espacio.
Además, rastrear las referencias a las subcadenas (que incluso pueden estar dentro de las subcadenas) y tratar de copiarlas en los momentos óptimos para evitar derrotar al GC (como se describe anteriormente), hace que el concepto sea una pesadilla. Es mucho más simple, y más confiable, copiar en .SubString , y mantener el modelo inmutable directo.
EDIT: Aquí hay una buena lectura acerca del peligro de mantener referencias a subcadenas dentro de cadenas más grandes.