3

假设您有一个由一堆固定大小的块组成的大文件。这些块中的每一个都包含一些可变大小的记录。每条记录必须完全适合单个块，然后根据定义，这些记录永远不会大于完整块。随着时间的推移，记录在这些块中添加和删除，因为记录来自这个“数据库”。

在某些时候，尤其是在可能将许多记录添加到数据库并删除了一些记录之后 - 许多块可能最终只被部分填充。

什么是一个好的算法来打乱这个数据库中的记录，通过更好地填充部分填充的块来压缩文件末尾不必要的块？

算法要求：

  • 必须在原始文件的位置进行压缩，而不是暂时将文件从其起始大小最多扩展几个块
  • 该算法不应不必要地干扰已经基本满的块
  • 必须一次从文件读取或写入整个块，并且应该假设写入操作相对昂贵
  • 如果记录从一个块移动到另一个块，则必须在从其起始位置删除之前将它们添加到新位置，以便在操作中断时不会因“失败”压缩而丢失记录。（假设这种记录的临时重复可以在恢复时检测到）。
  • 可用于此操作的内存可能只有几个块的数量级，这仅占整个文件大小的很小百分比
  • 假设记录大约为 10 字节到 1K 字节，平均大小可能为 100 字节。固定大小的块大约为 4K 或 8K，文件大约为 1000 个块。
4

4 回答 4

2

如果这些记录没有排序，我只需用从最后一个块中提取的记录填充前面的块。这将最大限度地减少数据的移动，相当简单，并且应该可以很好地打包数据。

例如：

// 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-only-in-memory 规则。我已经更新了伪代码来解决这个问题。还修复了我的循环条件中的故障。

于 2008-09-24T22:29:40.857 回答
2

这听起来像是装箱问题的变体，但是您已经有了想要改进的劣质分配。因此，我建议查看成功解决装箱问题的方法的变体。

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

您还需要弄清楚更重要的事情：将记录放入尽可能少的块中，或者将它们充分打包但读取和写入的块数量最少。

我的方法是对所有块进行初始传递，将它们全部分类为上面定义的三个类之一。对于每个块，您还希望跟踪其中的可用空间，对于太空的块，您将需要一个所有记录及其大小的列表。然后，从太空块中的最大记录开始，将它们移动到部分满的块中。如果您想最小化读取和写入，请将它们移动到您当前在内存中的任何块中。如果要尽量减少浪费的空间，请找到仍保留记录的具有最少空白空间的块，必要时读入该块。如果没有块将保存记录，则创建一个新块。如果内存中的块达到“足够满”阈值，则将其写出。

我跳过了很多细节，但这应该会给你一些想法。请注意，装箱问题是NP-hard问题，这意味着对于实际应用，您需要决定什么对您最重要，因此您可以选择一种在合理时间内为您提供近似最佳解决方案的方法。

于 2008-09-24T22:54:37.580 回答
2

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

请参阅Coffman 等人的“装箱近似算法：组合分析”。

于 2008-09-25T08:10:08.807 回答
0

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

有限时间内的堆碎片整理

于 2008-09-25T00:35:22.253 回答