在被阻止的文件中压缩记录的好算法是什么?

这听起来像是 bin packing problem 但是如果你已经有了一个你想要改进的下等分配。因此,我建议研究一下成功解决装箱问题的各种方法。

首先,您可能希望通过定义您认为“足够满”(块足够满,以至于您不想触摸它)的内容以及“太空”(块有太多的空空间,必须添加更多记录)来参数化您的问题。然后,您可以将所有块分类为“已满”、“太空”或“部分满”(那些既不足够也不太空的块)。然后,您将问题重新定义为如何通过创建尽可能多的完全足够的块来消除所有太空的块,同时最小化部分完全的块的数量。

您还需要计算出更重要的内容:将记录放入尽可能少的块中,或者充分地打包它们,但读写的块数量最少。

我的方法是对所有块进行初始传递,将它们全部分类为上面定义的三个类中的一个。对于每个块,您还需要跟踪其中的可用空间,对于太空的块,您需要一个包含所有记录及其大小的列表。然后,从太空块中最大的记录开始,将它们移动到部分满块中。如果您想最小化读和写,请将它们移到您当前内存中的任何块中。如果你想把浪费的空间减到最小,找一个有最少的空白空间的块来保存记录,如果需要的话,把这个块读进去。如果没有块保存记录,请创建一个新块。如果内存中的某个块达到“足够满”的阈值,则将其写出。重复,直到部分填充块中的所有记录都已放置。

我跳过了很多细节,但这应该给你一些建议。注意,装箱问题是 NP-hard 也就是说,对于实际应用,您需要决定什么对您最重要,这样您就可以选择一种方法,在合理的时间内为您提供一个近似最佳的解决方案。

如果没有对这些记录进行排序,我只需要从前面的块中填充从最后一个块中提取的记录。这将最大限度地减少数据的移动,相当简单,并且应该能够很好地紧密地打包数据。

例如。:

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

更新:我忽略了只在内存中维护no blocks规则。我已经更新了伪代码来修复这个问题。还修复了循环条件中的故障。

在线(一次进行碎片整理)有界空间(内存需求)装箱算法的修改可能在这里起作用。

见 "Bin Packing Approximation Algorithms: Combinatorial Analysis" Coffman等人

这是一个您可以利用的算法,尽管您在固定大小块中的记录可能需要更多的工作。

Heap Defragmentation in Bounded Time