python - posiciones - ¿Cuál es la mejor manera de implementar diccionarios anidados?

propiedades diccionarios python

Question

Tengo una estructura de datos que básicamente equivale a un diccionario anidado. Digamos que se ve así:

{''new jersey'': {''mercer county'': {''plumbers'': 3,
                                  ''programmers'': 81},
                ''middlesex county'': {''programmers'': 81,
                                     ''salesmen'': 62}},
 ''new york'': {''queens county'': {''plumbers'': 9,
                                ''salesmen'': 36}}}

Ahora, mantener y crear esto es bastante doloroso; cada vez que tengo un nuevo estado / condado / profesión, tengo que crear los diccionarios de capa inferior a través de detestables bloques try / catch. Además, tengo que crear iteradores anidados molestos si quiero revisar todos los valores.

También podría usar tuplas como claves, como estas:

{(''new jersey'', ''mercer county'', ''plumbers''): 3,
 (''new jersey'', ''mercer county'', ''programmers''): 81,
 (''new jersey'', ''middlesex county'', ''programmers''): 81,
 (''new jersey'', ''middlesex county'', ''salesmen''): 62,
 (''new york'', ''queens county'', ''plumbers''): 9,
 (''new york'', ''queens county'', ''salesmen''): 36}

Esto hace que iterar sobre los valores sea muy simple y natural, pero es más sintácticamente doloroso hacer cosas como agregaciones y mirar subconjuntos del diccionario (por ejemplo, si solo quiero ir estado por estado).

Básicamente, a veces quiero pensar en un diccionario anidado como un diccionario plano, y a veces quiero pensar en él como una jerarquía compleja. Podría envolver todo esto en una clase, pero parece que alguien ya podría haber hecho esto. Alternativamente, parece que puede haber algunas construcciones sintácticas realmente elegantes para hacer esto.

¿Cómo podría hacerlo mejor?

Addendum: conozco setdefault() pero realmente no setdefault() una sintaxis limpia. Además, cada sub-diccionario que cree todavía necesita tener setdefault() configurado manualmente.

Answer 1

¿Cuál es la mejor forma de implementar diccionarios anidados en Python?

Implementa __missing__ en una subclase dict para establecer y devolver una nueva instancia.

Este enfoque ha estado disponible (y documentado) desde Python 2.5, y (particularmente valioso para mí) imprime bastante como un dict normal , en lugar de la fea impresión de un default de autovigilancia:

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)() # retain local pointer to value
        return value                     # faster to return than dict lookup

(Observe que self[key] está en el lado izquierdo de la asignación, por lo que no hay recursión aquí).

y di que tienes algunos datos:

data = {(''new jersey'', ''mercer county'', ''plumbers''): 3,
        (''new jersey'', ''mercer county'', ''programmers''): 81,
        (''new jersey'', ''middlesex county'', ''programmers''): 81,
        (''new jersey'', ''middlesex county'', ''salesmen''): 62,
        (''new york'', ''queens county'', ''plumbers''): 9,
        (''new york'', ''queens county'', ''salesmen''): 36}

Aquí está nuestro código de uso:

vividict = Vividict()
for (state, county, occupation), number in data.items():
    vividict[state][county][occupation] = number

Y ahora:

>>> import pprint
>>> pprint.pprint(vividict, width=40)
{''new jersey'': {''mercer county'': {''plumbers'': 3,
                                  ''programmers'': 81},
                ''middlesex county'': {''programmers'': 81,
                                     ''salesmen'': 62}},
 ''new york'': {''queens county'': {''plumbers'': 9,
                                ''salesmen'': 36}}}

Crítica

Una crítica a este tipo de contenedor es que si el usuario escribe mal una clave, nuestro código podría fallar silenciosamente:

>>> vividict[''new york''][''queens counyt'']
{}

Y, además, ahora tendríamos un condado mal escrito en nuestros datos:

>>> pprint.pprint(vividict, width=40)
{''new jersey'': {''mercer county'': {''plumbers'': 3,
                                  ''programmers'': 81},
                ''middlesex county'': {''programmers'': 81,
                                     ''salesmen'': 62}},
 ''new york'': {''queens county'': {''plumbers'': 9,
                                ''salesmen'': 36},
              ''queens counyt'': {}}}

Explicación:

Solo proporcionamos otra instancia anidada de nuestra clase Vividict cada vez que se accede a una clave pero falta. (Devolver la asignación de valor es útil porque nos evita adicionalmente llamar al getter en el dict, y desafortunadamente, no podemos devolverlo tal como se establece).

Tenga en cuenta que esta es la misma semántica que la respuesta más votada, pero en la mitad de las líneas de código, la implementación de nosklo:

class AutoVivification(dict):
    """Implementation of perl''s autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

Demostración de uso

A continuación se muestra solo un ejemplo de cómo este dict se puede usar fácilmente para crear una estructura dict anidada sobre la marcha. Esto puede crear rápidamente una estructura jerárquica de árbol tan profundamente como desee.

import pprint

class Vividict(dict):
    def __missing__(self, key):
        value = self[key] = type(self)()
        return value

d = Vividict()

d[''foo''][''bar'']
d[''foo''][''baz'']
d[''fizz''][''buzz'']
d[''primary''][''secondary''][''tertiary''][''quaternary'']
pprint.pprint(d)

Qué salidas:

{''fizz'': {''buzz'': {}},
 ''foo'': {''bar'': {}, ''baz'': {}},
 ''primary'': {''secondary'': {''tertiary'': {''quaternary'': {}}}}}

Y como muestra la última línea, imprime muy bien y para una inspección manual. Pero si desea inspeccionar visualmente sus datos, implementar __missing__ para establecer una nueva instancia de su clase para la clave y devolverla es una solución mucho mejor.

Otras alternativas, por contraste:

dict.setdefault

Aunque el que pregunta cree que esto no está limpio, me parece preferible al Vividict .

d = {} # or dict()
for (state, county, occupation), number in data.items():
    d.setdefault(state, {}).setdefault(county, {})[occupation] = number

y ahora:

>>> pprint.pprint(d, width=40)
{''new jersey'': {''mercer county'': {''plumbers'': 3,
                                  ''programmers'': 81},
                ''middlesex county'': {''programmers'': 81,
                                     ''salesmen'': 62}},
 ''new york'': {''queens county'': {''plumbers'': 9,
                                ''salesmen'': 36}}}

Una falta de ortografía fallaría ruidosamente, y no saturaría nuestros datos con mala información:

>>> d[''new york''][''queens counyt'']
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
KeyError: ''queens counyt''

Además, creo que setdefault funciona muy bien cuando se usa en loops y no sabes qué obtendrás para las claves, pero el uso repetitivo se vuelve bastante engorroso, y no creo que nadie quiera mantener lo siguiente:

d = dict()

d.setdefault(''foo'', {}).setdefault(''bar'', {})
d.setdefault(''foo'', {}).setdefault(''baz'', {})
d.setdefault(''fizz'', {}).setdefault(''buzz'', {})
d.setdefault(''primary'', {}).setdefault(''secondary'', {}).setdefault(''tertiary'', {}).setdefault(''quaternary'', {})

Otra crítica es que setdefault requiere una nueva instancia, ya sea que se use o no. Sin embargo, Python (o al menos CPython) es bastante inteligente para manejar nuevas instancias sin usar y sin referencia, por ejemplo, reutiliza la ubicación en la memoria:

>>> id({}), id({}), id({})
(523575344, 523575344, 523575344)

Un incumplimiento predeterminado auto-vivificado

Esta es una implementación prolija, y el uso en una secuencia de comandos en la que no está inspeccionando los datos sería tan útil como implementar __missing__ :

from collections import defaultdict

def vivdict():
    return defaultdict(vivdict)

Pero si necesita inspeccionar sus datos, los resultados de un defecto de auto-vivificación predeterminado poblado con datos de la misma manera se ve así:

>>> d = vivdict(); d[''foo''][''bar'']; d[''foo''][''baz'']; d[''fizz''][''buzz'']; d[''primary''][''secondary''][''tertiary''][''quaternary'']; import pprint; 
>>> pprint.pprint(d)
defaultdict(<function vivdict at 0x17B01870>, {''foo'': defaultdict(<function vivdict 
at 0x17B01870>, {''baz'': defaultdict(<function vivdict at 0x17B01870>, {}), ''bar'': 
defaultdict(<function vivdict at 0x17B01870>, {})}), ''primary'': defaultdict(<function 
vivdict at 0x17B01870>, {''secondary'': defaultdict(<function vivdict at 0x17B01870>, 
{''tertiary'': defaultdict(<function vivdict at 0x17B01870>, {''quaternary'': defaultdict(
<function vivdict at 0x17B01870>, {})})})}), ''fizz'': defaultdict(<function vivdict at 
0x17B01870>, {''buzz'': defaultdict(<function vivdict at 0x17B01870>, {})})})

Este resultado es bastante poco elegante y los resultados son bastante ilegibles. La solución que se da típicamente es la conversión recursiva a un dict para la inspección manual. Esta solución no trivial se deja como un ejercicio para el lector.

Actuación

Finalmente, veamos el rendimiento. Estoy restando los costos de creación de instancias.

>>> import timeit
>>> min(timeit.repeat(lambda: {}.setdefault(''foo'', {}))) - min(timeit.repeat(lambda: {}))
0.13612580299377441
>>> min(timeit.repeat(lambda: vivdict()[''foo''])) - min(timeit.repeat(lambda: vivdict()))
0.2936999797821045
>>> min(timeit.repeat(lambda: Vividict()[''foo''])) - min(timeit.repeat(lambda: Vividict()))
0.5354437828063965
>>> min(timeit.repeat(lambda: AutoVivification()[''foo''])) - min(timeit.repeat(lambda: AutoVivification()))
2.138362169265747

En función del rendimiento, dict.setdefault funciona mejor. Lo recomiendo encarecidamente para el código de producción, en los casos en los que se preocupe por la velocidad de ejecución.

Si necesita esto para un uso interactivo (tal vez en una computadora portátil IPython), entonces el rendimiento en realidad no importa; en tal caso, me gustaría ir con Vividict para poder leer la salida. Comparado con el objeto AutoVivification (que usa __getitem__ lugar de __missing__ , que fue creado para este propósito) es muy superior.

Conclusión

Implementar __missing__ en un dict subclassed para establecer y devolver una nueva instancia es un poco más difícil que las alternativas, pero tiene los beneficios de

• fácil creación de instancias
• fácil población de datos
• fácil visualización de datos

y debido a que es menos complicado y más __getitem__ que la modificación de __getitem__ , debería preferirse ese método.

Sin embargo, tiene inconvenientes:

• Las malas búsquedas fallarán en silencio.
• La búsqueda incorrecta permanecerá en el diccionario.

Por lo tanto, personalmente prefiero setdefault a las otras soluciones, y tengo en cada situación donde he necesitado este tipo de comportamiento.

Answer 2

A menos que su conjunto de datos va a ser muy pequeño, es posible que desee considerar el uso de una base de datos relacional. Hará exactamente lo que quiera: facilitar el agregado de recuentos, la selección de subconjuntos de recuentos e incluso los recuentos agregados por estado, condado, ocupación o cualquier combinación de estos.

Answer 3

Como otros han sugerido, una base de datos relacional podría ser más útil para usted. Puede usar una base de datos sqlite3 en memoria como una estructura de datos para crear tablas y luego consultarlas.

import sqlite3

c = sqlite3.Connection('':memory:'')
c.execute(''CREATE TABLE jobs (state, county, title, count)'')

c.executemany(''insert into jobs values (?, ?, ?, ?)'', [
    (''New Jersey'', ''Mercer County'',    ''Programmers'', 81),
    (''New Jersey'', ''Mercer County'',    ''Plumbers'',     3),
    (''New Jersey'', ''Middlesex County'', ''Programmers'', 81),
    (''New Jersey'', ''Middlesex County'', ''Salesmen'',    62),
    (''New York'',   ''Queens County'',    ''Salesmen'',    36),
    (''New York'',   ''Queens County'',    ''Plumbers'',     9),
])

# some example queries
print list(c.execute(''SELECT * FROM jobs WHERE county = "Queens County"''))
print list(c.execute(''SELECT SUM(count) FROM jobs WHERE title = "Programmers"''))

Este es solo un simple ejemplo. Puede definir tablas separadas para estados, condados y títulos de trabajo.

Answer 4

Como tiene un diseño de esquema en estrella, es posible que desee estructurarlo más como una tabla relacional y menos como un diccionario.

import collections

class Jobs( object ):
    def __init__( self, state, county, title, count ):
        self.state= state
        self.count= county
        self.title= title
        self.count= count

facts = [
    Jobs( ''new jersey'', ''mercer county'', ''plumbers'', 3 ),
    ...

def groupBy( facts, name ):
    total= collections.defaultdict( int )
    for f in facts:
        key= getattr( f, name )
        total[key] += f.count

Ese tipo de cosas pueden contribuir en gran medida a crear un diseño tipo depósito de datos sin los gastos indirectos de SQL.

Answer 5

En cuanto a "odiosos try / catch blocks":

d = {}
d.setdefault(''key'',{}).setdefault(''inner key'',{})[''inner inner key''] = ''value''
print d

rendimientos

{''key'': {''inner key'': {''inner inner key'': ''value''}}}

Puede usar esto para convertir de su formato de diccionario plano a formato estructurado:

fd = {(''new jersey'', ''mercer county'', ''plumbers''): 3,
 (''new jersey'', ''mercer county'', ''programmers''): 81,
 (''new jersey'', ''middlesex county'', ''programmers''): 81,
 (''new jersey'', ''middlesex county'', ''salesmen''): 62,
 (''new york'', ''queens county'', ''plumbers''): 9,
 (''new york'', ''queens county'', ''salesmen''): 36}

for (k1,k2,k3), v in fd.iteritems():
    d.setdefault(k1, {}).setdefault(k2, {})[k3] = v

Answer 6

Encuentro setdefault bastante útil; Comprueba si una clave está presente y la agrega si no:

d = {}
d.setdefault(''new jersey'', {}).setdefault(''mercer county'', {})[''plumbers''] = 3

setdefault siempre devuelve la clave relevante, por lo que en realidad está actualizando los valores de '' d ''.

Cuando se trata de iterar, estoy seguro de que podrías escribir un generador con la suficiente facilidad si aún no existe uno en Python:

def iterateStates(d):
    # Let''s count up the total number of "plumbers" / "dentists" / etc.
    # across all counties and states
    job_totals = {}

    # I guess this is the annoying nested stuff you were talking about?
    for (state, counties) in d.iteritems():
        for (county, jobs) in counties.iteritems():
            for (job, num) in jobs.iteritems():
                # If job isn''t already in job_totals, default it to zero
                job_totals[job] = job_totals.get(job, 0) + num

    # Now return an iterator of (job, number) tuples
    return job_totals.iteritems()

# Display all jobs
for (job, num) in iterateStates(d):
    print "There are %d %s in total" % (job, num)

Answer 7

Esta es una función que devuelve un diccionario anidado de profundidad arbitraria:

from collections import defaultdict
def make_dict():
    return defaultdict(make_dict)

Úselo así:

d=defaultdict(make_dict)
d["food"]["meat"]="beef"
d["food"]["veggie"]="corn"
d["food"]["sweets"]="ice cream"
d["animal"]["pet"]["dog"]="collie"
d["animal"]["pet"]["cat"]="tabby"
d["animal"]["farm animal"]="chicken"

Iterare a través de todo con algo como esto:

def iter_all(d,depth=1):
    for k,v in d.iteritems():
        print "-"*depth,k
        if type(v) is defaultdict:
            iter_all(v,depth+1)
        else:
            print "-"*(depth+1),v

iter_all(d)

Esto se imprime:

- food
-- sweets
--- ice cream
-- meat
--- beef
-- veggie
--- corn
- animal
-- pet
--- dog
---- labrador
--- cat
---- tabby
-- farm animal
--- chicken

Es probable que desee hacerlo para que no se puedan agregar nuevos elementos al dict. Es fácil convertir de forma recursiva todos estos defaultdict a dict s normales.

def dictify(d):
    for k,v in d.iteritems():
        if isinstance(v,defaultdict):
            d[k] = dictify(v)
    return dict(d)

Answer 8

Me gusta la idea de incluir esto en una clase e implementar __getitem__ y __setitem__ modo que implementen un lenguaje de consulta simple:

>>> d[''new jersey/mercer county/plumbers''] = 3
>>> d[''new jersey/mercer county/programmers''] = 81
>>> d[''new jersey/mercer county/programmers'']
81
>>> d[''new jersey/mercer country'']
<view which implicitly adds ''new jersey/mercer county'' to queries/mutations>

Si quieres ser elegante, también puedes implementar algo como:

>>> d[''*/*/programmers'']
<view which would contain ''programmers'' entries>

pero sobre todo creo que tal cosa sería muy divertida de implementar: D

Answer 9

Para facilitar la iteración sobre su diccionario anidado, ¿por qué no simplemente escribir un generador simple?

def each_job(my_dict):
    for state, a in my_dict.items():
        for county, b in a.items():
            for job, value in b.items():
                yield {
                    ''state''  : state,
                    ''county'' : county,
                    ''job''    : job,
                    ''value''  : value
                }

Entonces, si tienes tu diccionario anidado compilado, iterar sobre él es simple:

for r in each_job(my_dict):
    print "There are %d %s in %s, %s" % (r[''value''], r[''job''], r[''county''], r[''state''])

Obviamente, su generador puede generar cualquier formato de datos que le sea útil.

¿Por qué estás usando try catch blocks para leer el árbol? Es bastante fácil (y probablemente más seguro) consultar si existe una clave en un dict antes de tratar de recuperarla. Una función que utiliza cláusulas de guardia podría verse así:

if not my_dict.has_key(''new jersey''):
    return False

nj_dict = my_dict[''new jersey'']
...

O, quizás un método algo detallado, es usar el método get:

value = my_dict.get(''new jersey'', {}).get(''middlesex county'', {}).get(''salesmen'', 0)

Pero para una forma un tanto más sucinta, es posible que desee considerar el uso de un collections.defaultdict , que es parte de la biblioteca estándar desde Python 2.5.

import collections

def state_struct(): return collections.defaultdict(county_struct)
def county_struct(): return collections.defaultdict(job_struct)
def job_struct(): return 0

my_dict = collections.defaultdict(state_struct)

print my_dict[''new jersey''][''middlesex county''][''salesmen'']

Estoy haciendo suposiciones sobre el significado de su estructura de datos aquí, pero debería ser fácil ajustar lo que realmente quiere hacer.

Answer 10

Puede crear un archivo YAML y leerlo usando PyYaml .

Paso 1: crea un archivo YAML, "employment.yml":

new jersey:
  mercer county:
    pumbers: 3
    programmers: 81
  middlesex county:
    salesmen: 62
    programmers: 81
new york:
  queens county:
    plumbers: 9
    salesmen: 36

Paso 2: léelo en Python

import yaml
file_handle = open("employment.yml")
my_shnazzy_dictionary = yaml.safe_load(file_handle)
file_handle.close()

y ahora my_shnazzy_dictionary tiene todos tus valores. Si necesita hacer esto sobre la marcha, puede crear el YAML como una cadena y alimentarlo en yaml.safe_load(...) .

Answer 11

Puede usar Addict: https://github.com/mewwts/addict

>>> from addict import Dict
>>> my_new_shiny_dict = Dict()
>>> my_new_shiny_dict.a.b.c.d.e = 2
>>> my_new_shiny_dict
{''a'': {''b'': {''c'': {''d'': {''e'': 2}}}}}

Answer 12

Puede usar la recursión en lambdas y defaultdict, sin necesidad de definir nombres:

a = defaultdict((lambda f: f(f))(lambda g: lambda:defaultdict(g(g))))

Aquí hay un ejemplo:

>>> a[''new jersey''][''mercer county''][''plumbers'']=3
>>> a[''new jersey''][''middlesex county''][''programmers'']=81
>>> a[''new jersey''][''mercer county''][''programmers'']=81
>>> a[''new jersey''][''middlesex county''][''salesmen'']=62
>>> a
defaultdict(<function __main__.<lambda>>,
        {''new jersey'': defaultdict(<function __main__.<lambda>>,
                     {''mercer county'': defaultdict(<function __main__.<lambda>>,
                                  {''plumbers'': 3, ''programmers'': 81}),
                      ''middlesex county'': defaultdict(<function __main__.<lambda>>,
                                  {''programmers'': 81, ''salesmen'': 62})})})

Answer 13

Si el número de niveles de anidamiento es pequeño, utilizo collections.defaultdict para esto:

from collections import defaultdict

def nested_dict_factory(): 
  return defaultdict(int)
def nested_dict_factory2(): 
  return defaultdict(nested_dict_factory)
db = defaultdict(nested_dict_factory2)

db[''new jersey''][''mercer county''][''plumbers''] = 3
db[''new jersey''][''mercer county''][''programmers''] = 81

Usar defaultdict como este evita un montón de setdefault() , get() , etc.

Answer 14

Solía ​​usar esta función. es seguro, rápido y fácil de mantener.

def deep_get(dictionary, keys, default=None):
    return reduce(lambda d, key: d.get(key, default) if isinstance(d, dict) else default, keys.split("."), dictionary)

Ejemplo:

>>> from functools import reduce
>>> def deep_get(dictionary, keys, default=None):
...     return reduce(lambda d, key: d.get(key, default) if isinstance(d, dict) else default, keys.split("."), dictionary)
...
>>> person = {''person'':{''name'':{''first'':''John''}}}
>>> print (deep_get(person, "person.name.first"))
John
>>> print (deep_get(person, "person.name.lastname"))
None
>>> print (deep_get(person, "person.name.lastname", default="No lastname"))
No lastname
>>>

Answer 15

Solo porque no he visto uno tan pequeño, aquí hay una frase que se anida tanto como quieras, sin sudar:

# yo dawg, i heard you liked dicts                                                                      
def yodict():
    return defaultdict(yodict)

Answer 16

Tengo algo similar en marcha. Tengo muchos casos en los que lo hago:

thedict = {}
for item in (''foo'', ''bar'', ''baz''):
  mydict = thedict.get(item, {})
  mydict = get_value_for(item)
  thedict[item] = mydict

Pero yendo a muchos niveles profundo. Es el ".get (item, {})" esa es la clave, ya que hará otro diccionario si no hay uno ya. Mientras tanto, he estado pensando en maneras de lidiar con esto mejor. En este momento, hay una gran cantidad de

value = mydict.get(''foo'', {}).get(''bar'', {}).get(''baz'', 0)

Entonces, en cambio, hice:

def dictgetter(thedict, default, *args):
  totalargs = len(args)
  for i,arg in enumerate(args):
    if i+1 == totalargs:
      thedict = thedict.get(arg, default)
    else:
      thedict = thedict.get(arg, {})
  return thedict

Lo cual tiene el mismo efecto si lo haces:

value = dictgetter(mydict, 0, ''foo'', ''bar'', ''baz'')

¿Mejor? Creo que si.

Answer 17

collections.defaultdict se puede subclasificar para crear un dictado anidado. Luego agregue cualquier método de iteración útil a esa clase.

>>> from collections import defaultdict
>>> class nesteddict(defaultdict):
    def __init__(self):
        defaultdict.__init__(self, nesteddict)
    def walk(self):
        for key, value in self.iteritems():
            if isinstance(value, nesteddict):
                for tup in value.walk():
                    yield (key,) + tup
            else:
                yield key, value


>>> nd = nesteddict()
>>> nd[''new jersey''][''mercer county''][''plumbers''] = 3
>>> nd[''new jersey''][''mercer county''][''programmers''] = 81
>>> nd[''new jersey''][''middlesex county''][''programmers''] = 81
>>> nd[''new jersey''][''middlesex county''][''salesmen''] = 62
>>> nd[''new york''][''queens county''][''plumbers''] = 9
>>> nd[''new york''][''queens county''][''salesmen''] = 36
>>> for tup in nd.walk():
    print tup


(''new jersey'', ''mercer county'', ''programmers'', 81)
(''new jersey'', ''mercer county'', ''plumbers'', 3)
(''new jersey'', ''middlesex county'', ''programmers'', 81)
(''new jersey'', ''middlesex county'', ''salesmen'', 62)
(''new york'', ''queens county'', ''salesmen'', 36)
(''new york'', ''queens county'', ''plumbers'', 9)

Answer 18

defaultdict() es tu amigo!

Para un diccionario bidimensional puedes hacer:

d = defaultdict(defaultdict)
d[1][2] = 3

Para más dimensiones, puede:

d = defaultdict(lambda :defaultdict(defaultdict))
d[1][2][3] = 4

Answer 19

class AutoVivification(dict):
    """Implementation of perl''s autovivification feature."""
    def __getitem__(self, item):
        try:
            return dict.__getitem__(self, item)
        except KeyError:
            value = self[item] = type(self)()
            return value

Pruebas:

a = AutoVivification()

a[1][2][3] = 4
a[1][3][3] = 5
a[1][2][''test''] = 6

print a

Salida:

{1: {2: {''test'': 6, 3: 4}, 3: {3: 5}}}

Answer 20

class JobDb(object):
    def __init__(self):
        self.data = []
        self.all = set()
        self.free = []
        self.index1 = {}
        self.index2 = {}
        self.index3 = {}

    def _indices(self,(key1,key2,key3)):
        indices = self.all.copy()
        wild = False
        for index,key in ((self.index1,key1),(self.index2,key2),
                                             (self.index3,key3)):
            if key is not None:
                indices &= index.setdefault(key,set())
            else:
                wild = True
        return indices, wild

    def __getitem__(self,key):
        indices, wild = self._indices(key)
        if wild:
            return dict(self.data[i] for i in indices)
        else:
            values = [self.data[i][-1] for i in indices]
            if values:
                return values[0]

    def __setitem__(self,key,value):
        indices, wild = self._indices(key)
        if indices:
            for i in indices:
                self.data[i] = key,value
        elif wild:
            raise KeyError(k)
        else:
            if self.free:
                index = self.free.pop(0)
                self.data[index] = key,value
            else:
                index = len(self.data)
                self.data.append((key,value))
                self.all.add(index)
            self.index1.setdefault(key[0],set()).add(index)
            self.index2.setdefault(key[1],set()).add(index)
            self.index3.setdefault(key[2],set()).add(index)

    def __delitem__(self,key):
        indices,wild = self._indices(key)
        if not indices:
            raise KeyError
        self.index1[key[0]] -= indices
        self.index2[key[1]] -= indices
        self.index3[key[2]] -= indices
        self.all -= indices
        for i in indices:
            self.data[i] = None
        self.free.extend(indices)

    def __len__(self):
        return len(self.all)

    def __iter__(self):
        for key,value in self.data:
            yield key

Ejemplo:

>>> db = JobDb()
>>> db[''new jersey'', ''mercer county'', ''plumbers''] = 3
>>> db[''new jersey'', ''mercer county'', ''programmers''] = 81
>>> db[''new jersey'', ''middlesex county'', ''programmers''] = 81
>>> db[''new jersey'', ''middlesex county'', ''salesmen''] = 62
>>> db[''new york'', ''queens county'', ''plumbers''] = 9
>>> db[''new york'', ''queens county'', ''salesmen''] = 36

>>> db[''new york'', None, None]
{(''new york'', ''queens county'', ''plumbers''): 9,
 (''new york'', ''queens county'', ''salesmen''): 36}

>>> db[None, None, ''plumbers'']
{(''new jersey'', ''mercer county'', ''plumbers''): 3,
 (''new york'', ''queens county'', ''plumbers''): 9}

>>> db[''new jersey'', ''mercer county'', None]
{(''new jersey'', ''mercer county'', ''plumbers''): 3,
 (''new jersey'', ''mercer county'', ''programmers''): 81}

>>> db[''new jersey'', ''middlesex county'', ''programmers'']
81

>>>

Editar: ahora devuelve diccionarios cuando consulta con comodines ( None ) y valores únicos de lo contrario.