ruby - 跨多列排序和平衡

Question

问题

我有一个看起来像这样的数据哈希。

{ "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 组 1000 个帐户使用 500GB 数据，而下一个桶有 10 组 97 个帐户(总共 970 个)使用 450GB 数据......我认为它很好。

到目前为止，我还没有想出可以做到这一点的算法。在我看来，我可能正在考虑这样的事情？

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，第二个部门进入存储桶 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 个。我在代码中的某个地方有错误，我还没有找到。

Answer 1

这是 knapsack problem 的示例.有一些解决方案，但这是一个非常棘手的问题，最好研究一个好的解决方案而不是尝试自己制作。