Python: a way to get an exhaustive, sorted list of keys in a nested dictionary?

Question

exhaustive :
- all keys in the dictionary, even if the keys are in a nested dictionary, which is the key value of the dictionary of the previous level.

sort :
- this means that keys are always returned in the same order

The embedding is arbitrarily deep. A non-recursive algorithm is preferred.

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

Note: dictionary values ​​may include lists (which may have dictionaries as elements), e.g.

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)

is an obvious (recursive) solution. To exclude recursion:

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 , , dict , ( , , per-instance per-class [, ], dicts ;-). , "" (, , ), , , . , , ( , , 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

. . : dicts dict, , , Alex Martelli.

#!/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', 'level3', 'z']
['category', 'content', 'content']

Answer 3

, , , dicts , :

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 4

...

#!/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()

Answer 5

, . .

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