java - studio - ¿Es realmente útil la internación de cadenas?

visual studio installer

Question

Hace un tiempo tuve una conversación sobre cadenas y varios idiomas, y surgió el tema de la internación de cadenas . Al parecer, Java y .NET Framework lo hacen automáticamente con todas las cadenas, así como con varios lenguajes de scripting. Teóricamente, ahorra memoria porque no terminas con varias copias de la misma cadena, y ahorra tiempo porque las comparaciones de igualdad de cadena son una simple comparación de puntero en lugar de una O (N) que recorre cada carácter de la cadena.

Pero cuanto más lo pienso, más escéptico crezco de los beneficios del concepto. Me parece que las ventajas son en su mayoría teóricas:

• En primer lugar, para utilizar el internado automático de cadenas, todas las cadenas deben ser inmutables, lo que hace que muchas de las tareas de procesamiento de cadenas sean más difíciles de lo que deberían ser. (Y sí, he escuchado todos los argumentos para la inmutabilidad en general. Ese no es el punto).
• Cada vez que se crea una nueva cadena, debe verificarse con la tabla de internación de cadenas, que es al menos una operación O (N). ( EDITAR: donde N es el tamaño de la cadena, no el tamaño de la tabla, ya que esto confunde a la gente). Por lo tanto, a menos que la proporción de comparaciones entre la igualdad de la cadena y la creación de una nueva cadena sea bastante alta, es poco probable que el tiempo neto ahorrado un valor positivo.
• Si la tabla de igualdad de cadenas utiliza referencias sólidas, las cadenas nunca se recogerán cuando ya no se necesiten, por lo que se perderá la memoria. Por otro lado, si la tabla utiliza referencias débiles, entonces la clase de cadena requiere algún tipo de finalizador para eliminar la cadena de la tabla, lo que ralentiza el proceso de GC. (Lo que podría ser bastante importante, dependiendo de cómo se implemente la tabla interna de cadena. En el peor de los casos, eliminar un elemento de una tabla hash puede requerir una reconstrucción O (N) de toda la tabla en determinadas circunstancias).

Esto es solo el resultado de mi pensamiento sobre los detalles de la implementación. ¿Hay algo que me haya perdido? ¿La internación de cadenas realmente proporciona algún beneficio significativo en el caso general?

EDIT 2: Muy bien, aparentemente estaba operando desde una premisa errónea. La persona con la que estaba hablando nunca señaló que la internación de cuerdas era opcional para las cuerdas recién creadas, y de hecho dio la fuerte impresión de que lo contrario era cierto. Gracias a Jon por arreglar el asunto. Otra respuesta aceptada para él.

Answer 1

¿La internación de cadenas realmente proporciona algún beneficio significativo en el caso general?

Sí. Es enorme. Pruébalo en java.

Escriba pruebas simples que comparen miles de cadenas semi-aleatorias para la igualdad con y sin internado.

a.equals( b )  is slow

a == b is fast.

Answer 2

En primer lugar, para utilizar el internado automático de cadenas, todas las cadenas deben ser inmutables, lo que hace que muchas de las tareas de procesamiento de cadenas sean más difíciles de lo que deberían ser. (Y sí, he escuchado todos los argumentos para la inmutabilidad en general. Ese no es el punto).

Esto es cierto y la cadena es inmutable en Java. No estoy seguro de si esto es algo malo. Sin entrar en inmutable y mutable, me gusta pensar que este es un gran diseño debido al almacenamiento en caché y mucha más simplicidad a la que no voy a entrar.

Cada vez que se crea una nueva cadena, debe verificarse con la tabla de internación de cadenas, que es al menos una operación O (N). Entonces, a menos que la proporción de comparaciones de igualdad de cadenas y creación de nuevas cadenas sea bastante alta, es poco probable que el tiempo neto ahorrado sea un valor positivo.

No es exactamente O (n). Puede hacer hashmaps y / u otras estructuras de datos que harán que esto se vea casi constantemente.

Si la tabla de igualdad de cadenas utiliza referencias sólidas, las cadenas nunca se recogerán cuando ya no se necesiten, por lo que se perderá la memoria. Por otro lado, si la tabla utiliza referencias débiles, entonces la clase de cadena requiere algún tipo de finalizador para eliminar la cadena de la tabla, lo que ralentiza el proceso de GC. (Lo que podría ser bastante importante, dependiendo de cómo se implemente la tabla interna de cadena. En el peor de los casos, eliminar un elemento de una tabla hash puede requerir una reconstrucción O (N) de toda la tabla en determinadas circunstancias).

Tienes razón en esto y estoy de acuerdo contigo. Excepto que siento que el procesamiento de GC y despreciable. Los beneficios a largo plazo son mucho más útiles que tener un recolector de basura haciendo una verificación adicional. No estoy seguro de lo que quiere decir sobre O (n) para eliminar de la tabla hash. La mayoría de las operaciones en tablas hash son O (1)

Así que en resumen, creo que su suposición de que la mayoría de las operaciones son lineales. Pero buscar cadenas está más cerca de un tiempo constante. Por lo tanto, este enfoque tendrá una pérdida de rendimiento despreciable pero una gran ganancia de memoria. Lo que yo diría que vale la pena.

Aquí hay una buena cita sobre lo que realmente está sucediendo y cómo se guarda la memoria.

Para ahorrar memoria (y acelerar las pruebas de igualdad), Java admite la "internación" de cadenas. Cuando se invoca el método intern () en una cadena, se realiza una búsqueda en una tabla de cadenas internas. Si un objeto de cadena con el mismo contenido ya está en la tabla, se devuelve una referencia a la cadena en la tabla. De lo contrario, la cadena se agrega a la tabla y se devuelve una referencia a ella.

Answer 3

Aquí está la documentation''s python:

sys.intern(string)

Introduzca la cadena en la tabla de cadenas "internadas" y devuelva la cadena internada, que es la cadena en sí misma o una copia. Las cadenas internas son útiles para obtener un poco de rendimiento en la búsqueda del diccionario: si las claves de un diccionario están internadas y la clave de búsqueda se internan, las comparaciones de claves (después del hashing) se pueden realizar mediante una comparación de puntero en lugar de una comparación de cadena. Normalmente, los nombres utilizados en los programas de Python se internan automáticamente, y los diccionarios que se utilizan para guardar los atributos de módulo, clase o instancia tienen claves internadas.

Las cuerdas internas no son inmortales; debe mantener una referencia al valor de retorno de intern () para beneficiarse de él.

Answer 4

El a.equals (b) es muy rápido para cadenas aleatorias. Es solo lento para cuerdas que son largas e iguales (o casi iguales)

Random rand = new Random(1);
String[] list = new String[2000];
for(int i=0;i<list.length;i++)
    list[i] = "1234567"+Long.toString(rand.nextInt(36*37), 36); // semi random
int count = 0;
long start = System.nanoTime();
for(int i=0;i<list.length;i++)
    for(int j=0;j<list.length;j++)
        if (list[i].equals(list[j]))
            count++;
long time = System.nanoTime() - start;
System.out.printf("The average time for equals() was %,d ns.%n", time/list.length/list.length);

en un portátil de 2,3 GHz se imprime

The average time for equals() was 19 ns.

Si internas () el primer valor y tienes que internar () un valor para hacer la comparación

       if (list[i] == list[j].intern())

huellas dactilares

The average time for equals() was 258 ns.

Este es un caso común ya que a menudo tiene un valor que sabe que está internado y un segundo que se ingresa y no se interna.

Si solo usa cadenas internas y ==, y no cuenta el costo, imprima

The average time for equals() was 4 ns.

Que es muchas veces más rápido si estás haciendo millones de comparación. Sin embargo, para una pequeña cantidad de comparaciones, está ahorrando 8 ns, pero podría costar 250 ns más.

Puede que sea más simple evitar intern () y usar equals ().

Answer 5

El internado de cadenas es útil cuando necesita comparar cadenas (1) de un conjunto finito (2) varias veces.

Luego, la sobrecarga de internar una cadena se ve contrarrestada por el beneficio de poder hacer un == rápido en lugar de equals() .

Hacer esto a veces puede ser más rápido que usar un HashMap , que se basa en las hashCode() y equals() .

Answer 6

Los puntos que enumeró son todos válidos hasta cierto punto. Pero hay importantes contra-argumentos.

1. La inmutabilidad es muy importante, especialmente si está utilizando mapas hash y se usan mucho.
2. De todos modos, las operaciones de composición de cadenas son muy lentas, ya que tienes que reasignar constantemente la matriz que contiene los caracteres.
3. Por otro lado, las operaciones subString() son muy rápidas.
4. La igualdad de cuerdas se usa mucho, y no estás perdiendo nada allí. La razón es que las cadenas no se internan automáticamente. De hecho, en Java, si las referencias son diferentes, equals() recurre a una comparación de carácter por carácter.
5. Claramente, el uso de referencias sólidas para la tabla de pasantes no es una buena idea. Tienes que vivir con los gastos generales de GC.
6. El manejo de cadenas de Java fue diseñado para ser eficiente en el espacio, especialmente en cadenas constantes y operaciones de subcadenas.

En general, diría que vale la pena en la mayoría de los casos y encaja bien con el concepto de montón administrado por VM. Aunque podría imaginar algunos escenarios especiales en los que podría ser un verdadero dolor.

Answer 7

No, Java y .NET no lo hacen "automáticamente con todas las cadenas". Ellos (bueno, Java y C #) lo hacen con expresiones de cadena constantes expresadas en bytecode / IL, y bajo demanda a través de los String.intern y String.Intern (.NET). La situación exacta en .NET es interesante, pero básicamente el compilador de C # garantizará que cada referencia a una constante de cadena igual dentro de un ensamblaje termine refiriéndose al mismo objeto de cadena. Esto se puede hacer de manera eficiente en el momento de la inicialización de tipo y puede ahorrar un montón de memoria.

No sucede cada vez que se crea una nueva cadena.

(En el frente de la inmutabilidad de las cuerdas, estoy muy contento de que las cuerdas sean inmutables. No quiero tener que tomar una copia cada vez que reciba un parámetro, etc., muchas gracias. No lo he visto hacer una cadena tareas de procesamiento más difíciles, ya sea ...)

Y como otros han señalado, buscar una cadena en una tabla hash no es generalmente una operación O (n), a menos que sea increíblemente desafortunado con las colisiones de hash ...

Personalmente no uso el internado de cadenas en el código de usuario-tierra; Si quiero algún tipo de caché de cadenas, crearé un HashSet<string> o algo similar. Esto puede ser útil en varias situaciones en las que espera encontrar las mismas cadenas varias veces (por ejemplo, nombres de elementos XML) pero con una colección simple no contamina un caché de todo el sistema.