FAQ
Hi Folks

How find all childrens values of a nested dictionary, fast!
a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}}, 'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}
a['a']
{'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
a['a']['b']
{'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
[68, 69, 66]}, '/': [51, 52, 54]}}
a['a']['b'].values()
[{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
[51, 52, 54]}]

Now I want find all values of key "/"

Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]

I am trying map, reduce, lambda.

Regards

macm

Search Discussions

  • Diez B. Roggisch at Nov 4, 2010 at 5:21 pm

    macm <moura.mario at gmail.com> writes:

    Hi Folks

    How find all childrens values of a nested dictionary, fast!
    There is no faster than O(n) here.
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}}, 'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}
    a['a']
    {'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
    2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
    a['a']['b']
    {'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
    [68, 69, 66]}, '/': [51, 52, 54]}}
    a['a']['b'].values()
    [{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
    [51, 52, 54]}]

    Now I want find all values of key "/"

    Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}}, 'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}


    def f(d):
    if "/" in d:
    for v in d["/"]:
    yield v
    for value in d.values():
    if isinstance(value, dict):
    for v in f(value):
    yield v


    print list(f(a))

    But that gives me a different result:

    [5, 6, 7, 8, 1, 2, 3, 4, 41, 42, 44, 51, 52, 54, 68, 69, 66, 21, 22,
    23, 12, 13, 14, 15]

    Why don't you expect e.g. 23 in your output?

    Diez
  • John Ladasky at Nov 6, 2010 at 4:06 am

    On Nov 4, 10:21?am, de... at web.de (Diez B. Roggisch) wrote:
    macm <moura.ma... at gmail.com> writes:
    ? ? for value in d.values():
    ? ? ? ? if isinstance(value, dict):
    I'm not a Python guru, but... do you care that you're breaking duck
    typing here? I've had other programmers warn me against using
    isinstance() for this reason. Yes, it's part of the Python language,
    but some people wonder whether it should be there.
  • Peter Otten at Nov 4, 2010 at 5:26 pm

    macm wrote:

    How find all childrens values of a nested dictionary, fast!
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc'
    :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}},
    'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}} a['a']
    {'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
    2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
    a['a']['b']
    {'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
    [68, 69, 66]}, '/': [51, 52, 54]}}
    a['a']['b'].values()
    [{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
    [51, 52, 54]}]

    Now I want find all values of key "/"

    Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]

    I am trying map, reduce, lambda.
    Hmm, I'm trying none of these and get a different result:
    def f(d):
    ... stack = [d.iteritems()]
    ... while stack:
    ... for k, v in stack[-1]:
    ... if k == "/":
    ... yield v
    ... else:
    ... stack.append(v.iteritems())
    ... break
    ... else:
    ... stack.pop()
    ...
    b = []
    for v in f(a):
    ... b.extend(v)
    ...
    b
    [5, 6, 7, 8, 41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54, 21, 22, 23, 12,
    13, 14, 15]

    What am I missing?

    Peter
  • Macm at Nov 4, 2010 at 5:56 pm
    Hi Folks

    Thanks a lot

    Script from Diez works:

    print list(f(a))

    but should be

    print list(f(a['a']['b']))

    to fit my example.



    About Peter script

    I am receiving
    for v in f(a['a']['b']):
    ... b.extend(v)
    ...
    Traceback (most recent call last):
    File "<stdin>", line 2, in <module>
    TypeError: 'int' object is not iterable

    I am trying understand this error.

    Best Regards and thanks a lot again!

    Mario
    macm





    On 4 nov, 15:26, Peter Otten wrote:
    macm wrote:
    How find all childrens values of a nested dictionary, fast!
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc'
    :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}},
    'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}} a['a']
    {'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
    2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
    a['a']['b']
    {'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
    [68, 69, 66]}, '/': [51, 52, 54]}}
    a['a']['b'].values()
    [{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
    [51, 52, 54]}]
    Now I want find all values of key "/"
    Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]
    I am trying map, reduce, lambda.
    Hmm, I'm trying none of these and get a different result:
    def f(d):
    ... ? ? stack = [d.iteritems()]
    ... ? ? while stack:
    ... ? ? ? ? ? ? for k, v in stack[-1]:
    ... ? ? ? ? ? ? ? ? ? ? if k == "/":
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? yield v
    ... ? ? ? ? ? ? ? ? ? ? else:
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? stack.append(v.iteritems())
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? break
    ... ? ? ? ? ? ? else:
    ... ? ? ? ? ? ? ? ? ? ? stack.pop()
    ...>>> b = []
    for v in f(a):
    ... ? ? b.extend(v)
    ...>>> b

    [5, 6, 7, 8, 41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54, 21, 22, 23, 12,
    13, 14, 15]

    What am I missing?

    Peter
  • Macm at Nov 4, 2010 at 6:01 pm
    Peter

    Ok! Both works fine!

    Thanks a lot!
    for v in f(a['a']['b']):
    ... b.extend(v)

    b

    Now I will try find which script is the fast!

    Regards

    macm


    On 4 nov, 15:56, macm wrote:
    Hi Folks

    Thanks a lot

    Script from Diez works:

    print list(f(a))

    but should be

    print list(f(a['a']['b']))

    to fit my example.

    About Peter script

    I am receiving
    for v in f(a['a']['b']):
    ... ? ? b.extend(v)
    ...
    Traceback (most recent call last):
    ? File "<stdin>", line 2, in <module>
    TypeError: 'int' object is not iterable

    I am trying understand this error.

    Best Regards and thanks a lot again!

    Mario
    macm
    On 4 nov, 15:26, Peter Otten wrote:

    macm wrote:
    How find all childrens values of a nested dictionary, fast!
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc'
    :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}},
    'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}} a['a']
    {'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
    2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
    a['a']['b']
    {'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
    [68, 69, 66]}, '/': [51, 52, 54]}}
    a['a']['b'].values()
    [{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
    [51, 52, 54]}]
    Now I want find all values of key "/"
    Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]
    I am trying map, reduce, lambda.
    Hmm, I'm trying none of these and get a different result:
    def f(d):
    ... ? ? stack = [d.iteritems()]
    ... ? ? while stack:
    ... ? ? ? ? ? ? for k, v in stack[-1]:
    ... ? ? ? ? ? ? ? ? ? ? if k == "/":
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? yield v
    ... ? ? ? ? ? ? ? ? ? ? else:
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? stack.append(v.iteritems())
    ... ? ? ? ? ? ? ? ? ? ? ? ? ? ? break
    ... ? ? ? ? ? ? else:
    ... ? ? ? ? ? ? ? ? ? ? stack.pop()
    ...>>> b = []
    for v in f(a):
    ... ? ? b.extend(v)
    ...>>> b
    [5, 6, 7, 8, 41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54, 21, 22, 23, 12,
    13, 14, 15]
    What am I missing?
    Peter
  • Peter Otten at Nov 4, 2010 at 6:09 pm

    macm wrote:

    About Peter script

    I am receiving
    for v in f(a['a']['b']):
    ... b.extend(v)
    ...
    Traceback (most recent call last):
    File "<stdin>", line 2, in <module>
    TypeError: 'int' object is not iterable

    I am trying understand this error.
    You are probably mixing Diez' implementation of f() with my invocation code.
    Or you have modified the input data and now it contains int values.

    Peter
  • Arnaud Delobelle at Nov 4, 2010 at 9:20 pm

    macm <moura.mario at gmail.com> writes:

    Hi Folks

    How find all childrens values of a nested dictionary, fast!
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]} ,'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}}, 'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}
    a['a']
    {'c': {'/': [5, 6, 7, 8]}, 'b': {'ba': {'/': [41, 42, 44]}, '/': [1,
    2, 3, 4], 'bc': {'bcd': {'/': [68, 69, 66]}, '/': [51, 52, 54]}}}
    a['a']['b']
    {'ba': {'/': [41, 42, 44]}, '/': [1, 2, 3, 4], 'bc': {'bcd': {'/':
    [68, 69, 66]}, '/': [51, 52, 54]}}
    a['a']['b'].values()
    [{'/': [41, 42, 44]}, [1, 2, 3, 4], {'bcd': {'/': [68, 69, 66]}, '/':
    [51, 52, 54]}]

    Now I want find all values of key "/"

    Desire result is [41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54]

    I am trying map, reduce, lambda.
    Tough requirement, but I think I've got it. Two lambdas, one reduce,
    one map ;)
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]}, 'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}},'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}
    f = lambda v,k=None: v if k=="/" else reduce(list.__add__, map(lambda k: f(v[k],k), v), [])
    f(a)
    [5, 6, 7, 8, 41, 42, 44, 1, 2, 3, 4, 68, 69, 66, 51, 52, 54, 21, 22, 23, 12, 13, 14, 15]

    This doesn't correspond with your desire result though.

    --
    Arnaud
  • Alexander Gattin at Nov 6, 2010 at 5:51 pm
    Hello,

    On Thu, Nov 04, 2010 at 09:20:04PM +0000, Arnaud
    Delobelle wrote:
    Tough requirement, but I think I've got it. Two
    lambdas, one reduce, one map ;)
    a = {'a' : {'b' :{'/' :[1,2,3,4], 'ba' :{'/' :[41,42,44]}, 'bc' :{'/':[51,52,54], 'bcd' :{'/':[68,69,66]}}},'c' :{'/' :[5,6,7,8]}},'ab' : {'/' :[12,13,14,15]}, 'ac' :{'/' :[21,22,23]}}
    f = lambda v,k=None: v if k=="/" else reduce(list.__add__, map(lambda k: f(v[k],k), v), [])
    Is it that new Python3 thing? :)

    P.S.

    Here is my variant that still works
    in python2:

    def i(x):
    r = []
    for k, v in x.iteritems():
    try: r.extend(i(v))
    except:
    if k == '/': r.extend(v)
    return r

    --
    With best regards,
    xrgtn

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedNov 4, '10 at 4:18p
activeNov 6, '10 at 5:51p
posts9
users6
websitepython.org

People

Translate

site design / logo © 2022 Grokbase