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



2 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) 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.

c# .net string substring time-complexity

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 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.




Related