Representaciones de cadena: ¿mejoras sobre cuerdas?

Question

Quiero una representación de cadenas con operaciones rápidas de concatenación y edición. He leído el documento "Ropes: an Alternative to Strings", pero ¿ha habido alguna mejora significativa en esta área desde 1995?

EDITAR: Una posibilidad que he considerado antes es usar un 2-3 finger tree con cadenas como hojas, pero no he hecho un análisis detallado de esto; esto da suma/eliminación amortiguada de tiempo constante en los extremos y concatenación logarítmica (en el número de fragmentos de la cadena más pequeña), a diferencia de viceversa para cuerdas.

Answer 1

¡Esta es una vieja pregunta! Me pregunto si alguien lee esto. Pero aún así es intrigante. En sus comentarios, que dicen que usted busca:

más rápido asintótica, o constantes factores, o un menor uso de memoria

Bueno, cuerdas tienen O (1) de inserción, y O (n) iteración. No puedes hacer nada mejor que eso. Las subcadenas e indexación obviamente serán más costosas. Pero la mayoría de los casos de uso para documentos grandes no requieren edición o acceso aleatorio. Si solo concatenas al final, un vector 1D/lista de cadenas podría mejorar la constante de tiempo de inserción. Solía ​​usar esto en JavaScript porque tenía una concatenación de cadenas tan lenta.

Se dice que la representación de la memoria es menos eficiente que el uso de cadenas. Dudo que: si trabaja en un idioma que tiene recolección de basura, la cuerda le permite usar la misma instancia de fragmento de cadena en varios lugares. En una cuerda que representa un documento HTML, habrá muchos elementos DIV, SPAN y LINK. Esto podría suceder automáticamente suponiendo que estas etiquetas son constantes de tiempo de compilación, y las agrega a la cuerda directamente. Incluso para frases tan cortas, el documento de cuerda se reducirá significativamente en tamaño, en el mismo orden de magnitud que la cuerda original. Cadenas más largas producirán una ganancia neta.

Si también hace que el elemento árbol sea de solo lectura, puede crear subropes (frases más largas expresadas como cuerdas), que ocurren varias veces o se comparten a través de cadenas basadas en cuerdas. La desventaja de este intercambio es que tales secciones de cable de fragmentos no se pueden cambiar: para editarlas, o para equilibrar el árbol, necesita copiar el gráfico de objetos. Pero eso no importa si en su mayoría se concatenan e iteran. En un servidor web, puede mantener un subroyecto que representa la declaración de hojas de estilo CSS que se comparte en todos los documentos HTML servidos por ese servidor.