Проблема
У меня есть хэш данных, который выглядит примерно так:
{ "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 ГБ данных ... и так далее.Есть пара сотен таких групп.Некоторые имеют много учетных записей, но используют очень мало памяти, а некоторые имеют только несколько пользователей и используют МНОГО хранилища, некоторые просто средние.
У меня есть 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?
Я все еще думаю, что есть лучший способ понять это, но это не приходит ко мне.Если у кого-то есть какие-либо мысли, я открыт для предложений.
Matt
Решение 1.1 - Обновление Brute Force
Хорошо ... вот обновление с первой попытки.Это все еще не решение проблемы «ранца».Просто грубое форсирование данных, чтобы баланс счетов попал в корзину.На этот раз я добавил некоторую логику, чтобы, если в корзине был более высокий полный процент учетных записей по сравнению с данными ... она нашла самую большую группу (по данным), которая лучше всего подходит по количеству учетных записей.Сейчас я получаю намного лучшее распределение данных по сравнению с моей первой попыткой (см. Историю редактирования, если вы хотите посмотреть с первой попытки).
Прямо сейчас я загружаю каждое ведение по очереди, заполняя одно ведро, затемвторой блок и т. д. Я думаю, что если бы я изменил код так, чтобы я заполнил их одновременно (или почти), я получил бы лучший баланс данных.
например, 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% pad к значению AVG_ACCTS, что в данном случае означает, что среднее значение будет 383, я думаю, но тогда все сегменты говорят, что в них 383 учетных записи ... что не может быть правдой, потому что тогда естьбольше аккаунтов в корзинах, чем MAX_ACCTS.У меня есть ошибка в коде, которую я еще не нашел.