El mejor enfoque para guardar grandes documentos editables en la memoria

StackOverflow https://stackoverflow.com/questions/838712

Pregunta

Necesito mantener una representación de un documento en la memoria, y estoy buscando la forma más eficiente de hacerlo.

Suposiciones

  • Los documentos pueden ser bastante grandes, arriba a 100 MB.
  • La mayoría de las veces el documento permanecerá sin cambios - (es decir, no querer hacer innecesaria por adelantado procesamiento).
  • Los cambios generalmente serán bastante cercanos entre sí en el documento (es decir, como los tipos de usuario).
  • Debería ser posible aplicar los cambios rápidamente (sin copiar todo el documento)
  • Los cambios se aplicarán en términos de compensaciones y texto nuevo / eliminado (no como línea / col).
  • Para trabajar en C #

Consideraciones actuales

  • Almacenar los datos como una cadena. Facil de código, rápido de configurar, muy lento para actualización.
  • Matriz de líneas, moderadamente fácil de codificar, más lenta de configurar (ya que tenemos que analizar la cadena en líneas), más rápida de actualizar (ya que podemos insertar líneas de eliminación fácilmente, pero encontrar compensaciones requiere sumar longitudes de línea).

Debe haber una carga de algoritmos estándar para este tipo de cosas (no es un millón de millas de asignación y fragmentación del disco).

Gracias por tus pensamientos.

¿Fue útil?

Solución

Sugeriría dividir el archivo en bloques. Todos los bloques tienen la misma longitud cuando los carga, pero la longitud de cada bloque puede cambiar si el usuario edita estos bloques. Esto evita mover 100 megabytes de datos si el usuario inserta un byte en el frente.

Para administrar los bloques, solo ellos, junto con el desplazamiento de cada bloque, en una lista. Si el usuario modifica la longitud de un bloque, solo debe actualizar los desplazamientos de los bloques después de este. Para encontrar un desplazamiento, puede usar la búsqueda binaria.

Tamaño de archivo: 100 MiB
Tamaño de bloque: 16 kiB
Bloques: 6400

Búsqueda de un desplazamiento mediante búsqueda binaria (peor de los casos): 13 pasos
Modificación de un bloque (peor de los casos): copie datos de 16384 bytes y actualice las compensaciones de bloque de 6400
Modificación de un bloque (caso promedio): copie datos de 8192 bytes y actualice 3200 compensaciones de bloque

El tamaño de bloque de 16 kiB es solo un ejemplo aleatorio: puede equilibrar los costos de las operaciones eligiendo el tamaño de bloque, tal vez en función del tamaño del archivo y la probabilidad de las operaciones. Hacer algunas matemáticas simples producirá el tamaño de bloque óptimo.

La carga será bastante rápida, ya que carga bloques de tamaño fijo, y guardar también debería funcionar bien, ya que tendrá que escribir unos pocos miles de bloques y no millones de líneas individuales. Puede optimizar la carga cargando bloques solo bajo demanda y puede optimizar el ahorro guardando solo todos los bloques que cambiaron (contenido o desplazamiento).

Finalmente, la implementación no será demasiado difícil también. Puede usar la clase StringBuilder para representar un bloque. Pero esta solución no funcionará bien para líneas muy largas con longitudes comparables al tamaño del bloque o más grandes porque tendrá que cargar muchos bloques y mostrar solo algunas partes pequeñas con el resto a la izquierda o derecha de la ventana. Supongo que tendrá que usar un modelo de partición bidimensional en este caso.

Otros consejos

Good Math, Bad Math escribió un excelente artículo sobre cuerdas y espacio intermedio Hace un tiempo que detalla los métodos estándar para representar archivos de texto en un editor de texto, e incluso los compara para simplificar la implementación y el rendimiento. En pocas palabras: un búfer de espacio (una matriz de caracteres grande con una sección vacía inmediatamente después de la posición actual del cursor) es su mejor y más simple apuesta.

Puede encontrar este documento útil --- Estructuras de datos para secuencias de texto que describe y analiza experimentalmente algunos algoritmos estándar, y compara [entre otras cosas] buffers gap y tablas de piezas.

FWIW, concluye que las tablas de piezas son ligeramente mejores en general; aunque net.wisdom parece preferir espacios intermedios.

Usaría un b-tree o una lista de líneas omitidas, o bloques más grandes si no va a editar mucho.

No tiene mucho costo adicional para determinar los extremos de la línea en la carga, ya que de todos modos tiene que visitar cada personaje al cargar.

Puede mover líneas dentro de un nodo sin mucho esfuerzo.

La longitud total del texto en cada nodo se almacena en el nodo y los cambios se propagan hasta los nodos principales.

Cada línea está representada por una matriz de datos, y comienza el índice, la longitud y la capacidad. Los saltos de línea / retornos de carro no se colocan en la matriz de datos. Las operaciones comunes, como las líneas de división, solo requieren cambios en las referencias en la matriz; la edición de líneas requiere una copia si se excede la capacidad. Se puede usar una estructura similar por línea temporalmente al editar esa línea, por lo que no realiza una copia cada vez que presiona una tecla.

Fuera de mi cabeza, hubiera pensado que una lista vinculada indexada sería bastante eficiente para este tipo de cosas a menos que tenga algunas muy líneas largas.

La lista vinculada le daría una manera eficiente de almacenar los datos y agregar o eliminar líneas a medida que el usuario edita. La indexación le permite saltar rápidamente a un punto particular en su archivo. Este tipo de idea también se presta bien para deshacer / rehacer operaciones de tipo, ya que debería ser razonablemente fácil clasificar las ediciones en pequeñas operaciones atómicas.

Sin embargo, estoy de acuerdo con el punto de crisb, probablemente es mejor hacer que algo simple funcione primero y luego ver si realmente es lento ...

Según su descripción, parece que su documento es solo texto sin formato, por lo que un generador de cadenas funcionaría bien.

Si se trata de un documento formateado, me inclinaría a utilizar las API de MS Word o similar y simplemente descargar el procesamiento de su documento a ellos, le ahorrará muchísimo tiempo, ya que el análisis de documentos a menudo puede ser un problema en el a * * :-)

Todavía no me preocuparía demasiado el rendimiento; parece que todavía no ha implementado uno, por lo que tampoco sabe qué características de rendimiento tiene el resto de su aplicación; puede ser que usted en realidad no puede permitirse el lujo de mantener múltiples documentos en la memoria cuando realmente tiene la oportunidad de perfilarlo.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top