¿Por qué no podemos insertar en archivos sin las escrituras adicionales? (No me refiero a añadir, ni sobrescribir)

7

Esto me ocurre como un problema independiente del lenguaje de programación.

Tengo un archivo con el contenido

aaabddd

Cuando quiero insertar C detrás de b , entonces mi código necesita volver a escribir ddd para obtener

aaabCddd

¿Por qué no puedo simplemente insertar C en esta posición?

No puedo hacer esto en Java, Python, .... No puedo hacer esto en Linux, Windows, .... Estoy en lo correcto?

No entiendo por qué C no se puede insertar sin las escrituras adicionales. ¿Podría alguien explicar por qué esto es así?

    
pregunta User 29.04.2014 - 19:57

7 respuestas

6

Dado que la mayoría de los sistemas de archivos almacenan el contenido de los archivos en bloques individuales que no son necesariamente contiguos en el disco físico, pero están vinculados mediante estructuras de puntero, parece que este modo: "insertar" en lugar de "anexar" o "sobrescribir" "- debería ser posible, y ciertamente podría hacerse más eficiente de lo que tenemos que hacer ahora: leer todo el contenido, editar el flujo de bytes y volver a escribir todo el contenido.

Sin embargo, para bien o para mal, la semántica de los sistemas de archivos de UNIX se diseñó de acuerdo con el paradigma "simple y áspero" de la década de 1970: le permite hacer todo, pero no necesariamente de la manera más eficiente posible. Hoy en día es casi impensable introducir un nuevo modo de apertura de archivos en la capa del Sistema de archivos virtuales y tener alguna esperanza de que los principales sistemas de archivos adopten la compatibilidad con ellos. Este es un motivo favorito para mí, pero lamentablemente uno no se resolverá pronto.

    
respondido por el Kilian Foth 29.04.2014 - 20:07
10

En teoría, puedes implementar un archivo que permita este tipo de cosas. Sin embargo, para obtener la máxima flexibilidad, debe almacenar un puntero al siguiente byte junto con cada byte en el archivo. Suponiendo un puntero de 64 bits, eso significaría que 8 de cada 9 bytes de su archivo se compondrían de punteros internos. Por lo tanto, se necesitarían 9000 bytes de espacio para almacenar 1000 bytes de datos reales. La lectura del archivo también sería lenta, ya que necesitaría leer cada byte, leer el puntero, seguir el puntero para leer el siguiente byte, etc. en lugar de leer grandes bloques contiguos de datos del disco.

Obviamente, este tipo de enfoque no es práctico. Sin embargo, podría dividir el archivo en, por ejemplo, bloques de 32 kb. Eso haría relativamente fácil agregar 32 kb de datos en cualquier límite de 32 kb en el archivo. No sería más fácil agregar un solo byte como el quinto byte del archivo. Sin embargo, si reserva algo de espacio libre en cada bloque, podría permitir que se realicen pequeñas adiciones de datos que solo afecten a los datos en ese bloque único. Tendría una penalización en términos de tamaño de archivo, por supuesto, pero potencialmente razonable. Sin embargo, determinar cuánto espacio reservar y cómo dividir los bloques tiende a ser mucho más fácil para una aplicación en particular que para un sistema de propósito general. Lo que funciona en un contexto puede ser muy malo en otro, dependiendo del acceso al archivo y características de modificación.

De hecho, muchos sistemas que pasan mucho tiempo interactuando con archivos implementan algo como lo que he descrito anteriormente cuando implementan su abstracción de archivo en particular. Las bases de datos, por ejemplo, generalmente implementarán algún concepto de "bloque" como la unidad más pequeña de E / S con la que pueden trabajar y generalmente reservarán una cantidad de espacio para el crecimiento futuro, de modo que la actualización de una fila en una tabla solo afecta la un bloque en el que se almacenan los datos en lugar de volver a escribir todo el archivo. Por supuesto, diferentes bases de datos tienen diferentes implementaciones con diferentes compromisos.

    
respondido por el Justin Cave 29.04.2014 - 20:25
8

El "problema" se reduce a cómo se escriben los archivos en el medio de almacenamiento byte a byte.

En su representación más básica, un archivo no es más que una serie de bytes escritos en el disco (también conocido como medio de almacenamiento). Así que su cadena original se ve como:

Address  Value
0x00     'a'
0x01     'a'
0x02     'a'
0x03     'b'
0x04     'd'
0x05     'd'
0x06     'd'

Y desea insertar C en la posición 0x04. Eso requiere desplazar los bytes 4 - 6 hacia abajo un byte para que pueda insertar el nuevo valor. Si no lo haces, sobrescribirás el valor que actualmente está en 0x04, que no es lo que quieres.

Address  Value
0x00     'a'
0x01     'a'
0x02     'a'
0x03     'b'
0x04     'C'
0x05     'd'
0x06     'd'
0x07     'd'

Entonces, la razón por la que tiene que volver a escribir la cola del archivo después de insertar un nuevo valor es porque no hay espacio dentro del archivo para aceptar el valor insertado. De lo contrario, sobreescribiría lo que había allí.

Addendum 1 : si desea reemplazar el valor de b con C , entonces no necesita volver a escribe la cola de la cuerda. Reemplazar un valor con un tamaño similar no requiere una reescritura.

Addendum 2 : si quisiera reemplazar la cadena ab con C , entonces necesitaría reescribir el resto del archivo a medida que ' He creado un hueco en el archivo.

Addendum 3 : las construcciones a nivel de bloque se crearon para facilitar el manejo de archivos grandes. En lugar de tener que encontrar 1M de espacio contiguo para su archivo, ahora solo necesita encontrar 1M de bloques disponibles para escribir.

En teoría, podrías construir un sistema de archivos que hiciera un enlace byte por byte similar a lo que proporcionan los bloques. A continuación, puede insertar un nuevo byte actualizando el | De los punteros en el punto apropiado. Me atrevería a suponer que el rendimiento sería bastante bajo.

Como Sugerido por el Gran Maestro B , use una imagen de dominós apilados para comprender visualmente cómo se representa el archivo.

No puedes insertar otro dominó dentro de la línea de dominó sin que todo se caiga. Tienes que crear el espacio para el nuevo dominó moviendo los otros hacia abajo en la línea. Mover dominós en la línea equivale a volver a escribir la cola del archivo después del punto de inserción.

    
respondido por el GlenH7 29.04.2014 - 20:33
1

La forma más eficiente de insertar un bloque de bytes en medio de un archivo sería:

  1. Asigna el archivo a la memoria
  2. Agregue los bytes al final de la imagen de memoria del archivo
  3. Rote estos archivos en su lugar (con un algoritmo estándar disponible en la Biblioteca Estándar de C ++, por ejemplo)
  4. Deje que el sistema operativo se encargue de escribir bloques sucios en el disco
respondido por el Laurent LA RIZZA 25.09.2015 - 15:05
0

Primero debe leer todo después del punto de inserción y luego volver a escribirlo por todo el espacio que va a insertar. Luego puede escribir sus datos de "inserción" en el lugar correcto. Funcionamiento de rendimiento extremadamente pobre, por lo tanto, no se admite de forma nativa.

    
respondido por el Brian Knoblauch 29.04.2014 - 20:05
0

La inserción en un archivo no se implementa en la mayoría de los sistemas de archivos porque se considera una operación "costosa" (que consume tiempo y que consume espacio) con posibles repercusiones "costosas" a largo plazo y modos de falla adicionales.

Un sistema de archivos con semántica de inserción probablemente usaría shift & insert (potencialmente muy costoso cuando se inserta en la parte delantera de un archivo grande, pero no / pocos efectos secundarios a largo plazo) o algún tipo de asignación de pila generalizada con asignación de longitud variable tamaños (rendimiento de muy mal comportamiento en algunos casos [imagina las caras de los usuarios interactivos si intentan guardar un archivo durante un GC del mundo sin parar!]).

Si desea experimentar, puede crear fácilmente una abstracción de E / S de archivos en Java o Python que implemente la inserción. Si tiene éxito y tiene características de rendimiento de buen comportamiento, tiene la base para un excelente trabajo de investigación. Buena suerte.

    
respondido por el Scott Leadley 29.04.2014 - 21:14
-1

Cuando haces acceso directo a un archivo, estás usando un nivel bajo que se puede usar para construir estructuras más sofisticadas. Considere construir una base de datos con sus datos que permita los tipos de acceso que necesita, incluida la inserción.

Sería menos costoso si solo necesita recorrer el archivo para no realizar accesos aleatorios a un desplazamiento específico. Si necesita acceso aleatorio por desplazamiento en el archivo, deberá actualizar el índice para todos los bytes más allá del punto de inserción.

En general, pagará en la indexación de las estructuras de datos, la memoria para almacenar el índice y los accesos de disco adicionales para actualizarlo.

    
respondido por el Patricia Shanahan 29.04.2014 - 21:07

Lea otras preguntas en las etiquetas