How find all childrens values of a nested dictionary, fast!

[macm]

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

 

[Diez B. Roggisch]

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

 

[Peter Otten]

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:
.... 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)
....[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]

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

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:

...     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 = []
...     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]

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

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

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:

...     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]

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]

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.

 

[John Ladasky]

macm <[email protected]> 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.

 

[Alexander Gattin]

Hello,

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