Найти все вхождения ключа во вложенных словарях и списках

87

У меня есть такой словарь:

{ "id" : "abcde",
  "key1" : "blah",
  "key2" : "blah blah",
  "nestedlist" : [ 
    { "id" : "qwerty",
      "nestednestedlist" : [ 
        { "id" : "xyz",
          "keyA" : "blah blah blah" },
        { "id" : "fghi",
          "keyZ" : "blah blah blah" }],
      "anothernestednestedlist" : [ 
        { "id" : "asdf",
          "keyQ" : "blah blah" },
        { "id" : "yuiop",
          "keyW" : "blah" }] } ] } 

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

Как лучше всего обойти это, чтобы извлечь значения каждого ключа "id"? Я хочу получить эквивалент запроса XPath, например «// id». Значение «id» всегда является строкой.

Итак, в моем примере результат, который мне нужен, в основном:

["abcde", "qwerty", "xyz", "fghi", "asdf", "yuiop"]

Порядок не важен.

Мэтт Суэйн
источник
Большинство ваших решений взорвутся, если мы передадим их Noneна вход. Вы заботитесь о надежности? (поскольку теперь это используется как канонический вопрос)
smci

Ответы:

74

Я нашел этот вопрос / ответ очень интересным, поскольку он предлагает несколько различных решений одной и той же проблемы. Я взял все эти функции и протестировал их со сложным словарным объектом. Мне пришлось исключить две функции из теста, потому что у них было много неудачных результатов, и они не поддерживали возвращение списков или диктов в качестве значений, что я считаю важным, поскольку функция должна быть подготовлена ​​практически для любых данных.

Итак, я прокачал другие функции за 100000 итераций через timeitмодуль, и на выходе получился следующий результат:

0.11 usec/pass on gen_dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
6.03 usec/pass on find_all_items(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.15 usec/pass on findkeys(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
1.79 usec/pass on get_recursively(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.14 usec/pass on find(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -
0.36 usec/pass on dict_extract(k,o)
- - - - - - - - - - - - - - - - - - - - - - - - - - - - -

У всех функций была одна и та же стрелка для поиска ('ведение журнала') и один и тот же объект словаря, который построен следующим образом:

o = { 'temparature': '50', 
      'logging': {
        'handlers': {
          'console': {
            'formatter': 'simple', 
            'class': 'logging.StreamHandler', 
            'stream': 'ext://sys.stdout', 
            'level': 'DEBUG'
          }
        },
        'loggers': {
          'simpleExample': {
            'handlers': ['console'], 
            'propagate': 'no', 
            'level': 'INFO'
          },
         'root': {
           'handlers': ['console'], 
           'level': 'DEBUG'
         }
       }, 
       'version': '1', 
       'formatters': {
         'simple': {
           'datefmt': "'%Y-%m-%d %H:%M:%S'", 
           'format': '%(asctime)s - %(name)s - %(levelname)s - %(message)s'
         }
       }
     }, 
     'treatment': {'second': 5, 'last': 4, 'first': 4},   
     'treatment_plan': [[4, 5, 4], [4, 5, 4], [5, 5, 5]]
}

Все функции дали одинаковый результат, но разница во времени огромна! Функция gen_dict_extract(k,o)- это моя функция, адаптированная из приведенных здесь функций, на самом деле она очень похожа на findфункцию из Alfe, с основным отличием, что я проверяю, имеет ли данный объект функцию iteritems, в случае, если строки передаются во время рекурсии:

def gen_dict_extract(key, var):
    if hasattr(var,'iteritems'):
        for k, v in var.iteritems():
            if k == key:
                yield v
            if isinstance(v, dict):
                for result in gen_dict_extract(key, v):
                    yield result
            elif isinstance(v, list):
                for d in v:
                    for result in gen_dict_extract(key, d):
                        yield result

Таким образом, этот вариант является самым быстрым и безопасным из имеющихся здесь функций. И find_all_itemsон невероятно медленный и далеко от второго по скорости, в get_recursivleyто время как остальные, за исключением dict_extract, близки друг к другу. Функции funи keyHoleработают только в том случае, если вы ищете строки.

Интересный аспект обучения :)

программное обеспечение hexerei
источник
1
Если вы хотите искать несколько ключей, как я, просто: (1) измените значение на gen_dict_extract(keys, var)(2) поместите for key in keys:как строку 2 и сделайте отступ для остальных (3) измените первый выход наyield {key: v}
Бруно Броноски
6
Вы сравниваете яблоки с апельсинами. Выполнение функции, возвращающей генератор, занимает меньше времени, чем выполнение функции, возвращающей готовый результат. Попробуйте timeit next(functionname(k, o)для всех решений для генераторов.
kaleissin
6
hasattr(var, 'items')для python3
gobrewers14 08
1
Рассматривали ли вы удаление if hasattrчасти для версии, использующей tryдля перехвата исключения в случае сбоя вызова (см. Pastebin.com/ZXvVtV0g для возможной реализации)? Это уменьшит двойной поиск атрибута iteritems(один раз для hasattr()и один раз для вызова) и, таким образом, вероятно, сократит время выполнения (что кажется вам важным). Но никаких тестов не проводил.
Alfe
2
Для всех, кто посещает эту страницу теперь, когда Python 3 взял верх, помните, что iteritemsэто стало items.
Майк Уильямсон
46
d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [ 
    { "id" : "qwerty",
        "nestednestedlist" : [ 
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [ 
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] } 


def fun(d):
    if 'id' in d:
        yield d['id']
    for k in d:
        if isinstance(d[k], list):
            for i in d[k]:
                for j in fun(i):
                    yield j

>>> list(fun(d))
['abcde', 'qwerty', 'xyz', 'fghi', 'asdf', 'yuiop']
кев
источник
Единственное, что я бы изменил, это for k in dна for k,value in d.items()с последующим использованием valueвместо вместо d[k].
ovgolovin
Спасибо, отлично работает. Требуется очень небольшая модификация, потому что мои списки могут содержать как строки, так и dicts (о которых я не упоминал), но в остальном идеальны.
Мэтт Суэйн
1
Это подходит для очень узкого случая, вы обязаны рассмотреть ответ от «hexerei software» под названиемgen_dict_extract
Бруно Броноски
Я получил ошибку «TypeError: аргумент типа« NoneType »не повторяется»
xiaoshir
2
Похоже, это решение не поддерживает списки
Alex R
23
d = { "id" : "abcde",
    "key1" : "blah",
    "key2" : "blah blah",
    "nestedlist" : [
    { "id" : "qwerty",
        "nestednestedlist" : [
        { "id" : "xyz", "keyA" : "blah blah blah" },
        { "id" : "fghi", "keyZ" : "blah blah blah" }],
        "anothernestednestedlist" : [
        { "id" : "asdf", "keyQ" : "blah blah" },
        { "id" : "yuiop", "keyW" : "blah" }] } ] }


def findkeys(node, kv):
    if isinstance(node, list):
        for i in node:
            for x in findkeys(i, kv):
               yield x
    elif isinstance(node, dict):
        if kv in node:
            yield node[kv]
        for j in node.values():
            for x in findkeys(j, kv):
                yield x

print(list(findkeys(d, 'id')))
арайнчи
источник
1
Этот пример работал со всеми протестированными мной сложными словарями. Отлично сработано.
Это должен быть принятый ответ, он может находить ключи, которые находятся в словарях, которые вложены в список списков и т. Д.
Антон
Это работает и в Python3, если оператор печати в конце изменен. Ни одно из вышеперечисленных решений не сработало для ответа API со списками, вложенными в dicts, перечисленными внутри списков и т.д., но это сработало прекрасно.
Энди Форсено
21
def find(key, value):
  for k, v in value.iteritems():
    if k == key:
      yield v
    elif isinstance(v, dict):
      for result in find(key, v):
        yield result
    elif isinstance(v, list):
      for d in v:
        for result in find(key, d):
          yield result

РЕДАКТИРОВАТЬ: @Anthon заметил, что это не сработает для напрямую вложенных списков. Если у вас есть это на входе, вы можете использовать это:

def find(key, value):
  for k, v in (value.iteritems() if isinstance(value, dict) else
               enumerate(value) if isinstance(value, list) else []):
    if k == key:
      yield v
    elif isinstance(v, (dict, list)):
      for result in find(key, v):
        yield result

Но я думаю, что исходную версию легче понять, поэтому я оставлю ее.

Alfe
источник
1
Это тоже отлично работает, но также возникают проблемы, если он встречает список, который напрямую содержит строку (которую я забыл включить в свой пример). Я думаю, что добавление isinstanceпроверки dictперед двумя последними строками решит эту проблему.
Мэтт Суэйн,
1
Спасибо за похвалы, но я был бы более горд получить их за чистоту моего кода, чем за его скорость.
Alfe
1
В 95% случаев да. Остальные (редкие) случаи - это те, в которых некоторое ограничение по времени может вынудить меня выбрать более быструю версию вместо более чистой. Но мне это не нравится. Это всегда означает возложить на моего преемника, которому придется поддерживать этот код, много работы. Это риск, потому что мой преемник может запутаться. Тогда мне придется написать много комментариев, может быть, целый документ, объясняющий мои мотивы, сроки экспериментов, их результаты и т. Д. Это намного больше работы для меня и всех коллег, чтобы сделать это правильно. Очиститель намного проще.
Alfe 05
2
@Alfe - спасибо за этот ответ. Мне нужно было извлечь все вхождения строки во вложенном dict для конкретного варианта использования Elasticsearch, и этот код был полезен с незначительной модификацией - stackoverflow.com/questions/40586020/…
Саураб Хирани
1
Это полностью нарушает списки, непосредственно содержащиеся в списках.
Anthon
5

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

def find_all_items(obj, key, keys=None):
    """
    Example of use:
    d = {'a': 1, 'b': 2, 'c': {'a': 3, 'd': 4, 'e': {'a': 9, 'b': 3}, 'j': {'c': 4}}}
    for k, v in find_all_items(d, 'a'):
        print "* {} = {} *".format('->'.join(k), v)    
    """
    ret = []
    if not keys:
        keys = []
    if key in obj:
        out_keys = keys + [key]
        ret.append((out_keys, obj[key]))
    for k, v in obj.items():
        if isinstance(v, dict):
            found_items = find_all_items(v, key, keys=(keys+[k]))
            ret += found_items
    return ret
Долан Антенуччи
источник
5

Я просто хотел повторить отличный ответ @hexerei-software, используя yield fromи принимая списки верхнего уровня.

def gen_dict_extract(var, key):
    if isinstance(var, dict):
        for k, v in var.items():
            if k == key:
                yield v
            if isinstance(v, (dict, list)):
                yield from gen_dict_extract(v, key)
    elif isinstance(var, list):
        for d in var:
            yield from gen_dict_extract(d, key)
Крис
источник
Отличный мод на ответ @hexerei-software: лаконичный и допускающий список слов! Я использую это вместе с предложениями @bruno-bronosky в его комментариях for key in keys. Кроме того, я добавил к 2 isinstanceв (list, tuple)течение еще дополнительной разновидности. ;)
Cometsong
4

Эта функция рекурсивно ищет словарь, содержащий вложенные словари и списки. Он создает список под названием fields_found, который содержит значение для каждого случая обнаружения поля. «Поле» - это ключ, который я ищу в словаре, его вложенных списках и словарях.

def get_recursively (search_dict, поле):
    "" "Делает диктовку с вложенными списками и диктовками,
    и ищет во всех словарях ключ поля
    при условии.
    "" "
    fields_found = []

    для ключа значение в search_dict.iteritems ():

        если поле key ==:
            fields_found.append (значение)

        elif isinstance (значение, dict):
            results = get_recursively (значение, поле)
            для результата в результатах:
                fields_found.append (результат)

        elif isinstance (значение, список):
            для позиции по стоимости:
                если isinstance (item, dict):
                    more_results = get_recursively (элемент, поле)
                    для another_result в more_results:
                        fields_found.append (другой_результат)

    вернуть fields_found
Бекка Петрин
источник
1
Вы можете использовать fields_found.extend (more_results) вместо запуска другого цикла. На мой взгляд, выглядел бы немного чище.
sapit
0

Вот мой удар:

def keyHole(k2b,o):
  # print "Checking for %s in "%k2b,o
  if isinstance(o, dict):
    for k, v in o.iteritems():
      if k == k2b and not hasattr(v, '__iter__'): yield v
      else:
        for r in  keyHole(k2b,v): yield r
  elif hasattr(o, '__iter__'):
    for r in [ keyHole(k2b,i) for i in o ]:
      for r2 in r: yield r2
  return

Пример:

>>> findMe = {'Me':{'a':2,'Me':'bop'},'z':{'Me':4}}
>>> keyHole('Me',findMe)
<generator object keyHole at 0x105eccb90>
>>> [ x for x in keyHole('Me',findMe) ]
['bop', 4]
AX Labs
источник
0

Следуя ответу программного обеспечения @hexerei и комментарию @bruno-bronosky, если вы хотите перебрать список / набор ключей:

def gen_dict_extract(var, keys):
   for key in keys:
      if hasattr(var, 'items'):
         for k, v in var.items():
            if k == key:
               yield v
            if isinstance(v, dict):
               for result in gen_dict_extract([key], v):
                  yield result
            elif isinstance(v, list):
               for d in v:
                  for result in gen_dict_extract([key], d):
                     yield result    

Обратите внимание, что я передаю список с одним элементом ([key]} вместо строкового ключа.

Жоао Энрикес
источник