c# - how - stringbuilder net
¿Existe algún escenario en el que la estructura de datos de Rope sea más eficiente que un generador de cadenas? (5)
Relacionado con esta pregunta , basado en un comentario del usuario Eric Lippert .
¿Existe algún escenario en el que la estructura de datos de Rope sea más eficiente que un generador de cadenas? Algunas personas opinan que las estructuras de datos de cuerdas casi nunca son mejores en términos de velocidad que las operaciones del generador de cadenas nativas en casos típicos, por lo que tengo curiosidad por ver escenarios realistas donde las cuerdas son mejores.
La documentación para la implementación de SGI C ++ entra en algunos detalles sobre los comportamientos de la O grande y los factores constantes que son instructivos.
Su documentación asume que las cadenas son muy largas , los ejemplos presentados para referencia hablan de 10 MB de cadenas . Se escribirán muy pocos programas que traten tales cosas y, para muchas clases de problemas con tales requisitos, volverlos a trabajar para que estén basados en la transmisión en lugar de requerir que la cadena completa esté disponible cuando sea posible dará lugar a resultados significativamente superiores. Como tales cuerdas son para la manipulación sin transmisión de secuencias de caracteres de varios megabytes cuando puede tratar adecuadamente la cuerda como secciones (ellas mismas cuerdas) en lugar de solo una secuencia de caracteres.
Ventajas significativas:
- La concatenación / inserción se convierten en operaciones de tiempo casi constantes.
- Ciertas operaciones pueden reutilizar las secciones de cuerda anteriores para permitir compartir en la memoria.
- Tenga en cuenta que las cadenas .Net, a diferencia de las cadenas Java, no comparten el búfer de caracteres en las subcadenas, una opción con ventajas y desventajas en términos de huella de memoria. Las cuerdas tienden a evitar este tipo de problemas.
- Las cuerdas permiten la carga diferida de las subcadenas hasta que se requiera
- Tenga en cuenta que es difícil hacerlo bien, es muy fácil dejarlo sin sentido debido al excesivo afán de acceso y requiere código de consumo para tratarlo como una cuerda, no como una secuencia de caracteres.
Contras significativas:
- El acceso de lectura aleatoria se convierte en O (log n)
- Los factores constantes en el acceso de lectura secuencial parecen estar entre 5 y 10
- el uso eficiente de la API requiere tratarlo como una cuerda, no solo caer en una cuerda como una implementación de respaldo en la cadena de caracteres "normal".
Esto lleva a algunos usos "obvios" (el primero mencionado explícitamente por SGI).
- Edite búferes en archivos grandes que permiten deshacer / rehacer fácilmente
- Tenga en cuenta que, en algún momento, es posible que deba escribir los cambios en el disco, lo que implica la transmisión a través de toda la cadena, por lo que esto solo es útil si la mayoría de las ediciones residen principalmente en la memoria en lugar de requerir persistencia frecuente (por ejemplo, a través de una función de guardado automático)
- Manipulación de segmentos de ADN donde se produce una manipulación significativa, pero en realidad ocurre muy poca producción
- Algoritmos multihilo que mutan subsecciones locales de cadena. En teoría, estos casos pueden dividirse en hilos y núcleos separados sin necesidad de tomar copias locales de las subsecciones y luego combinarlas, ahorrando una gran cantidad de memoria y evitando una operación de combinación en serie costosa al final.
Hay casos en los que el comportamiento específico del dominio en la cadena se puede acoplar con aumentos relativamente simples a la implementación de Rope para permitir:
- Las cadenas de solo lectura con un número significativo de subcadenas comunes son susceptibles de internamiento simple para ahorros significativos de memoria.
- Las cadenas con estructuras dispersas, o repetición local significativa son susceptibles de ejecutar la codificación de longitud mientras que aún permiten niveles razonables de acceso aleatorio.
- Donde los límites de las cadenas secundarias son, en sí mismos, "nodos" donde se puede almacenar la información, aunque estas estructuras se pueden hacer mejor como un Trix de Radix si rara vez se modifican pero a menudo se leen.
Como puede ver en los ejemplos enumerados, todos caen bien en la categoría ''nicho''. Además, varios pueden tener alternativas superiores si está dispuesto / es capaz de reescribir el algoritmo como una operación de procesamiento de flujo en su lugar.
La mayoría de los editores de texto avanzados representan el cuerpo del texto como un "tipo de cuerda" (aunque en la implementación, las hojas no suelen ser caracteres individuales, sino que el texto se ejecuta), principalmente para mejorar las inserciones y eliminaciones frecuentes en textos grandes.
En general, StringBuilder está optimizado para agregarse e intenta minimizar el número total de reasignaciones sin tener que ubicar demasiado. La garantía típica es (log2 N asignaciones, y menos de 2.5 veces la memoria). Normalmente, la cadena se construye una vez y luego se puede usar durante bastante tiempo sin ser modificada.
La cuerda está optimizada para inserciones y eliminaciones frecuentes, y trata de minimizar la cantidad de datos copiados (por un mayor número de asignaciones). En una implementación de búfer lineal, cada inserción y eliminación se convierte en O (N), y generalmente tiene que representar inserciones de un solo carácter.
La respuesta corta a esta pregunta es sí, y eso requiere poca explicación. Por supuesto, hay situaciones en las que la estructura de datos de Rope es más eficiente que un generador de cadenas. Funcionan de manera diferente, por lo que son más adecuados para diferentes propósitos.
(Desde una perspectiva C #)
La estructura de datos de la cuerda como un árbol binario es mejor en ciertas situaciones. Cuando observa valores de cadena extremadamente grandes (piense en más de 100 MB de xml provenientes de SQL), la estructura de datos de cuerda podría mantener todo el proceso fuera del montón de objetos grandes, donde el objeto de cadena lo golpea cuando pasa 85000 bytes.
Si está buscando cadenas de 5-1000 caracteres, probablemente no mejore el rendimiento lo suficiente como para que valga la pena. Este es otro caso de una estructura de datos que está diseñada para el 5% de las personas que tienen una situación extrema.
Las máquinas virtuales de Javascript a menudo usan cuerdas para cadenas.
Maxime Chevalier-Boisvert, desarrollador de Higgs Javascript VM, says :
En JavaScript, puede usar matrices de cadenas y, finalmente, Array.prototype.join para hacer que la concatenación de cadenas sea razonablemente rápida, O (n), pero la forma "natural" en que los programadores de JS tienden a construir cadenas es simplemente agregarlas con el operador + = construirlos incrementalmente. Las cadenas JS son inmutables, por lo que si no se optimizan internamente, el agregado incremental es O (n2). Creo que es probable que las cuerdas se implementaran en los motores JS específicamente debido a los puntos de referencia de SunSpider que añaden cadenas. Los implementadores de motores JS utilizaron cuerdas para obtener una ventaja sobre otros al hacer que algo que antes era lento, más rápido. Si no fuera por esos puntos de referencia, creo que los gritos de la comunidad sobre el funcionamiento deficiente de las cadenas podrían haberse producido con "use Array.prototype.join, dummy!"
El 10º Concurso de Programación ICFP se basó , básicamente, en personas que utilizan la estructura de datos de cuerda para una resolución eficiente. Ese fue el gran truco para conseguir una máquina virtual que funcionara en un tiempo razonable.
La cuerda es excelente si hay muchos prefijos (aparentemente, la palabra "prependir" está compuesta por gente de TI y no es una palabra adecuada) y potencialmente mejor para las inserciones; Los StringBuilders usan memoria continua, por lo que solo funcionan de manera eficiente para agregar.
Por lo tanto, StringBuilder es ideal para construir cadenas agregando fragmentos, un caso de uso muy normal. Como los desarrolladores necesitan hacer esto mucho, los StringBuilders son una tecnología muy común.
Las cuerdas son excelentes para los buffers de edición, por ejemplo, la estructura de datos detrás de, por ejemplo, un TextArea de solidez empresarial. Por lo tanto (una relajación de Ropes, por ejemplo, una lista de líneas vinculadas en lugar de un árbol binario) es muy común en el mundo de los controles de UI, pero eso no suele estar expuesto a los desarrolladores y usuarios de esos controles.
Realmente se necesitan grandes cantidades de datos y una rotación para realizar el pago de la cuerda: los procesadores son muy buenos para las operaciones de transmisión, y si tiene la RAM, entonces la reasignación de prefijos funciona de manera aceptable para los casos de uso normales. Esa competencia mencionada en la parte superior fue la única vez que la vi que necesitaba.