假设您有一个由一堆固定大小的块组成的大文件。这些块中的每个块都包含一些可变大小的记录。每条记录必须完全适合单个块,然后根据定义,此类记录决不能大于整个块。随着时间的流逝,随着记录从该“数据库”进出,记录将添加到这些块中或从中删除。
在某个时候,尤其是在可能将许多记录添加到数据库中并删除了一些记录之后,尤其是在许多块最终只能部分填充的情况下。
有什么好的算法可以对数据库中的记录进行混洗,从而通过更好地填充部分填充的块来压缩文件末尾的不必要块?
算法要求:
这听起来像是装箱问题的一种变体,但是您已经有一个要改善的劣质分配。因此,我建议研究能成功解决垃圾箱包装问题的各种方法。
首先,您可能想通过定义您认为“足够充满”的内容(其中一个块足够充满以至于您不想触摸它)和什么是“太空”(其中一个块具有太多的空白空间,因此必须添加更多的记录)。然后,您可以将所有块分类为足够满,太空或部分满(既不满也不空)。然后,您将问题重新定义为如何通过创建尽可能多的足够多的块,同时最小化部分完全块的数量来消除所有太空的块。
您还需要弄清更重要的事情:将记录放入尽可能少的块中,或者将它们适当地打包,但要读取和写入的块数最少。
我的方法是对所有块进行初始遍历,将它们全部分类为上面定义的三个类之一。对于每个块,您还希望跟踪其中的可用空间,对于太空的块,您将需要具有所有记录及其大小的列表。然后,从太空的块中最大的记录开始,将它们移到部分充满的块中。如果要最大程度地减少读写,请将它们移到当前内存中的任何块中。如果要最小化浪费的空间,请找到仍然保留记录的空白空间最少的块,并在必要时读取该块。如果没有任何块将保留该记录,请创建一个新块。如果内存中的某个块达到“足够多”的阈值,则将其写出。
我已经跳过了许多细节,但这应该可以使您有所了解。请注意,装箱问题是NP-hard的,这意味着对于实际应用,您将要决定对您最重要的事情,因此您可以选择一种在合理的时间内为您提供最佳解决方案的方法。