合計が均等になるようにグループ分けする
問題
製品のテストをJenkinsで並列に走らせていると想像して下さい。
実行するテストケースをノードに上手く割り振っていなかったので、 あるノードではテストが5分で終わるのに、別のノードでは40分もかかってしまっていました。
各テストケースの所要時間は分かっているので、上手く再分配したいと思います。
（待ち行列方式で、空いたノードに動的にテストケースを実行させる戦略もありますが、 今回は考えないことにします。）
解決
テストケースを所要時間が長い順にソートし、合計時間が短いノードに順に分配していけば、それなりに上手く行きます。
# -*- coding: utf-8 -*-
from operator import itemgetter
# n個のグループに分ける。
# ただし、各グループのサイズはgroup_sizeを超えないようにする
def pack_into_groups(n, group_size, items, get_volume):
items.sort(key=get_volume, reverse=True)
for item in items:
if get_volume(item) > group_size:
raise ValueError(
"{!r} is larger than group_size {!r}".format(item, group_size)
)
groups = [[[], 0] for _ in range(n)]
for item in items:
smallest_group = min(groups, key=itemgetter(1))
smallest_group[0].append(item)
smallest_group[1] += get_volume(item)
if smallest_group[1] > group_size:
raise ValueError('Failed to partition into {} groups'.format(n))
return groups
# できるだけ少ないグループ数に収めようとする
def pack_into_groups_as_small(max_group_count, group_size, items, get_volume):
for n in range(1, max_group_count):
try:
return pack_into_groups(n, group_size, items, get_volume)
except ValueError as e:
continue
else:
raise e
def main():
# テストケースとその実行時間
test_cases_to_partition = [
dict(name='test A', duration=1),
dict(name='test B', duration=2),
dict(name='test C', duration=5),
dict(name='test D', duration=13),
dict(name='test E', duration=1),
dict(name='test F', duration=3),
dict(name='test G', duration=8),
dict(name='test H', duration=21),
]
max_total_time = 25 # テストは25分以内に実行したい
max_group_count = 5 # 多くても5ノードに収めたい
# グループに分け、合計時間とテストケース名を表示
groups = pack_into_groups_as_small(
max_group_count,
max_total_time,
test_cases_to_partition,
itemgetter('duration')
)
for test_cases, total in groups:
print('total: {}'.format(total))
for test_case in test_cases:
print('\t{}'.format(test_case['name']))
if __name__ == '__main__':
main()
補足
この問題はビンパッキング問題 - Wikipedia と呼ばれ、NP困難問題なので効率的に解くことは（多分）できません。
したがって、今回の解法も場合によっては必要より多くのグループができてしまうのですが、 実際には必要最小限の2倍ぐらいまでしかグループは増えないことが証明できます。
