defaultdict of arbitrary depth

[Paul McGuire]

In responding to another post on defaultdict, I posted an
implementation of a 2-level hashtable, by creating a factory method
that returned a defaultdict(dict). The OP of that other thread was
trying to build a nested tree from a set of n-tuples, in which the
first (n-1) values in each tuple were the keys for navigating down the
tree, and the final n'th value was the value for to be assigned to the
leaf node. My post worked only if n=2, which fortunately was the test
case that the OP gave. But it annoyed me that this required advance
knowledge of the number of keys.

I've hacked out this recursivedefaultdict which is a
defaultdict(defaultdict(defaultdict(...))), arbitrarily deep depending
on the keys provided in the reference.

Please comment.

-- Paul


from collections import defaultdict

data = [
('A','B','Z',1), ('A','C','Y',2), ('A','C','X',3),
('B','A','W',4), ('B','B','V',5), ('B','B','U',6),
('B','D','T',7),
]

class recursivedefaultdict(object):
def __init__(self):
self.__dd = defaultdict(recursivedefaultdict)
def __getattr__(self,attr):
return self.__dd.__getattribute__(attr)
def __getitem__(self,*args):
return self.__dd.__getitem__(*args)
def __setitem__(self,*args):
return self.__dd.__setitem__(*args)

table = recursivedefaultdict()

for k1,k2,k3,v in data:
table[k1][k2][k3] = v

for kk in sorted(table.keys()):
print "-",kk
for jj in sorted(table[kk].keys()):
print " -",jj
for ii in sorted(table[kk][jj].keys()):
print " -",ii,table[kk][jj][ii]

prints:
- A
- B
- Z 1
- C
- X 3
- Y 2
- B
- A
- W 4
- B
- U 6
- V 5
- D
- T 7

 

[Carsten Haese]

[...]
I've hacked out this recursivedefaultdict which is a
defaultdict(defaultdict(defaultdict(...))), arbitrarily deep depending
on the keys provided in the reference.

Please comment.
[...]

class recursivedefaultdict(object):
def __init__(self):
self.__dd = defaultdict(recursivedefaultdict)
def __getattr__(self,attr):
return self.__dd.__getattribute__(attr)
def __getitem__(self,*args):
return self.__dd.__getitem__(*args)
def __setitem__(self,*args):
return self.__dd.__setitem__(*args)

This is shorter:

from collections import defaultdict

class recursivedefaultdict(defaultdict):
def __init__(self):
self.default_factory = type(self)

 

[Paul McGuire]

[...]
I've hacked out this recursivedefaultdict which is a
defaultdict(defaultdict(defaultdict(...))), arbitrarily deep depending
on the keys provided in the reference.

Please comment.
[...]

class recursivedefaultdict(object):
def __init__(self):
self.__dd = defaultdict(recursivedefaultdict)
def __getattr__(self,attr):
return self.__dd.__getattribute__(attr)
def __getitem__(self,*args):
return self.__dd.__getitem__(*args)
def __setitem__(self,*args):
return self.__dd.__setitem__(*args)

This is shorter:

from collections import defaultdict

class recursivedefaultdict(defaultdict):
def __init__(self):
self.default_factory = type(self)

Of course, very short and sweet! Any special reason you wrote:
self.default_factory = type(self)
instead of:
self.default_factory = recursivedefaultdict
?


-- Paul

 

[Carsten Haese]

Of course, very short and sweet! Any special reason you wrote:
self.default_factory = type(self)
instead of:
self.default_factory = recursivedefaultdict
?

Besides a pathological need to be clever? The former keeps the
recursive relationship intact if you define a class that inherits from
recursivedefaultdict. The latter would create the nested entries of the
derived class as "vanilla" recursivedefaultdicts instead of instances of
the derived class. Whether this would matter in practice is, of course,
a different question.

 

[Steve Holden]

[...]
I've hacked out this recursivedefaultdict which is a
defaultdict(defaultdict(defaultdict(...))), arbitrarily deep depending
on the keys provided in the reference.
Please comment.
[...]
class recursivedefaultdict(object):
def __init__(self):
self.__dd = defaultdict(recursivedefaultdict)
def __getattr__(self,attr):
return self.__dd.__getattribute__(attr)
def __getitem__(self,*args):
return self.__dd.__getitem__(*args)
def __setitem__(self,*args):
return self.__dd.__setitem__(*args)

This is shorter:

from collections import defaultdict

class recursivedefaultdict(defaultdict):
def __init__(self):
self.default_factory = type(self)

Of course, very short and sweet! Any special reason you wrote:
self.default_factory = type(self)
instead of:
self.default_factory = recursivedefaultdict
?

It's more robust under subclassing.

regards
Steve
--
Steve Holden +1 571 484 6266 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://del.icio.us/steve.holden
--------------- Asciimercial ------------------
Get on the web: Blog, lens and tag the Internet
Many services currently offer free registration
----------- Thank You for Reading -------------

 

[Daniel]

Any reason why this wouldn't work?
.... return defaultdict(rdict, *args, **kw)
....

d = rdict()
d[1][2][3][4][5] # ...

defaultdict(<function rdict at 0x61370>, {})


~ Daniel

 

[Paddy]

In responding to another post on defaultdict, I posted an
implementation of a 2-level hashtable, by creating a factory method
that returned a defaultdict(dict). The OP of that other thread was
trying to build a nested tree from a set of n-tuples, in which the
first (n-1) values in each tuple were the keys for navigating down the
tree, and the final n'th value was the value for to be assigned to the
leaf node. My post worked only if n=2, which fortunately was the test
case that the OP gave. But it annoyed me that this required advance
knowledge of the number of keys.

I've hacked out this recursivedefaultdict which is a
defaultdict(defaultdict(defaultdict(...))), arbitrarily deep depending
on the keys provided in the reference.

Please comment.

-- Paul

from collections import defaultdict

data = [
('A','B','Z',1), ('A','C','Y',2), ('A','C','X',3),
('B','A','W',4), ('B','B','V',5), ('B','B','U',6),
('B','D','T',7),
]

class recursivedefaultdict(object):
def __init__(self):
self.__dd = defaultdict(recursivedefaultdict)
def __getattr__(self,attr):
return self.__dd.__getattribute__(attr)
def __getitem__(self,*args):
return self.__dd.__getitem__(*args)
def __setitem__(self,*args):
return self.__dd.__setitem__(*args)

table = recursivedefaultdict()

for k1,k2,k3,v in data:
table[k1][k2][k3] = v

for kk in sorted(table.keys()):
print "-",kk
for jj in sorted(table[kk].keys()):
print " -",jj
for ii in sorted(table[kk][jj].keys()):
print " -",ii,table[kk][jj][ii]

prints:
- A
- B
- Z 1
- C
- X 3
- Y 2
- B
- A
- W 4
- B
- U 6
- V 5
- D
- T 7

There is something here:
http://groups.google.com/group/comp.lang.python/msg/92502e0278c2a56e

- Paddy.