Pythonで辞書データを2重ループにならずに処理したいです。

Question

行いたいこと

以下のような辞書があります。

store = {
         "A店": {"リンゴ":5, "みかん":3, "もも": 1},
         "B店": {"リンゴ": 3, "なし": 1},
         "C店": {"いちご": 6, "みかん":1},
         "D店": {"いちご":6, "リンゴ": 3, "なし": 2, "みかん":1}
}

この辞書を以下のルールで分けていきます。

1. お店ごとに品物をグループ分けする
2. グループは合計5以下になるようにわける(ただし1つの品で5以上ならそのまま1グループにする)

A店の場合は リンゴで1グループ、みかんとももで1グループ
B店の場合はリンゴとなしで1グループ
C店の場合はいちごで1グループ、みかんで1グループ
D店の場合はいちごで1グループ、リンゴとなしで1グループ、みかんで1グループ

品物は数字で降順にソートされているとします。

最終的にはこのグループを以下のようなデータに変換したいです。

[
["A店", "リンゴ"],
["A店", "みかん もも"],
["B店", "リンゴ なし"],
["C店", "いちご みかん"],
["D店", "いちご"],
["D店", "リンゴ なし"],
["D店", "みかん"]
]

このときに色々考えてみたのですが、2重ループになってしまい困っています。

どのようにすれば1回のループで実現できますでしょうか。

Comments

[maisumakun]

> 2重ループになってしまい困っています。

なぜ困るのですか？

[WatanabeJin]

いまはデータが3つなのですが、これは簡単に例題をするために行っています。
実際は1万以上のお店と、1万以上の品物があります。
ですので2重ループですと処理が遅くなってしまいます。

[maisumakun]

> ですので2重ループですと処理が遅くなってしまいます。

実際に困る程度の速度しか出なかったのですか？

[maisumakun]

> 実際は1万以上のお店と、1万以上の品物があります。

1万以上のお店全てに1万種類の商品がある、という状況なのですか？（そうだとしたらデータは1億項目になりますので、順当にたどっていっても時間がかかるのは「仕方ない」です）

Answer 1

どのようにすれば1回のループで実現できますでしょうか。

無理でしょう。
速度が要求されるならC言語などで書いてはいかがでしょうか？
Pythonでは、ジェネレータにすればメモリを消費せずに高速になるかもしれません。

stores = {
         "A店": {"リンゴ":5, "みかん":3, "もも": 1},
         "B店": {"リンゴ": 3, "なし": 1},
         "C店": {"いちご": 6, "みかん":1},
         "D店": {"いちご":6, "リンゴ": 3, "なし": 2, "みかん":1}
}

def convert(limit=5):
    for store, products in stores.items():
        names, counts = [], 0
        for name, count in products.items():
            names.append(name)
            counts += count
            if counts >= limit:
                yield store, " ".join(names)
                names, counts = [], 0
        if names:
            yield store, " ".join(names)

for item in convert():
    print(item)