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


Answers

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.

Question

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?




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.






Links