问题
我有一个看起来像这样的数据哈希。
{ "GROUP_A" => [22, 440],
"GROUP_B" => [14, 70],
"GROUP_C" => [60, 620],
"GROUP_D" => [174, 40],
"GROUP_E" => [4, 12]
# ...few hundred more
}
GROUP_A 有 22 个帐户，他们正在使用 440GB 的数据......等等。有几百个这样的组。有些人有很多帐户但使用的存储空间很少，有些人只有少数用户并使用大量存储空间，有些只是平均水平。
我有 X 个存储桶（服务器），我想将这些帐户组放入其中，并且我希望每个存储桶的帐户数量大致相同，并且每个存储桶也包含大致相同数量的数据。组的数量并不重要，所以如果一个存储桶有 1 组使用 500GB 数据的 1000 个帐户，而下一个存储桶有 10 组使用 450GB 数据的 97 个帐户（总共 970 个）......我会称之为好。
到目前为止，我还没有想出一个算法来做到这一点。在我的脑海中，我可能正在考虑这样的事情？
PASS 1
Bucket 1: Group with largest data, 60 users.
Bucket 2: Next largest data group, 37 users.
Bucket 3: Next largest data group, 72 users.
Bucket 4: etc....
PASS 2
Bucket 1: Add a group with small amount of data, but more users than average.
# There's probably a ratio I can calculate to figure this out...divide users/datavmaybe?
Bucket 2: Find a "small data" group where sum of users in Bucket 1 ~= sum of users in Bucket 2
# But then there's no guarantee that the data usages will be close enough
Bucket 3: etc...
PASS 3
Bucket 1: Now what? Back to next largest data group?
我仍然认为有更好的方法来解决这个问题，但它并没有出现在我身上。如果有人有任何想法，我愿意接受建议。
马特
解决方案 1.1 - 蛮力更新
嗯....这是第一次尝试的更新。这仍然不是一个“背包问题”的解决方案。只需暴力破解数据，以便帐户在存储桶之间保持平衡。这次我添加了一些逻辑，以便如果一个存储桶的帐户完整百分比与数据相比更高......它将根据帐户数量找到最适合的最大组（按数据）。与我的第一次尝试相比，我现在的数据分布要好得多（如果您想查看第一次尝试，请参阅编辑历史记录）。
现在我按顺序加载每个存储桶，填充存储桶一，然后存储存储桶二，等等......我想如果我要修改代码以便同时（或几乎同时）填充它们，我会获得更好的数据平衡。
例如，第 1 部门进入存储桶 1，第 2 部门进入存储桶 2，等等……直到所有存储桶都有一个部门……然后再次从存储桶 1 开始。
dept_arr_sorted_by_acct = dept_hsh.sort_by {|key, value| value[0]}
ap "MAX ACCTS: #{max_accts} AVG ACCTS: #{avg_accts}"
ap "MAX SIZE: #{max_size} AVG SIZE: #{avg_data}"
# puts dept_arr_sorted_by_acct
# exit
bucket_arr = Array.new
used_hsh = Hash.new
server_names.each do |s|
bucket_hsh = Hash.new
this_accts=0
this_data=0
my_key=""
my_val=[]
accts=0
data=0
accts_space_pct_used = 0
data_space_pct_used = 0
while this_accts < avg_accts
if accts_space_pct_used <= data_space_pct_used
# This loop runs if the % used of accts is less than % used of data
dept_arr_sorted_by_acct.each do |val|
# Sorted by num accts - ascending. Loop until we find the last entry in the array that has <= accts than what we need
next if used_hsh.has_key?(val[0])
#do nothing
if val[1][0] <= avg_accts-this_accts
my_key = val[0]
my_val = val[1]
accts = val[1][0]
data = val[1][1]
end
end
else
# This loop runs if the % used of data is less than % used of accts
dept_arr_sorted_by_data = dept_arr_sorted_by_acct.sort { |a,b| b[1][1] <=> a[1][1] }
dept_arr_sorted_by_data.each do |val|
# Sorted by size - descending. Find the first (largest data) entry where accts <= what we need
next if used_hsh.has_key?(val[0])
# do nothing
if val[1][0] <= avg_accts-this_accts
my_key = val[0]
my_val = val[1]
accts = val[1][0]
data = val[1][1]
break
end
end
end
used_hsh[my_key] = my_val
bucket_hsh[my_key] = my_val
this_accts = this_accts + accts
this_data = this_data + data
accts_space_pct_used = this_accts.to_f / avg_accts * 100
data_space_pct_used = this_data.to_f / avg_data * 100
end
bucket_arr << [this_accts, this_data, bucket_hsh]
end
x=0
while x < bucket_arr.size do
th = bucket_arr[x][2]
list_of_depts = []
th.each_key do |key|
list_of_depts << key
end
ap "Bucket #{x}: #{bucket_arr[x][0]} accounts :: #{bucket_arr[x][1]} data :: #{list_of_depts.size} departments"
#ap list_of_depts
x = x+1
end
……结果……
"MAX ACCTS: 2279 AVG ACCTS: 379"
"MAX SIZE: 1693315 AVG SIZE: 282219"
"Bucket 0: 379 accounts :: 251670 data :: 7 departments"
"Bucket 1: 379 accounts :: 286747 data :: 10 departments"
"Bucket 2: 379 accounts :: 278226 data :: 14 departments"
"Bucket 3: 379 accounts :: 281292 data :: 19 departments"
"Bucket 4: 379 accounts :: 293777 data :: 28 departments"
"Bucket 5: 379 accounts :: 298675 data :: 78 departments"
(379 * 6 <> 2279) 我仍然需要弄清楚当 MAX_ACCTS 不能被桶数整除时如何计算。我尝试在 AVG_ACCTS 值上添加 1% 填充，在这种情况下，我认为平均值为 383，但随后所有存储桶都说他们有 383 个帐户……这不可能是真的，因为那时有存储桶中的帐户数量超过 MAX_ACCTS 个。我在我还没有找到的地方的代码中有一个错误。