読者です 読者をやめる 読者になる 読者になる

合計が均等になるようにグループ分けする

Python デザインパターン

問題

製品のテストを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倍ぐらいまでしかグループは増えないことが証明できます。

Bin Packing 問題 近似アルゴリズム