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

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

{'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 подходит, пожалуйста.

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

Edit (2): Исправлен код.

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

 dreftymac30 окт. 2017 г., 20:55
 Josh Petitt27 июн. 2014 г., 01:27
для «4130-2-1» вы хотите «key4», а не «key5», верно? «key5» содержит «4130-2-2».

Ответы на вопрос(7)

Это старый вопрос, но по-прежнему лучший результат 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 *). Родительский бит немного дергается, но это сработает.

 dreftymac22 нояб. 2017 г., 02:35
Это отличная библиотека. Это заслуживает гораздо большего внимания.

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

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

измените способ, которым ваши данные возвращаются вам на что-то более подходящее.

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

 JV.19 дек. 2008 г., 13:23
Идея, когда мы создали эту структуру, заключалась в том, чтобы получить к ней доступ через ключи - как - key1, key2 и т. д. Теперь я наткнулся на требование доступа через эти идентификаторы. Второй пункт - хорошее предложение, попробуем это.
Решение Вопроса

Ваша структура неприятно нерегулярна. Вот версия спосетитель функция, которая пересекает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...
 S.Lott19 дек. 2008 г., 14:04
@JV: внутренние словари "attrs" опрометчивы. Это кандидаты в объекты определенного класса, а не просто анонимные словари.
 JV.19 дек. 2008 г., 14:23
+1 за использование посетителя
 JV.19 дек. 2008 г., 13:54
У меня есть огромная коллекция из них, если вы можете предложить лучшую структуру с поддержкой произвольного уровня, простотой вставки и извлечения, это будет здорово. К тому времени, как вы определите эту структуру, я попробую ваше решение. Благодарю.

независимо от того, сколько уровней вложенности у вас есть в вашем 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}
 JV.19 дек. 2008 г., 13:18
Я исправил пример кода, о котором идет речь, пожалуйста, пересмотрите
 JV.19 дек. 2008 г., 14:18
Я проголосовал за вас, не знаю, как выбрать 2 ответа, иначе я бы выбрал и этот. :)
 PEZ19 дек. 2008 г., 13:06
Это не работает, когда я пробую это на моей машине.

Например:

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

Поскольку известно, что рекурсия ограничена в 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,)) )

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

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'] )
 S.Lott19 дек. 2008 г., 21:56
Если вы выполняете много поисков, затраты на преобразование в Objects, а затем в индекс по id идентифицируются в поисках. Построение объектов - это O (n). Построение индекса - O (n) и может быть сделано, поскольку объекты строятся. Поиск по идентификатору O (1).

Ваш ответ на вопрос