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

451

Dado que las cadenas son inmutables en .NET, me pregunto por qué se han diseñado de manera que string.Substring()lleve tiempo O ( substring.Length), en lugar de hacerlo O(1).

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

usuario541686
fuente
3
@Mehrdad: me gusta esta pregunta. ¿Podría decirme cómo podemos determinar O () de una función determinada en .Net? ¿Está claro o debemos calcularlo? Gracias
odiseh
1
@odiseh: A veces (como en este caso) está claro que la cadena se está copiando. Si no es así, puede buscar en la documentación, realizar puntos de referencia o intentar buscar en el código fuente de .NET Framework para descubrir qué es.
user541686

Respuestas:

423

ACTUALIZACIÓN: Me gustó mucho esta pregunta, simplemente la escribí en un blog. Ver cadenas, inmutabilidad y persistencia.


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

La respuesta larga es:

Una estructura de datos inmutable 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 (típicamente O (1) u O (lg n)) de copia o nueva asignación se llama "persistente" Estructura de datos inmutable. Las cadenas en .NET son inmutables; su pregunta es esencialmente "¿por qué no son persistentes"?

Porque cuando observa las operaciones que generalmente se realizan en cadenas en programas .NET, en todos los aspectos relevantes no es peor en absoluto crear una cadena completamente nueva. El gasto y la dificultad de construir una estructura de datos compleja y persistente no se pagan solos.

Las personas generalmente usan "subcadena" para extraer una cadena corta, digamos, diez o veinte caracteres, de una cadena algo más larga, quizás 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á quizás unos cientos de caracteres, el nombre será una docena. La asignación de cadenas y la copia de memoria de cincuenta bytes es asombrosamente rápida en el hardware moderno. Que hacer una nueva estructura de datos que consista en un puntero al centro 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 cortas en vida útil; 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 victoria; 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 subcadenas que la gente realizaba típicamente en cadenas fueran completamente diferentes, entonces tendría sentido optar por un enfoque persistente. Si las personas generalmente tienen cadenas de un millón de caracteres y extraen miles de subcadenas superpuestas con tamaños en el rango de los cien mil caracteres, y esas subcadenas vivieron mucho tiempo en el montón, entonces tendría mucho sentido ir con una subcadena persistente Acercarse; sería un desperdicio y una tontería no hacerlo. Pero la mayoría de los programadores de línea de negocios no hacen nada, incluso 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 cadenas todos los días; las probabilidades son buenas de que no lo hagas. Los pocos que 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 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 montón de estructuras de datos inmutables persistentes para representar cambios realizados en un búfer de texto que nos permite volver a utilizar de forma rápida y eficiente la mayor parte de los datos de cadena existentes y los análisis sintácticos y léxicos existentes en una edición típica. Este fue un problema difícil de resolver y su solución se ajustó estrechamente al dominio específico de edición de código C # y VB. No sería realista esperar que el tipo de cadena incorporado nos resuelva este problema.

Eric Lippert
fuente
47
Sería interesante contrastar cómo lo hace Java (o al menos lo hizo en algún momento en el pasado): la subcadena devuelve una nueva cadena, pero apunta al mismo carácter [] que la cadena más grande, lo que significa que el carácter más grande [] ya no se puede recolectar basura hasta que la subcadena queda fuera de alcance. Prefiero la implementación de .net con diferencia.
Michael Stum
13
He visto este tipo de código bastante: string contents = File.ReadAllText(filename); foreach (string line in content.Split("\n")) ...u otras versiones del mismo. Me refiero a leer un archivo completo, luego procesar las diferentes partes. Ese tipo de código sería considerablemente más rápido y requeriría menos memoria si una cadena fuera persistente; siempre tendría exactamente una copia del archivo en la memoria en lugar de copiar cada línea, luego las partes de cada línea a medida que la procesa. Sin embargo, como dijo Eric, ese no es el caso de uso típico.
configurador
18
@configurator: Además, en .NET 4, el método File.ReadLines divide un archivo de texto en líneas para usted, sin tener que leerlo primero en la memoria.
Eric Lippert
8
@Michael: Java Stringse implementa como una estructura de datos persistente (eso no se especifica en los estándares, pero todas las implementaciones que conozco hacen esto).
Joachim Sauer
33
Respuesta corta: se hace una copia de los datos para permitir la recolección de basura de la cadena original .
Qtax
121

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

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


EDITAR: Mehrdad sugiere no copiar la cadena en absoluto, sino mantener una referencia a un fragmento.

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, ¿TODA la cadena no se puede recolectar basura solo porque una referencia contiene 4 caracteres? Eso parece una pérdida ridícula de espacio.

Además, el seguimiento de las referencias a las subcadenas (que incluso pueden estar dentro de las subcadenas) y el intento de copiar en momentos óptimos para evitar derrotar al GC (como se describió anteriormente) hacen que el concepto sea una pesadilla. Copiar .SubStringy mantener el modelo directo e inmutable es mucho más simple y confiable .


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

abelenky
fuente
55
+1: Exactamente mis pensamientos. Internamente, probablemente usa lo memcpyque todavía es O (n).
leppie
77
@abelenky: ¿Supongo que quizás al no copiarlo en absoluto? Ya está allí, ¿por qué deberías copiarlo?
user541686
2
@Mehrdad: SI estás después del rendimiento. Simplemente no sea seguro en este caso. Entonces puedes obtener una char*subcadena.
leppie
99
@Mehrdad: es posible que esperes demasiado allí, se llama StringBuilder , y es bueno construir cadenas. No se llama StringMultiPurposeManipulator
MattDavey
3
@SamuelNeff, @Mehrdad: las cadenas en .NET no se NULL terminan. Como se explica en la publicación de Lippert , los primeros 4 bytes contienen la longitud de la cadena. Es por eso que, como señala Skeet, pueden contener \0personajes.
Elideb
33

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

El simple .substring(...)comparte la charmatriz utilizada internamente con el objeto String original, que luego new String(...)puede copiar a una nueva matriz, si es necesario (para evitar obstaculizar la recolección de basura del original).

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

sll
fuente
50
Lo llamas "flexibilidad". Lo llamo "Una forma de insertar accidentalmente un error difícil de diagnosticar (o un problema de rendimiento) en el software porque no me di cuenta de que tengo que parar y pensar en todos los lugares donde este código puede estar llamado desde (incluidos los que solo se inventarían en la próxima versión) solo para obtener 4 caracteres del centro de una cadena "
Nir
3
voto negativo retraído ... Después de un poco más cuidadoso de exploración del código, parece una subcadena en Java que hace referencia a una matriz compartida, al menos en la versión openjdk. Y si desea garantizar una nueva cadena, hay una manera de hacerlo.
Don Roby
11
@Nir: lo llamo "status quo bias". Para usted, la forma en que Java lo hace parece estar llena de riesgos y la forma .Net es la única opción sensible. Para los programadores de Java, lo contrario es el caso.
Michael Borgwardt
77
Prefiero fuertemente .NET, pero esto suena como una cosa que Java hizo bien. Es útil que se permita a un desarrollador tener acceso a un método de subcadena verdaderamente O (1) (sin rodar su propio tipo de cadena, lo que dificultaría la interoperabilidad con cualquier otra biblioteca, y no sería tan eficiente como una solución integrada) ) Sin embargo, la solución de Java es probablemente ineficiente (requiere al menos dos objetos de montón, uno para la cadena original y otro para la subcadena); los lenguajes que admiten cortes reemplazan efectivamente el segundo objeto con un par de punteros en la pila.
Qwertie
10
Como JDK 7u6 ya no es cierto , ahora Java siempre copia el contenido de String para cada uno .substring(...).
Xaerxess
12

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

Java también cambió su comportamiento a la copia , para evitar pérdidas de memoria.

Sin embargo, creo 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 solo puede hacer una copia. Esto evita la pérdida de mucha memoria al tiempo que proporciona un beneficio significativo.

usuario541686
fuente
Copiar siempre le permite eliminar la matriz interna. Reduce a la mitad el número de asignaciones de almacenamiento dinámico, ahorrando memoria en el caso común de cadenas cortas. También significa que no necesita saltar a través de una indirección adicional para cada acceso de personaje.
CodesInChaos
2
Creo que lo importante de esto es que Java realmente cambió de usar la misma base char[](con diferentes punteros al principio y al final) para crear una nueva String. Esto muestra claramente que el análisis de costo-beneficio debe mostrar una preferencia por la creación de uno nuevo String.
Filogenia
2

Ninguna de las respuestas aquí abordó "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 "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 a char*en unfixed declaración, el puntero apuntará a 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 P / Invoke a Win32 (u otras) 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 carácter", la regla dice que debes hacer una copia. Incluso si obtiene la subcadena al final, entonces no habría lugar para colocar la longitud sin corromper las otras variables.


A veces, sin embargo, realmente quieres hablar sobre "el medio de la cadena", y no necesariamente te importa el comportamiento P / Invoke. La ReadOnlySpan<T>estructura agregada recientemente 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);

los ReadOnlySpan<char> "subcadena" 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 / Invocar, entonces no hay mucha diferencia (a menos que la API a la que desea llamar no tenga unReadOnlySpan<char> sobrecarga).

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 stringexisten las mismas diferencias de .

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

bartonjs
fuente