¿Qué es un buen algoritmo para compactar registros en un archivo bloqueado?

Question

Supongamos que tiene un archivo grande formado por un grupo de bloques de tamaño fijo. Cada uno de estos bloques contiene cierto número de registros de tamaño variable. Cada registro debe encajar completamente dentro de un solo bloque y luego, por definición, tales registros nunca son más grandes que un bloque completo. Con el tiempo, los registros se agregan y eliminan de estos bloques a medida que los registros van y vienen de esta base de datos " " ;.

En algún momento, especialmente después de que quizás se agreguen muchos registros a la base de datos y se eliminen varios, muchos de los bloques pueden terminar parcialmente rellenos.

¿Qué es un buen algoritmo para barajar los registros en esta base de datos para compactar bloques innecesarios al final del archivo al rellenar mejor los bloques parcialmente rellenos?

Requisitos del algoritmo:

• La compactación debe ocurrir en lugar del archivo original sin extender temporalmente el archivo en más de unos pocos bloques a lo sumo desde su tamaño inicial
• El algoritmo no debe alterar innecesariamente los bloques que ya están completamente llenos
• Los bloques completos deben leerse o escribirse desde / al archivo a la vez y uno debe asumir que la operación de escritura es relativamente costosa
• Si los registros se mueven de un bloque a otro, deben agregarse a su nueva ubicación antes de que se eliminen de su posición inicial, de modo que, en caso de que se interrumpa la operación, no se pierdan registros como resultado de la falla " compactacion (Suponga que esta duplicación temporal de dichos registros puede detectarse en la recuperación).
• La memoria que se puede usar para esta operación solo puede ser del orden de varios bloques, lo que representa un porcentaje muy pequeño del tamaño total del archivo
• Suponga que los registros son del orden de 10 bytes a 1K bytes con un tamaño promedio de tal vez 100 bytes. Los bloques de tamaño fijo son del orden de 4 K u 8 K y el archivo es del orden de 1000 bloques.

Answer 1

Esto suena como una variación del problema de empaquetado de contenedores , pero donde ya tiene un Asignación inferior a la que desea mejorar. Por lo tanto, sugiero ver las variaciones de los enfoques que son exitosos para el problema del empaque de contenedores.

En primer lugar, es probable que desee parametrizar su problema definiendo lo que considera "suficientemente completo" (donde un bloque está lo suficientemente lleno para que no quieras tocarlo), y lo que está " demasiado vacío " (donde un bloque tiene tanto espacio vacío que tiene que tener más registros agregados). Luego, puede clasificar todos los bloques como lo suficientemente completos, demasiado vacíos o parcialmente llenos (aquellos que no están lo suficientemente completos ni demasiado vacíos). Luego, redefine el problema como la forma de eliminar todos los bloques demasiado vacíos creando tantos bloques completos como sea posible y minimizando el número de bloques parcialmente completos.

También querrá averiguar qué es más importante: obtener los registros en el menor número posible de bloques o empaquetarlos adecuadamente pero con la menor cantidad de bloques leídos y escritos.

Mi enfoque sería hacer una pasada inicial sobre todos los bloques, clasificarlos en una de las tres clases definidas anteriormente. Para cada bloque, también desea realizar un seguimiento del espacio libre disponible en él, y para los bloques demasiado vacíos, querrá tener una lista de todos los registros y sus tamaños. Luego, comenzando con los registros más grandes en los bloques demasiado vacíos, muévalos a los bloques parcialmente completos. Si desea minimizar las lecturas y escrituras, muévalas a cualquiera de los bloques que tenga actualmente en la memoria. Si desea minimizar el espacio desperdiciado, busque el bloque con la menor cantidad de espacio vacío que aún pueda contener el registro y lea el bloque si es necesario. Si ningún bloque retendrá el registro, cree un nuevo bloque. Si un bloque en la memoria alcanza el nivel " suficientemente completo " Umbral, escríbelo. Repita hasta que todos los registros en los bloques parcialmente rellenos se hayan colocado.

He omitido más de unos pocos detalles, pero esto debería darte una idea. Tenga en cuenta que el problema del empaquetado de contenedores es NP-hard , lo que significa que para aplicaciones prácticas, querrá decidir qué es lo más importante para usted, para que pueda elegir un enfoque que le brinde la mejor solución en un tiempo razonable.

Answer 2

Si no hay un ordenamiento para estos registros, simplemente llenaría los bloques desde el frente con los registros extraídos del último (s) bloque (es). Esto minimizará el movimiento de datos, es bastante simple y debería hacer un trabajo decente de empaquetar los datos firmemente.

Por ejemplo:

// records should be sorted by size in memory (probably in a balanced BST)
records = read last N blocks on disk;

foreach (block in blocks) // read from disk into memory
{
    if (block.hasBeenReadFrom())
    {
        // we read from this into records already
        // all remaining records are already in memory

        writeAllToNewBlocks(records);

        // this will leave some empty blocks on the disk that can either
        // be eliminated programmatically or left alone and filled during
        // normal operation

        foreach (record in records)
        {
            record.eraseFromOriginalLocation();
        }

        break;
    }

    while(!block.full())
    {
        moveRecords = new Array; // list of records we've moved

        size = block.availableSpace();
        record = records.extractBestFit(size);
        if (record == null)
        {
            break;
        }

        moveRecords.add(record);
        block.add(record);

        if (records.gettingLow())
        {
            records.readMoreFromDisk();
        }
    }

    if(moveRecords.size() > 0)
    {
        block.writeBackToDisk();
        foreach (record in moveRecords)
        {
            record.eraseFromOriginalLocation();
        }
    }
}

Actualización: me olvidé de mantener la regla de no bloquear solo en la memoria. He actualizado el pseudocódigo para solucionar este problema. También corregí un error en mi condición de bucle.

Answer 3

Una modificación de un espacio en línea (para desfragmentar en una pasada) delimitado (los requisitos de memoria) podría funcionar aquí.

Consulte " Algoritmos de aproximación del empaque de contenedores: Análisis combinatorio " por Coffman et al.

Answer 4

Aquí hay un algoritmo que puede aprovechar, aunque sus registros dentro de bloques de tamaño fijo pueden requerir un poco más de trabajo.

Desfragmentación del montón en tiempo limitado