0

問題

このようなデータのハッシュがあります。

{ "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 個のアカウントがあり、440 GB のデータを使用しています...など。これらのグループは数百あります。多くのアカウントを持っているがストレージをほとんど使用していない人もいれば、少数のユーザーしか持たず大量のストレージを使用している人もいれば、平均的な人もいます。

これらのアカウントのグループを入れたい X 個のバケット (サーバー) があり、バケットごとにほぼ同じ数のアカウントがあり、各バケットにもほぼ同じ量のデータが含まれている必要があります。グループの数は重要ではないため、バケットに 500 GB のデータを使用する 1000 アカウントの 1 グループがあり、次のバケットに 450 GB のデータを使用する 97 アカウントの 10 グループ (合計 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 を満たし、次にバケット 2 を満たします。コードを変更して、それらを同時に (またはほぼ同時に) 満たすようにすれば、データ バランスが改善されると思います。

たとえば、1 番目の部門をバケット 1 に、2 番目の部門をバケット 2 に、というように...すべてのバケットが 1 つの部門になるまで...その後、再びバケット 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 を超えています。まだ見つけていないコードのどこかに間違いがあります。

4

1 に答える 1

2

これはナップザック問題の例です。いくつかの解決策がありますが、これは非常に難しい問題であり、独自の解決策を試すよりも、適切な解決策を研究する方がよいでしょう。

于 2011-05-17T03:48:09.870 に答える