それなりブログ

とあるWebエンジニアのそれなりのブログ、JavaScript/Node.js/Python/PHP/ゲーム作成 など

[Python] 再帰的にdictをwalkする関数

「自分の子リストを持つdictデータ」を再帰的に評価したかった

例えば以下のようなデータを

adict = {
    'name': u'波平',
    'children': [
        {
            'name': u'サザエ',
            'children':[{'name':u'タラオ', 'children':[]}],
        },
        {'name': u'カツオ', 'children':[]},
        {'name': u'ワカメ', 'children':[]},
    ]
}

こんな風に操作したいなと思いました

for child in 関数(adict):
print child['name'] # -> u'波平' から順次表示

walk_dict関数を作ったけど

というわけで、walk_dict(adict, children_key) という関数を作りました

・・・と、要件は満たせたんですが、何か変

for i in walk_dict(child, children_key):
    yield i

のところを、generatorを解除するのに1回しか回らんループをしてるのが特に変?

ということで

「○○モジュール使えばいいんじゃないの?お馬鹿なの?」
という、身も蓋もない意見を絶賛募集中です!

後、ついでにも程がありますが、JavaScriptでも同じような関数を募集中です!!

別解を貰った

@kenji4569 さんから別解を貰ったので、元解答と両方さらしておきます

# 自分
def walk_dict(adict, children_key):
    yield adict
    for child in adict[children_key]:
        for i in walk_dict(child, children_key):
            yield i

# @kenji4569 さん
def walk_dict(adict, children_key):
    from itertools import chain
        return chain([adict], *[walk_dict(child, children_key) for child in adict[children_key]])

JavaScript版

アルゴリズムは一緒です、JSに書き起こしただけ
イテレーターにはなってません

function walkObject(obj, childrenKey) {
    var sequence = [];
    sequence.push(obj);
    var children = obj[childrenKey];
    for (var i = 0; i < children.length; i++) {
        var child = children[i];
        sequence = sequence.concat(arguments.callee(child, childrenKey));
    }
    return sequence;
}

4 Responses to “[Python] 再帰的にdictをwalkする関数”

  • 細田謙二 より:

    itertoolsのchainでがんばってみました:
    from itertools import chain
    def walk_dict(adict, children_key):
    return chain([adict], *[walk_dict(child, children_key) for child in adict[children_key]])
    やや難読ですが、「1回しか回らんループ」は消せます。
    (頭の体操になりました)

  • kjirou より:

    あざーす、記事に載せました
    確かに見事にfor文が消えてるんですが、リスト内包表記の時点でlistとして展開しちゃうから、イテレーターもどきになっちゃってますな・・・残念
    考えた結果、「iteratorもgeneratorもループするためのものなんだから、for で回して解除するのが正しいだろう」と解釈することにしました
    じゃあ、はじめっから言うなよ!という感じですね、はい

  • 細田謙二 より:

    そうっすね。。補足ですが、この場合、局所的にはリストを返しますが、全体としては(chainを使っているので)イテレータになります。つまり、イテレートに必要となるメモリ容量は、結果全体ではなく、各辞書要素に格納されているリストの最大長で決まります。
    で、2.6以降ではchain.from_iterableを使って完全イテレータにすることも可能です:

    return chain.from_iterable([[adict], (walk_dict(child, children_key) for child in adict[children_key])])

  • kjirou より:

    関数の一行目に、adictの内容が確認できるprint文を入れて実行すると、先にそれが全ノード分実行されてから値を返すんだけど、これは値を返す前に全データ展開しちゃってるということではない?
    もう頭が追い付かないので、実行結果の判断しかできないんだけど


コメントを残す

メールアドレスが公開されることはありません。

Categories

Archives