python：一種獲取嵌套字典中密鑰的排序列表的方法？

Question

窮舉：
- 字典中的所有鍵，即使鍵位於嵌套字典中，該嵌套字典是前一級詞典鍵的值。

排序：
- 這是爲了確保鍵總是以相同的順序

的嵌套任意深度返回。非遞歸算法是優選的。

level1 = { 
    'a'   : 'aaaa', 
    'level2_1' : {'b': 'bbbbb', 'level3': {'c': 'cccc', 'd': 'dddddd'} }, 
    'level2_2' : { 'z': 'zzzzzzz' } 
} 

注意：字典值可以包括列表（其可以具有字典作爲元素），例如，

tricky = {'category': [{'content': 'aaaaa'}, {'content': 'bbbbbb'}]}

Answer 1

def _auxallkeys(aset, adict): 
    aset.update(adict) 
    for d in adict.itervalues(): 
    if isinstance(d, dict): 
     _auxallkeys(aset, d) 

def allkeys(adict): 
    aset = set() 
    _auxallkeys(aset, adict) 
    return sorted(aset) 

是明顯的（遞歸）溶液。爲了消除遞歸：

def allkeys(adict): 
    aset = set() 
    pending = [adict] 
    while pending: 
    d = pending.pop() 
    aset.update(d) 
    for dd in d.itervalues(): 
     if isinstance(dd, dict): 
     pending.append(dd) 
    return sorted(aset) 

因爲不同的嵌套類型的字典處理的順序爲了這個目的並不重要。

編輯：在OP評論抱怨，如果字典不是嵌套它不工作，而是在列表（我回答說，它也可能是一個元組，一個對象，每個屬性 - 實例或每類[可能是其基類]，一個架子，以及許多其他方法來隱藏房子周圍的字典;-)。如果OP會屈尊來定義他所說的「嵌套」（顯然不是爲普通人申請到word中的問題相同的含義）正是，它可能會更容易地幫助他。同時，這裏有一個包含列表（和元組，但不包括而不是生成器，許多itertools類的實例，擱架等等）的版本;

def allkeys(adict): 
    aset = set() 
    pending = [adict] 
    pendlis = [] 

    def do_seq(seq): 
    for dd in seq: 
     if isinstance(dd, dict): 
     pending.append(dd) 
     elif isinstance(dd, (list, tuple)): 
     pendlis.append(dd) 

    while pending or pendlis: 
    while pending: 
     d = pending.pop() 
     aset.update(d) 
     do_seq(d.itervalues()) 
    while pendlis: 
     l = pendlis.pop() 
     do_seq(l) 

    return sorted(aset) 

Answer 2

我認爲最好使用遞歸方法。 我的代碼如下。

level1 = { 
    'a'   : 'aaaa', 
    'level2_1' : {'b': 'bbbbb', 'level3': {'c': 'cccc', 'd': 'dddddd'} }, 
    'level2_2' : { 'z': 'zzzzzzz' } 
} 

all_keys=[]  # a global list to store all the keys in level1 

def depth (dict): 
    for k in dict: 
     if type(dict[k]) == type(dict):  #judge the type of elements in dictionary 
      depth(dict[k])     # recursive 
     else: 
      all_keys.append(k) 

depth(level1) 

print all_keys 

Answer 3

非遞歸方法現在對我來說並不明顯。以下原型適用於您的原始示例。編輯：現在將處理字典中的列表中類型的字典，至少一個在亞歷克斯·馬爾泰利的答案註釋引用的棘手例子內。

#!/usr/bin/env python 
import types 

def get_key_list(the_dict, key_list): 
    for k, v in (the_dict.iteritems()): 
     key_list.append(k) 
     if type(v) is types.DictType: 
      get_key_list(v, key_list) 
     if type(v) is types.ListType: 
      for lv in v: 
       if type(lv) is types.DictType: 
        get_key_list(lv, key_list) 
    return 

level1 = { 
    'a'   : 'aaaa', 
    'level2_1' : {'b': 'bbbbb', 'level3': {'c': 'cccc', 'd': 'dddddd'} }, 
    'level2_2' : { 'z': 'zzzzzzz' } 
} 
tricky = {'category': [{'content': 'aaaaa'}, {'content': 'bbbbbb'}]} 

key_list = [] 
get_key_list(level1, key_list) 
key_list.sort() 
print key_list 

key_list = [] 
get_key_list(tricky, key_list) 
key_list.sort() 
print key_list 

輸出：

[ 'A'， 'B'， 'C'， 'd'， 'level2_1'， 'level2_2'， '級別3'， 'Z']
[「類」，「內容」，「內容」]

Answer 4

這裏有一個非遞歸解決方案，處理髮電機以及列表，元組和類型的字典，並增加了所有連續按鍵是否有鍵多次出現：

def get_iterator(i): 
    if hasattr(i, 'next'): 
     # already an iterator - use it as-is! 
     return i 
    elif hasattr(i, '__iter__') and not isinstance(i, basestring): 
     # an iterable type that isn't a string 
     return iter(i) 
    else: 
     # Can't iterate most other types! 
     return None 

def get_dict_keys(D): 
    LRtn = [] 
    L = [(D, get_iterator(D))] 
    while 1: 
     if not L: break 
     cur, _iter = L[-1] 

     if _iter: 
      # Get the next item 
      try: 
       i = _iter.next() 
      except StopIteration: 
       del L[-1] 
       continue 

     if isinstance(cur, dict): 
      # Process a dict and all subitems 
      LRtn.append(i) 

      _iter = get_iterator(cur[i]) 
      if _iter: L.append((cur[i], _iter)) 
     else: 
      # Process generators, lists, tuples and all subitems 
      _iter = get_iterator(i) 
      if _iter: L.append((i, _iter)) 

    # Sort and return 
    LRtn.sort() 
    return LRtn 

D = { 
    'a'   : 'aaaa', 
    'level2_1' : {'b': 'bbbbb', 'level3': {'c': 'cccc', 'd': 'dddddd', 'e': 134, 'f': [{'blah': 553}]} }, 
    'level2_2' : { 'z': 'zzzzzzz' }, 
    'blah2': iter([{'blah3': None}]), 
} 

print get_dict_keys(D) 

編輯：增加速度的位和取得的代碼越短。

Answer 5

我也喜歡一個遞歸方法...

#!/usr/bin/env python 

def extract_all_keys(structure): 
    try: 
     list_of_keys = structure.keys() 
     for value in structure.values(): 
      add_all_keys_in_value_to_list(value, list_of_keys) 
    except AttributeError: 
     list_of_keys = [] 
    return list_of_keys.sort() 


def add_all_keys_in_value_to_list(value, list_of_keys): 
    if isinstance(value, dict): 
     list_of_keys += extract_all_keys(value) 
    elif isinstance(value, (list, tuple)): 
     for element in value: 
      list_of_keys += extract_all_keys(element) 


import unittest 

class TestKeys(unittest.TestCase): 

    def given_a_structure_of(self, structure): 
     self.structure = structure 


    def when_keys_are_extracted(self): 
     self.list_of_keys = extract_all_keys(self.structure) 


    def testEmptyDict(self): 
     self.given_a_structure_of({}) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, []) 


    def testOneElement(self): 
     self.given_a_structure_of({'a': 'aaaa'}) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['a']) 


    def testTwoElementsSorted(self): 
     self.given_a_structure_of({ 
      'z': 'zzzz', 
      'a': 'aaaa', 
      }) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['a', 'z']) 


    def testNestedElements(self): 
     self.given_a_structure_of({ 
      'a': {'aaaa': 'A',}, 
      'b': {'bbbb': 'B',}, 
      }) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['a', 'aaaa', 'b', 'bbbb']) 


    def testDoublyNestedElements(self): 
     self.given_a_structure_of({ 
      'level2': {'aaaa': 'A', 
       'level3': {'bbbb': 'B'} 
       } 
      }) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['aaaa', 'bbbb', 'level2', 'level3']) 


    def testNestedExampleOnStackOverflow(self): 
     level1 = { 
       'a'   : 'aaaa', 
       'level2_1' : {'b': 'bbbbb', 'level3': {'c': 'cccc', 'd': 'dddddd'} }, 
       'level2_2' : { 'z': 'zzzzzzz' } 
       } 
     self.given_a_structure_of(level1) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['a', 'b', 'c', 'd', 'level2_1', 'level2_2', 'level3', 'z']) 


    def testListExampleOnStackOverflow(self): 
     tricky = {'category': [{'content': 'aaaaa'}, {'content': 'bbbbbb'}]} 
     self.given_a_structure_of(tricky) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['category', 'content', 'content']) 


    def testTuplesTreatedLikeLists(self): 
     tricky_tuple = {'category': ({'content': 'aaaaa'}, {'content': 'bbbbbb'})} 
     self.given_a_structure_of(tricky_tuple) 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, ['category', 'content', 'content']) 


    def testCanHandleString(self): 
     self.given_a_structure_of('keys') 
     self.when_keys_are_extracted() 
     self.assertEquals(self.list_of_keys, []) 

if __name__ == '__main__': 
    unittest.main()