Was ist ein guter Algorithmus für die Datensätze in einer gesperrten Datei Verdichten?

Question

Angenommen, Sie eine große Datei aus einer Reihe von Blöcken fester Größe gemacht haben. Jeder dieser Blöcke enthält eine Anzahl von variabler Größe Aufzeichnungen. Jeder Datensatz muss passen vollständig in einem einzigen Block und dann solche Aufzeichnungen per definitionem nie größer als ein voller Block. Im Laufe der Zeit werden Datensätze hinzugefügt und aus diesen Blöcken gelöscht, wie Aufzeichnungen kommen und gehen aus dieser „Datenbank“.

An einem gewissen Punkt, vor allem nach vielleicht viele Datensätze der Datenbank hinzugefügt werden und einige werden entfernt -. Viele der Blöcke können am Ende nur teilweise gefüllt

Was ist ein guter Algorithmus die Datensätze um in dieser Datenbank zu komprimieren aus unnötigen Blöcken am Ende der Datei durch eine bessere Auffüllen der teilweise gefüllten Blöcke zu mischen?

Anforderungen des Algorithmus:

• Die Verdichtung muss anstelle der ursprünglichen Datei geschehen, ohne vorübergehend um mehr als ein paar Blöcke die Datei erstreckt höchstens von seiner Ausgangsgröße
• Der Algorithmus sollte nicht unnötig blockiert stören, die bereits überwiegend voll
• Ganze Blöcke müssen von / zu der Datei auf einmal gelesen oder geschrieben werden, und man sollte die Schreiboperation annimmt relativ teuer ist
• Wenn Datensätze von einem Block zum anderen verschoben werden, müssen sie an ihrem neuen Standort hinzugefügt werden, bevor sie aus ihrer Ausgangsposition entfernt wird, so dass im Falle der Betrieb keine Datensätze verloren als Folge der „failed“ Verdichtung unterbrochen wird. (Es sei angenommen, dass diese vorübergehende Vervielfältigung solcher Aufzeichnungen können bei der Erholung festgestellt werden).
• Der Speicher, der für diesen Vorgang verwendet werden kann, kann nur vielleicht mehrere Blöcke in der Größenordnung von sein, die ein sehr kleiner Prozentsatz der Gesamtdateigröße ist
• Nehmen wir an, Datensätze in der Größenordnung von 10 Bytes mit einer durchschnittlichen Größe von vielleicht 100 Byte auf 1 K Bytes sind. Die feste Größe Blöcke sind in der Größenordnung von 4K oder 8K und dass die Datei in der Größenordnung von 1000 von Blöcken ist.

Answer 1

Das klingt wie eine Variation der Bin Packing Problem , aber wo Sie bereits ein inferior Zuordnung, die Sie verbessern möchten. Also schlage ich vor, auf Schwankungen der Ansätze suchen, die für die Bin Packing Problem erfolgreich sind.

Zu allererst möchten Sie wahrscheinlich Ihr Problem parametrieren definieren, was man „voll genug“ betrachten (wo ein Block voll genug ist, dass man es nicht berühren wollen), und was „zu leer“ (wo ein Block hat so viel leeren Raum, dass es mehrere Datensätze hinzugefügt haben, um es) hat. Dann können Sie alle Blöcke als voll genug klassifizieren, zu leer oder teilweise voll (jene, die weder voll genug noch zu leer sind). Sie definieren dann das Problem, wie man durch die Schaffung so viele voll genug Blöcke wie möglich, alle zu leeren Blöcke zu eliminieren, während die Anzahl der teilweise gefüllten Blöcke minimiert wird.

Sie werden auch arbeiten wollen, was wichtiger ist: die Datensätze in den wenigsten Blöcke möglich bekommen, oder sie angemessen Verpackung aber mit der geringsten Menge von Blöcken gelesen und geschrieben

.

Mein Ansatz wäre ein Anstich über alle Blöcke zu machen, um sie alle in eine der drei Klassen oben definiert zu klassifizieren. Für jeden Block, möchten Sie auch den Überblick über den freien Raum darin zur Verfügung zu halten, und für die zu leeren Blöcke, finden Sie eine Liste aller Datensätze und deren Größe haben wollen. Dann mit dem größten Datensätze in den zu leeren Blöcken beginnen, sie in die teilweise voll Blöcke bewegen. Wenn Sie minimieren wollen liest und schreibt, um sie in einem der Blöcke bewegen Sie derzeit im Speicher haben. Wenn Sie vergeudeten Raum minimieren möchten, finden Sie den Block mit der geringsten Menge von leeren Raum, der den Datensatz noch halten wird, lesen Sie den Block in falls erforderlich. Wenn kein Block den Rekord halten wird, erstellen Sie einen neuen Block. Wenn ein Block im Speicher der „voll genug“ Schwelle erreicht, schreiben Sie es aus. Wiederholen, bis alle Datensätze in den teilweise gefüllten Blöcke platziert wurden.

Ich habe über mehr als ein paar Details ausgelassen, aber das sollte Ihnen eine Vorstellung geben. Beachten Sie, dass die Bin Packing Problem ist NP-hard , was bedeutet, dass für praktische Anwendungen, Sie entscheiden wollen, was ist für Sie am wichtigsten, so können Sie einen Ansatz wählen, die Ihnen eine annähernd optimale Lösung in angemessener Zeit geben werden.

Answer 2

Wenn es keine Bestellung zu diesen Aufzeichnungen ist, würde ich einfach die Blöcke von der Front mit Datensatz aus dem letzten Block (n) extrahierten füllen. Dadurch wird die Bewegung von Daten minimieren, ist recht einfach und soll fest, einen anständigen Job tun Daten der Verpackung.

Z. B:.

// 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();
        }
    }
}

Update: Ich vernachlässigte die Nein-Blöcke-nur-in-Speicher-Regel zu halten. Ich habe den Pseudo-Code aktualisiert dieses Problem zu beheben. Auch eine Störung in meiner Schleifenbedingung festgelegt.

Answer 3

Eine Abwandlung eines On-line (in einem Durchgang zu defragmentieren) begrenzt Raum (die Speicheranforderungen) Bin Packing Algorithmus wahrscheinlich hier arbeiten könnte.

Siehe "Bin Packing Approximationsalgorithmen: Combinatorial Analysis" von Coffman et al.

Answer 4

Hier ist ein Algorithmus Sie Hebelwirkung in der Lage sein könnte, wenn auch Ihre Unterlagen innerhalb festgelegter Größe Blöcke könnte ein wenig mehr Arbeit erfordern.

Heap Defragmentierungs in Bounded Zeit