Как это сделать - обход словаря Python и поиск

Question

У меня есть вложенные словари:

{'key0': {'attrs': {'entity': 'p', 'hash': '34nj3h43b4n3', 'id': '4130'},
          u'key1': {'attrs': {'entity': 'r',
                              'hash': '34njasd3h43b4n3',
                              'id': '4130-1'},
                    u'key2': {'attrs': {'entity': 'c',
                                        'hash': '34njasd3h43bdsfsd4n3',
                                        'id': '4130-1-1'}}},
          u'key3': {'attrs': {'entity': 'r',
                              'hash': '34njasasasd3h43b4n3',
                              'id': '4130-2'},
                    u'key4': {'attrs': {'entity': 'c',
                                        'hash': '34njawersd3h43bdsfsd4n3',
                                        'id': '4130-2-1'}},
                    u'key5': {'attrs': {'entity': 'c',
                                        'hash': '34njawersd3h43bdsfsd4n3',
                                        'id': '4130-2-2'}}}},
 'someohterthing': 'someothervalue',
 'something': 'somevalue'}

дано id - один из всех ids, как 4130 до 4130-2-2.
Какой самый простой способ перейти к правильному словарю?

Например, если данный id равен 4130-2-1, то он должен достигнуть словаря с key=key5

не xml подходит, пожалуйста.

Редактировать (1): Вложенность находится между уровнями от 1 до 4, но я знаю вложение, прежде чем анализировать.

Редактировать (2) : Исправлен код.

** Редактировать (3): ** Снова исправлен код для строковых значений ids. Пожалуйста, извините за созданную путаницу. Надеюсь, это окончательно :) 1029 *

Answer 1

Ваша структура неприятно нерегулярна. Вот версия с функцией Visitor , которая пересекает под словари attrs.

def walkDict( aDict, visitor, path=() ):
    for  k in aDict:
        if k == 'attrs':
            visitor( path, aDict[k] )
        elif type(aDict[k]) != dict:
            pass
        else:
            walkDict( aDict[k], visitor, path+(k,) )

def printMe( path, element ):
    print path, element

def filterFor( path, element ):
    if element['id'] == '4130-2-2':
        print path, element

Вы бы использовали это так.

walkDict( myDict, filterFor )

Это можно превратить в генератор вместо Посетитель ; yield path, aDict[k] вместо вызова функции посетителя.

Вы бы использовали его в цикле for.

for path, attrDict in walkDictIter( aDict ):
    # process attrDict...

Answer 2

Если вы хотите решить проблему в общем, независимо от того, сколько уровней вложенности у вас есть в вашем dict, то создайте рекурсивную функцию, которая будет проходить по дереву:

def traverse_tree(dictionary, id=None):
    for key, value in dictionary.items():
        if key == 'id':
            if value == id:
                print dictionary
        else:
             traverse_tree(value, id)
    return

>>> traverse_tree({1: {'id': 2}, 2: {'id': 3}}, id=2)
{'id': 2}

Answer 3

Подобные проблемы часто лучше решать с помощью правильных определений классов, а не общих словарей.

class ProperObject( object ):
    """A proper class definition for each "attr" dictionary."""
    def __init__( self, path, attrDict ):
        self.path= path
        self.__dict__.update( attrDict )
    def __str__( self ):
        return "path %r, entity %r, hash %r, id %r" % (
            self.path, self.entity, self.hash, self.id )

masterDict= {} 
def builder( path, element ):
    masterDict[path]= ProperObject( path, element )

# Use the Visitor to build ProperObjects for each "attr"
walkDict( myDict, builder )

# Now that we have a simple dictionary of Proper Objects, things are simple
for k,v in masterDict.items():
    if v.id == '4130-2-2':
        print v

Кроме того, теперь, когда у вас есть правильные определения объектов, вы можете сделать следующее

# Create an "index" of your ProperObjects
import collections
byId= collections.defaultdict(list)
for k in masterDict:
    byId[masterDict[k].id].append( masterDict[k] )

# Look up a particular item in the index
print map( str, byId['4130-2-2'] )

Answer 4

Это старый вопрос, но по-прежнему лучший результат Google, поэтому я обновлю:

Мой друг и я опубликовали библиотеку, чтобы решить (почти) эту точную проблему. dpath-python (никакого отношения к модулю perl dpath, который делает подобные вещи).

http://github.com/akesterson/dpath-python

Все, что вам нужно сделать, это что-то вроде этого:

$ easy_install dpath
>>> import dpath.util
>>> results = []
>>> for (path, value) in dpath.util.search(my_dictionary, "*/attrs/entity/4130*", yielded=True):
>>> ... parent = dpath.util.search("/".join(path.split("/")[:-2])
>>> ... results.append(parent)

... это даст вам список всех объектов словаря, которые соответствуют вашему поиску, то есть всех объектов, которые имели (ключ = 4130 *) Родительский бит немного дергается, но это сработает.

Answer 5

Поскольку известно, что рекурсия ограничена в python (см. Какова максимальная глубина рекурсии в Python и как ее увеличить? ) Я предпочел бы иметь ответ на этот вопрос, основанный на цикле, поэтому ответ может быть адаптирован к любому уровню глубины в словаре. Для этого функция

def walkDict( aDict, visitor, path=() ):
    for  k in aDict:
        if k == 'attrs':
            visitor( path, aDict[k] )
        elif type(aDict[k]) != dict:
            pass
        else:
            walkDict( aDict[k], visitor, path+(k,) )

Может быть заменено на:

def walkDictLoop(aDict, visitor, path=()):
    toProcess = [(aDict, path)]
    while toProcess:
        dictNode, pathNode = toProcess.pop(0)
        for k in dictNode:
            if k == 'attrs':
                visitor(pathNode, dictNode[k])
            if isinstance(dictNode[k], dict):
                toProcess.append( (dictNode[k], pathNode+(k,)) )

Answer 6

Я верю, что pydash даст вам самый эффективный способ достичь этого.

Например:

data = {'a': {'b': {'c': [0, 0, {'d': [0, {1: 2}]}]}}, 'names': {'first': 'gus', 'second': 'parvez'}}

pydash.get(data, 'a.b.c.2.d.1.[1]')

# output: 2

Подробную документацию вы можете найти здесь: https://pydash.readthedocs.io/en/latest/quickstart.html

Answer 7

Ну, если вам нужно сделать это всего несколько раз, вы можете просто использовать вложенный dict.iteritems (), чтобы найти то, что вы ищете.

Если вы планируете сделать это несколько раз, выступления быстро станут проблемой. В этом случае вы могли бы:

• измените способ возврата данных на более подходящий.

• , если вы не можете, преобразуйте данные, как только они улетят, в раздел между id и ключами (используя iteritems). Тогда используйте это.