Проблема
У меня есть хэш данных, который выглядит примерно так.
{ "GROUP_A" => [22, 440],
"GROUP_B" => [14, 70],
"GROUP_C" => [60, 620],
"GROUP_D" => [174, 40],
"GROUP_E" => [4, 12]
# ...few hundred more
}
ГРУППА_А имеет 22 аккаунта, и они используют 440 ГБ данных... и так далее. Таких групп около сотни. У некоторых много учетных записей, но они используют очень мало места для хранения, а некоторые имеют всего несколько пользователей и используют МНОГО места для хранения, а некоторые просто средние.
У меня есть X корзин (серверов), в которые я хочу поместить эти группы учетных записей, и я хочу, чтобы в каждой корзине было примерно одинаковое количество учетных записей, и каждая корзина также содержала примерно одинаковое количество данных. Количество групп не имеет значения, поэтому, если в корзине есть 1 группа из 1000 учетных записей, использующих 500 ГБ данных, а в следующей корзине 10 групп из 97 учетных записей (всего 970), использующих 450 ГБ данных... Я бы назвал это хорошим.
Пока я не придумал алгоритм, который будет это делать. В моем уме я думаю о чем-то подобном возможно?
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 не делится без остатка на количество сегментов. Я попытался добавить 1% к значению AVG_ACCTS, что в данном случае означает, что среднее значение будет 383, я думаю, но тогда все корзины говорят, что в них 383 учетных записи... что не может быть правдой, потому что тогда есть больше аккаунтов в корзинах, чем MAX_ACCTS. У меня где-то в коде ошибка, которую я еще не нашел.
