DjangoBB LoFi version

Полная версия: Рекурсивный поиск по вложенным словарям

Начало » Python для новичков » Рекурсивный поиск по вложенным словарям

1 2

latino2003

Июль 14, 2015 12:24:36

Shaman
Судя по описанию структуры там нет словарей в списках и она вырождается в многомерный слорварь.

Все верно. Но сути вопроса это не меняет:
пройтись рекурсивно по словарю и
1. найти ключ равный match_key и вернуть его значения
2. найти элемент списка по части значения(найти элемент “Москва” по запросу “оскв”)

Shaman

Июль 14, 2015 12:53:31

latino2003
Все верно. Но сути вопроса это не меняет:

Меняет. Избавляемся от рекурсии, но там есть свои минусы в работе с иерархией. Если не нужно работать с конкретными уровнями, тогда, может, будет проще.

py.user.next

Июль 14, 2015 12:58:17

latino2003
Структура данных состоит из двух типов - словарь и список.

Напиши, что возвращает каждый вызов:

f(['a', 'b', 'c'], 'a')
 
f({'a': ['b', 'c']}, 'a')
 
f({'a': ['b', 'c']}, 'c')
 
f({'a': {'b': []}}, 'b')

Напиши, являются ли эти вызовы валидными:

f({'a': 'b'}, 'a')
 
f([{'a': 'b'}], 'a')
 
f({'a': {'b': 'c'}}, 'b')
 
f({'a': {'b': 'c'}}, 'c')

latino2003

Июль 14, 2015 14:41:54

py.user.next
Напиши, что возвращает каждый вызов:
f(['a', 'b', 'c'], 'a') -> 'a'
f({'a': ['b', 'c']}, 'a') -> (key,values) = ('a', 'b', 'c')
f({'a': ['b', 'c']}, 'c') -> 'c'
f({'a': {'b': []}}, 'b') -> (key,values) = ('b') 
Напиши, являются ли эти вызовы валидными:
f({'a': 'b'}, 'a') #значением словаря может быть только список или словарь
f([{'a': 'b'}], 'a') #список может содержать только юникод-элементы
f({'a': {'b': 'c'}}, 'b') #значением словаря может быть только список или словарь
f({'a': {'b': 'c'}}, 'c') #значением словаря может быть только список или словарь
Все вызовы невалидны, так как:
словари могут содержать в качестве значений только список или словарь
списки не могут быть многомерным и содержат только юникод-элементы -
['a', 'b', 'c']

py.user.next

Июль 15, 2015 00:38:30

>>> def find_in_list(lst, key):
...     assert isinstance(lst, list)
...     if key in lst:
...         return key
... 
>>> def find_in_dict(dct, key):
...     assert isinstance(dct, dict)
...     if key in dct:
...         return [key] + dct[key]
...     else:
...         for i in dct.values():
...             out = find(i, key)
...             if out is not None:
...                 return out    
... 
>>> def find(cont, key):
...     if isinstance(cont, list):
...         return find_in_list(cont, key)
...     elif isinstance(cont, dict):
...         return find_in_dict(cont, key)
... 
>>> 
>>> info = [u'no', u'информацьион']
>>> address = [u'Москва', u'Верхние поля', u'18а']
>>> phones = ['ph1', 'ph2']
>>> vasya = {u'информация':info,
...          u'адрес':address,
...          u'телефоны':phones}
>>> 
>>> prot = []
>>> base = [u'ground']
>>> part = [1, 2, 3]
>>> fedya = {u'протокол':prot,
...          u'база':base,
...          u'партия':part}
>>> 
>>> mila = [u'abc', u'безнадега', u'точка ру']
>>> main_dict = {u'вася пупкин':vasya,
...              u'федя негров':fedya,
...              u'мила йовович':mila}
>>> 
>>> find(main_dict, u'телефоны')
['телефоны', 'ph1', 'ph2']
>>>

latino2003

Июль 15, 2015 09:34:09

Блин, вооот в чем проблема моей ошибки в использовании рекурсии - надо было разбить на две функции, а я голову сломал. Спасибо!

py.user.next

Июль 15, 2015 09:44:12

latino2003
надо было разбить на две функции

Это взаимно-рекурсивные функции: find() вызывает find_in_dict(), а find_in_dict() вызывает find().