gpt4 book ai didi

algorithm - 简单的存储分配算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:09:54 24 4
gpt4 key购买 nike

我们有一大堆机器使用一大堆数据存储。我们想将所有机器的数据传输到新的数据存储中。这些新商店的机器可用存储空间量各不相同。此外,每台机器需要存储的数据量各不相同。单个机器的所有数据必须存储在单个数据存储中;它不能被分割。除此之外,数据的分配方式并不重要。

我们目前拥有的数据多于我们的空间,因此不可避免地,某些机器需要将数据保留在原处,直到我们找到更多数据。与此同时,有没有人知道一种算法(相对简单:我没那么聪明)可以为我们拥有的存储提供最佳或接近最佳的分配(即分配后新存储上剩余的空间最少) )?

我知道这听起来像是一道家庭作业题,但我向你保证这是真的!

最佳答案

乍一看这似乎是多背包问题(http://www.or.deis.unibo.it/knapsack.html,第 6.6 章“多背包问题 - 近似算法”),但实际上它是一个调度问题,因为它涉及时间元素。不用说,解决这些类型的问题很复杂。一种方法是将它们建模为网络流并使用像 GOBLIN 这样的网络流库。

在您的情况下,请注意您实际上不想以最佳方式填充存储,因为如果您这样做,将更有可能存储较小的数据包,因为它会导致更紧密的包装。这很糟糕,因为如果大包裹留在机器上,那么您 future 的包装会越来越糟糕。您想要做的是优先存储较大的包裹,即使这意味着在商店中留出更多额外空间,因为这样您将来会获得更大的灵 active 。

下面是如何用一个简单的算法解决这个问题:

(1) 确定 bin 大小并对它们进行排序。例如,如果您有 3 家商店,空间分别为 20 GB、45 GB 和 70 GB,那么您的目标是 { 20, 45, 70 }。

(2) 将所有数据包按大小排序。例如,您可能有数据包:{ 2, 2, 4, 6, 7, 7, 8, 11, 13, 14, 17, 23, 29, 37 }。

(3) 如果任何包裹的总和超过商店的 95%,则将它们放入该商店并转到步骤 (1)。这里不是这种情况。

(4) 生成两个包的所有排列。

(5) 如果任何排列总和大于商店的 95%,则将它们放入该商店。如果有领带,则更喜欢带有更大包装的组合。在我的示例中,有两个这样的对 { 37, 8 } = 45 和 { 17, 2 } = 19。(请注意,使用 { 17, 2 } 胜过使用 { 13, 7 })。如果找到一个或多个匹配项,请返回步骤 (1)。

好的,现在我们只剩下一家商店:70 个和以下包裹:{ 2, 4, 6, 7, 7, 11, 13, 14, 23, 29 }。

(6) 将 perms 的数量增加 1,然后转到步骤 5。例如,在我们的例子中,我们发现没有 3-perm 增加到 70 的 95% 以上,但是 4 perm { 29, 23, 14 , 4 } = 70。最后我们在机器上留下了包 { 2, 6, 7, 7, 11, 13 }。请注意,这些大多是较小的包。

请注意,perms 是按相反的词法顺序(最大的在前)进行测试的。例如,如果您有“abcde”,其中 e 是最大的,那么 3-perms 的反向词法顺序是:

cde
bde
阿德
公元前
王牌

此算法非常简单,并且会根据您的情况产生良好的结果。

关于algorithm - 简单的存储分配算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12828711/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com