defaultdict of arbitrary depth

131 views
Skip to first unread message

Paul McGuire

unread,
Aug 16, 2007, 11:25:13 PM8/16/07
to
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

unread,
Aug 17, 2007, 12:19:13 AM8/17/07
to Paul McGuire, pytho...@python.org
On Thu, 2007-08-16 at 20:25 -0700, Paul McGuire wrote:
> [...]

> 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)

--
Carsten Haese
http://informixdb.sourceforge.net


Paul McGuire

unread,
Aug 17, 2007, 12:27:11 AM8/17/07
to
> Carsten Haesehttp://informixdb.sourceforge.net- Hide quoted text -
>
> - Show quoted text -

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

unread,
Aug 17, 2007, 12:53:12 AM8/17/07
to Paul McGuire, pytho...@python.org
On Thu, 2007-08-16 at 21:27 -0700, Paul McGuire wrote:
> 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

unread,
Aug 17, 2007, 1:40:35 AM8/17/07
to pytho...@python.org
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

unread,
Aug 21, 2007, 8:49:51 PM8/21/07
to
Any reason why this wouldn't work?

>>> from collections import defaultdict
>>> def rdict(*args, **kw):
... return defaultdict(rdict, *args, **kw)
...
>>> d = rdict()
>>> d[1][2][3][4][5] # ...
defaultdict(<function rdict at 0x61370>, {})


~ Daniel

Paddy

unread,
Aug 22, 2007, 12:38:43 AM8/22/07
to
Reply all
Reply to author
Forward
0 new messages