c# - ¿Cuánto crecer un búfer en un módulo C similar a StringBuilder?
java (7)
¿Alguien sabe lo que hace Java o C # bajo el capó?
Eche un vistazo al siguiente enlace para ver cómo se hace en StringBuilder de Java desde JDK7, en particular, el método expandCapacity. http://hg.openjdk.java.net/build-infra/jdk7/jdk/file/0f8da27a3ea3/src/share/classes/java/lang/AbstractStringBuilder.java
En C, estoy trabajando en una "clase" que administra un búfer de bytes, lo que permite agregar datos arbitrarios al final. Ahora estoy buscando el cambio de tamaño automático a medida que la matriz subyacente se llena usando llamadas a realloc . Esto debería tener sentido para cualquiera que haya usado Java o C # StringBuilder . Entiendo cómo hacer para cambiar el tamaño. Pero, ¿alguien tiene alguna sugerencia, con las razones proporcionadas, sobre cuánto crecer el búfer con cada tamaño?
Obviamente, se debe hacer una compensación entre el espacio desperdiciado y las llamadas de reasignación excesivas (lo que podría llevar a una copia excesiva). He visto algunos tutoriales / artículos que sugieren duplicar. Eso parece un desperdicio si el usuario logra proporcionar una buena conjetura inicial. ¿Vale la pena intentar redondear a una potencia de dos o un múltiplo del tamaño de alineación en una plataforma?
¿Alguien sabe lo que hace Java o C # bajo el capó?
Cuando trabaje con expandir y contraer buffers, la propiedad clave que desea es aumentar o disminuir por un múltiplo de su tamaño, no por una diferencia constante.
Considere el caso en el que tiene una matriz de 16 bytes, aumentar su tamaño en 128 bytes es una exageración; sin embargo, si en cambio tuvieras una matriz de 4096 bytes y la incrementaras solo en 128 bytes, terminarías copiando mucho.
Me enseñaron a siempre doblar o reducir a la mitad las matrices. Si realmente no tiene ninguna pista sobre el tamaño o el máximo, multiplicar por dos garantiza que tenga mucha capacidad durante mucho tiempo y, a menos que esté trabajando en un sistema con recursos limitados, no es suficiente asignar el doble del espacio. demasiado terrible Además, mantener las cosas en potencias de dos puede permitirle usar cambios de bits y otros trucos, y la asignación subyacente suele estar en potencias de dos.
En C #, la estrategia utilizada para aumentar el búfer interno utilizado por un StringBuilder ha cambiado con el tiempo.
Existen tres estrategias básicas para resolver este problema, y tienen diferentes características de rendimiento.
La primera estrategia básica es:
- Hacer una matriz de caracteres
- Cuando te quedes sin espacio, crea una nueva matriz con k más caracteres, para alguna constante k.
- Copie la matriz anterior a la nueva matriz y deje huérfana la matriz antigua.
Esta estrategia tiene varios problemas, el más obvio de los cuales es que es O (n 2 ) en el tiempo si la cadena que se está construyendo es extremadamente grande. Digamos que k es un millar de caracteres y la cadena final es un millón de caracteres. ¡Usted termina reasignando la cadena a 1000, 2000, 3000, 4000, ... y por lo tanto copiando 1000 + 2000 + 3000 + 4000 + ... + 999000 caracteres, que suma en el orden de 500 mil millones de caracteres copiados!
Esta estrategia tiene la buena propiedad de que la cantidad de memoria "desperdiciada" está delimitada por k.
En la práctica, esta estrategia rara vez se usa debido a ese problema de n cuadrado.
La segunda estrategia básica es
- Hacer una matriz
- Cuando se quede sin espacio, cree una nueva matriz con k% más caracteres, para alguna constante k.
- Copie la matriz anterior a la nueva matriz y deje huérfana la matriz antigua.
El k% suele ser del 100%; si es así, esto se llama la estrategia "doble cuando está lleno".
Esta estrategia tiene la propiedad agradable de que su costo amortizado es O (n). Supongamos que nuevamente la cadena final es un millón de caracteres y comienzas con mil. Realiza copias a 1000, 2000, 4000, 8000, ... y termina copiando 1000 + 2000 + 4000 + 8000 ... + 512000 caracteres, que suma aproximadamente un millón de caracteres copiados; mucho mejor.
La estrategia tiene la propiedad de que el costo amortizado es lineal, independientemente del porcentaje que elija.
Esta estrategia tiene el inconveniente de que, a veces, una operación de copia es extremadamente costosa , y puede estar desperdiciando hasta un k% de la longitud de la cadena final en la memoria no utilizada .
La tercera estrategia es hacer una lista enlazada de matrices, cada matriz de tamaño k. Cuando se desborda una matriz existente, se asigna una nueva y se agrega al final de la lista.
Esta estrategia tiene la buena propiedad de que ninguna operación es particularmente costosa, la memoria desperdiciada total está delimitada por k, y no es necesario poder ubicar bloques grandes en el montón de forma regular. Tiene el inconveniente de que, finalmente, convertir la cosa en una cadena puede ser costoso, ya que los arreglos en la lista enlazada pueden tener una mala ubicación.
El generador de cadenas en el marco .NET solía usar una estrategia double-when-full; ahora usa una estrategia de lista de bloques enlazada.
Es específico de la implementación, de acuerdo con la documentación , pero comienza con 16:
La capacidad predeterminada para esta implementación es 16, y la capacidad máxima predeterminada es Int32.MaxValue.
Un objeto StringBuilder puede asignar más memoria para almacenar caracteres cuando se amplía el valor de una instancia y la capacidad se ajusta en consecuencia. Por ejemplo, los métodos Anexar, Anexar Formato, Garantía de Capacidad, Insertar y Reemplazar pueden aumentar el valor de una instancia.
La cantidad de memoria asignada es específica de la implementación, y se lanza una excepción (ya sea ArgumentOutOfRangeException o OutOfMemoryException) si la cantidad de memoria requerida es mayor que la capacidad máxima.
Basado en otras cosas del marco .NET, sugeriría multiplicarlo por 1.1 cada vez que se alcance la capacidad actual. Si se necesita espacio adicional, solo tiene un equivalente a EnsureCapacity de EnsureCapacity que lo expandirá al tamaño necesario manualmente.
La lista en .NET framework usa este algoritmo: si se especifica la capacidad inicial, crea un búfer de este tamaño; de lo contrario, no se asigna ningún búfer hasta que se agregan los primeros elementos, lo que asigna un espacio igual al número de elementos agregados, pero no menos de 4. Cuando se necesita más espacio, asigna un nuevo búfer con una capacidad anterior 2x y copia todos los elementos del búfer anterior al nuevo búfer. Anteriormente, StringBuilder usaba un algoritmo similar.
En .NET 4, StringBuilder asigna el búfer inicial de tamaño especificado en el constructor (el tamaño predeterminado es de 16 caracteres). Cuando el búfer asignado es demasiado pequeño, no se realiza ninguna copia. En su lugar, llena el búfer actual hasta el borde, luego crea una nueva instancia de StringBuilder, que asigna un búfer de tamaño * MAX (length_of_remaining_data_to_add, MIN (length_of_all_previous_buffers, 8000)) por lo que al menos todos los datos restantes se ajustan al nuevo búfer y al tamaño total de todos los buffers al menos se duplica. El nuevo StringBuilder mantiene la referencia al StringBuilder antiguo y, por lo tanto, las instancias individuales crean una lista enlazada de búferes.
Por lo general, desea mantener el factor de crecimiento un poco más pequeño que la media de oro (~ 1.6). Cuando es más pequeño que la media dorada, los segmentos descartados serán lo suficientemente grandes para satisfacer una solicitud posterior, siempre que estén adyacentes entre sí. Si su factor de crecimiento es mayor que la media de oro, eso no puede suceder.
Descubrí que reducir el factor a 1.5 todavía funciona bastante bien, y tiene la ventaja de ser fácil de implementar en enteros matemáticos ( size = (size + (size << 1))>>1; - con un compilador decente puede escribir eso como (size * 3)/2 , y aún debería compilarse en código rápido).
Me parece recordar una conversación hace unos años en Usenet, en la que PJ Plauger (o tal vez fue Pete Becker) de Dinkumware, diciendo que habrían realizado pruebas más extensas que nunca, y llegaron a la misma conclusión (así, para Por ejemplo, la implementación de std::vector en su biblioteca estándar de C ++ usa 1.5).
Traducir esto a C.
Probablemente mantendré una List<List<string>> lista.
class StringBuilder
{
private List<List<string>> list;
public Append(List<string> listOfCharsToAppend)
{
list.Add(listOfCharsToAppend);
}
}
De esta manera, usted simplemente mantiene una lista de Listas y asigna memoria a pedido en lugar de asignar memoria con mucha antelación.