12

ネストされたディクショナリに値が複数回存在する可能性がある場合、ネストされたディクショナリを処理し、特定の値に対してネストされた親キーを返すのに苦労しています。例えば：

example_dict = { 'key1' : 'value1',
                 'key2' : 'value2',
                 'key3' : { 'key3a': 'value3a' },
                 'key4' : { 'key4a': { 'key4aa': 'value4aa',
                                       'key4ab': 'value4ab',
                                       'key4ac': 'value1'},
                            'key4b': 'value4b'}
                }

上記の辞書に「value1」が 2 回表示されていることに気付くでしょう。ここでは、異なる親キー (この場合は「key1」) を識別する単一のリストまたは一連のリストを返す関数を作成したいと考えています。 ' および ('key4', 'key4a', key4ac)。

このタイプの問題は、このサイトの他の場所で処理され、探している値が 1 回しか表示されず、次の再帰関数によって容易に処理されました。

def find_key(d,key):
    for k,v in d.items():
        if isinstance(v,dict):
            p = find_key(v,key)
            if p:
                return [k] + p
        elif v == key:
            return [k]

print find_key(example_dict,'value4ac').

上記のコードをディクショナリで実行すると、親キーに対して 1 つの回答しか得られません。どんな助けでも大歓迎です、ありがとう！

4

2 に答える 2

12

単一の検索を行うだけでない限り (または、メモリに非常に制約があるが、CPU 時間を消費する必要がある場合など)、逆引き辞書を作成したいと思うでしょう。そうすれば、それをそのまま使用できます。

簡単にするために、2 つのステップで説明します。まず、ネストされたディクショナリをキーパス ディクショナリに変換します。

def keypaths(nested):
    for key, value in nested.iteritems():
        if isinstance(value, collections.Mapping):
            for subkey, subvalue in keypaths(value):
                yield [key] + subkey, subvalue
        else:
            yield [key], value

list(keypaths(example_dict))これが何をするのか明らかでない場合は、印刷してください。

では、逆引き辞書はどのように作成するのでしょうか。1 対 1 のマッピングの場合は、次のようにするだけです。

reverse_dict = {value: keypath for keypath, value in keypaths(example_dict)}

しかし、あなたのような多対 1 マッピングの場合、逆は 1 対多であるため、各値をキーのリストにマッピングする必要があります。そう：

reverse_dict = {}
for keypath, value in keypaths(example_dict):
    reverse_dict.setdefault(value, []).append(keypath)

そして今、あなたは空想的なものは何も必要としません。で通常の​​辞書検索を行うだけですreverse_dict：

>>> reverse_dict['value2']
[('key2',)]
>>> reverse_dict['value1']
[('key1',), ('key4', 'key4a', 'key4ac')]
>>> reverse_dict['value3']
KeyError: 'value3'

[]a を発生させる代わりに最後のものを返したい場合は、プレーンの代わりに aKeyErrorを使用でき、その後は必要ありません。defaultdict(list)dictsetdefault

いずれにせよ、この逆マッピングを構築するのにかかる時間は、力ずくで 1 回の検索を行うのにかかる時間よりもわずかに長いだけなので、100 回の検索を行う場合は、この方法でほぼ 100 倍速くなります。同様に簡単です。

于 2013-09-16T04:29:09.990 に答える
7

ここに1つの解決策があります：

from copy import copy

example_dict = { 'key1' : 'value1',
                 'key2' : 'value2',
                 'key3' : { 'key3a': 'value3a' },
                 'key4' : { 'key4a': { 'key4aa': 'value4aa',
                                       'key4ab': 'value4ab',
                                       'key4ac': 'value1'},
                            'key4b': 'value4b'}
                }


result = []
path = []

def get_keys(d, target):
    for k, v in d.iteritems():
        path.append(k)
        if isinstance(v, dict):
            get_keys(v, target)
        if v == target:
            result.append(copy(path))
        path.pop()

結果：

>>> get_keys(example_dict, 'value1')
>>> result
[['key1'], ['key4', 'key4a', 'key4ac']]
于 2013-09-16T01:44:21.127 に答える