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

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

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

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
•  at Nov 4, 2010 at 6:09 pm ⇧

macm wrote:

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
•  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
•  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 Overview
 group python-list categories python posted Nov 4, '10 at 4:18p active Nov 6, '10 at 5:51p posts 9 users 6 website python.org

### 6 users in discussion

Content

People

Support

Translate

site design / logo © 2022 Grokbase