並列処理の偏りを防ぎつつ、任意の数でハッシュをバケット分割できるキー名を求める方法

Question

背景・実現したいこと

並列計算を行うために、偏りが少ない形で分割処理するための前処理が行えるPython3での記述方法を探しています。

下記の入出力データ例と共に、どのような処理を行いたいかの説明をさせてください。

######入出力データ例

configの中に、aaa, bbb, cccという添え字があり、aaaの中には4つ、bbbには1つ、cccには3つ要素があります。
concurrency_limit=2ということで、単純に2つに分割すると [['aaa','bbb'],['ccc']]となります。
これではaaaとbbbの要素数は4+1=5、もう一方のcccの要素数は3となり、偏ってしまいます。

そうではなく、中の要素数を考慮した分割を行い、要素数の多い順に[['aaa'], ['ccc','bbb']]という結果を得られる方法が知りたく、お力添え頂けますでしょうか。
外部ライブラリを用いる方法も含めて探しております。

# 入力パラメータ (この結果を用いて並列上限数として作用させるため、この名称です)
concurrency_limit = 2

# 入力データ例 (k:vの箇所はそれぞれ異なる計算したい内容が記されている想定です)
config = {
    'aaa': {
             'aaa1': {'k': 'v'},
             'aaa2': {'k': 'v'},
             'aaa3': {'k': 'v'},
             'aaa4': {'k': 'v'}},
     'bbb': {'bbb1': {'k': 'v'}},
     'ccc': {
             'ccc1': {'k': 'v'},
             'ccc2': {'k': 'v'},
             'ccc3': {'k': 'v'}}
    }

# 出力データ例 (できるならば要素の多い順に並んで欲しいが、[['aaa'], ['bbb','ccc']]という順番でも可です)
[['aaa'], ['ccc','bbb']]

考えたこと

おそらく次のようなステップで行うのだろうと想像できたのですが、不勉強で記述方法が分かりませんでした。
もし、別の最適解を求められるスマートな手法があるとしたら、よりよい形での処理方法を学びたいです。

1. 要素数を計算済のデータ構造を作り大きい順にソートする 'aaa':4, 'ccc':3, 'bbb':1
2. concurrency_limit: Nのループで、新たに作ったハッシュ配列に先頭N件を格納する [{'item':['aaa'],'sum':4},{'item':['ccc'],'sum':3}]
3. 2周目のループでcountが少ない順に残った要素を追記する [{'item':['aaa'],'sum':4},{'item':['ccc','bbb'],'sum':4}]
4. itemの中身を出力する [['aaa'], ['ccc','bbb']]

検算として、 10, 7, 5, 4, 3, 2 という数列を2つに分割するとき、上記の方法だと次の分割となります。

1. 1ループ目 [10], [7]
2. 2ループ目 [10,4], [7,5]
3. 3ループ目 [10,4,2], [7,5,3]

合計値が左辺は10+4+2=16、右辺は7+5+3=15となり、おおむね均等配分出来ていると確認ができました。

しかし、 [3, 3, 2, 2, 2] に対して同じ手法で2分割すると、3 + 2 + 2 = 7 と 3 + 2 = 5 となります。
最適解である 3 + 3 = 6 と 2 + 2 + 2 = 6 とは異なる事にppaulさんのご指摘で気づきました。

試してみたこと

1次元配列を指定の数に分割する時に numpy や pandas を使ったことがあったので、関連する関数を探しました。
しかし入力データの形式を変えたとしても要件に合う物がなさそうに思えました。

また、teratailやGoogleで 均等 配分 分割などのキーワードで探しましたが、見つけられませんでした。

Comments

[ppaul]

次のようなステップの方法で[3, 3, 2, 2, 2]をやると、
3 + 2 + 2 = 7 と3 + 2 = 5 となりますね。
最適解は 3 + 3 = 6 と 2 + 2 + 2 = 6 ですが、最適解でなくても良いのですか？

[y-ken]

素晴らしいご指摘ありがとうございます。
確かにおっしゃるとおりで、最適解である方がもちろん好ましいです。

[y-ken]

その誤差を埋めるためにコード量がとても増えてしまう場合には、多少の偏りは許容したいと考えてます

Answer 1

また、teratailやGoogleで 均等 配分 分割などのキーワードで探しましたが、見つけられませんでした。

回答というか参考情報として。
問題としてはMultiway number partitioningに該当すると思います。

the problem of partitioning a multiset of numbers into a fixed number of subsets, such that the sums of the subsets are as similar as possible.

この問題はNP困難なのでconfigに含まれる要素数にもよりますが、厳密解ではなく近似解を求める手法をとるのが現実的かと思います。

Comments

[y-ken]

ありがとうございます。奥が深いのですね。
シンプルなアプローチで近似解を求める方向でサンプルを頂くことは出来ますでしょうか

[can110]

シンプルなアプローチとしては
・最初に値リストを降順にソート
・リストの先頭から、値の合計の最も少ない箱に詰めていく
といった感じでしょうか。
難しくないと思いますので、ご自身で実装できるかと思います。

[y-ken]

ありがとうございます、拙いながらも実践してみました。コードレビューいただけると、嬉しいです。

Answer 2

頂いた手法を元に、実装しました。
もし、こんな風に書いた方がもっと賢いですよ、というフィードバックございましたら、いただけると大変ありがたいです。

from operator import itemgetter
In [26]: groups = [[[], 0] for _ in range(concurrency_limit)]
    ...:
    ...: item_list = dict(sorted({category: len(config[category]) for category in config}.items(), key=lambda x:x[1
    ...: ], reverse = True))
    ...:
    ...: for item in item_list:
    ...:     print(f"item:{item} count:{item_list[item]}")
    ...:     smallest_group = min(groups, key=itemgetter(1))
    ...:     smallest_group[0].append(item)
    ...:     smallest_group[1] += item_list[item]
    ...:
    ...: print([item[0] for item in groups])
item:aaa count:4
item:ccc count:3
item:bbb count:1
[['aaa'], ['ccc', 'bbb']]