Python: compruebe si un diccionario es un subconjunto de otro diccionario más grande

100

Estoy tratando de escribir un método de filtro personalizado que toma un número arbitrario de kwargs y devuelve una lista que contiene los elementos de una lista similar a una base de datos que contiene esos kwargs .

Por ejemplo, suponga que d1 = {'a':'2', 'b':'3'}y d2= lo mismo. d1 == d2resulta en Verdadero. Pero supongamos d2= lo mismo más un montón de otras cosas. Mi método necesita poder decir si d1 en d2 , pero Python no puede hacer eso con diccionarios.

Contexto:

Tengo una clase de palabras, y cada objeto tiene propiedades como word, definition, part_of_speech, y así sucesivamente. Quiero poder llamar a un método de filtro en la lista principal de estas palabras, como Word.objects.filter(word='jump', part_of_speech='verb-intransitive'). No puedo entender cómo administrar estas claves y valores al mismo tiempo. Pero esto podría tener una mayor funcionalidad fuera de este contexto para otras personas.

Jamey
fuente

Respuestas:

108

Convierta a pares de elementos y compruebe la contención.

all(item in superset.items() for item in subset.items())

La optimización se deja como ejercicio para el lector.

Ignacio Vázquez-Abrams
fuente
18
Si los valores son dict hashable, utilizando viewitems () es la forma más optimizied se me ocurre: d1.viewitems() <= d2.viewitems(). Las ejecuciones de Timeit mostraron una mejora de rendimiento 3 veces superior. Si no se puede mezclar, incluso usarlo en iteritems()lugar de items()conduce a una mejora de aproximadamente 1.2x. Esto se hizo usando Python 2.7.
Chad
34
No creo que la optimización deba dejarse en manos del lector; me preocupa que la gente realmente use esto sin darse cuenta de que va a construir una copia de superset.items () e iterar a través de él para cada elemento del subconjunto.
robert king
4
Con Python 3 items()devolverá vistas ligeras en lugar de copias. No es necesaria ninguna optimización adicional.
Kentzo
3
¿Qué pasa con los directorios anidados?
Andreas Profous
5
esto es muy gracioso. Dejaré el refinamiento del tema del humor al lector.
profundización
95

En Python 3, puede usar dict.items()para obtener una vista similar a un conjunto de los elementos de dict. Luego puede usar el <=operador para probar si una vista es un "subconjunto" de la otra:

d1.items() <= d2.items()

En Python 2.7, use dict.viewitems()para hacer lo mismo:

d1.viewitems() <= d2.viewitems()

En Python 2.6 y versiones anteriores, necesitará una solución diferente, como usar all():

all(key in d2 and d2[key] == d1[key] for key in d1)
augurar
fuente
1
para python3 esto se convierte end1.items() <= d2.items()
radu.ciorba
Advertencia: si su programa podría usarse potencialmente en Python 2.6 (o incluso en una versión inferior), en d1.items() <= d2.items()realidad están comparando 2 listas de tuplas, sin un orden particular, por lo que el resultado final probablemente no será confiable. Por esta razón, cambio a la respuesta de @blubberdiblub.
RayLuo
1
d1.items() <= d2.items()es un comportamiento indefinido. No está documentado en los documentos oficiales y, lo que es más importante, no está probado: github.com/python/cpython/blob/… Así que esto depende de la implementación.
Rodrigo Martins de Oliveira
2
@RodrigoMartins Está documentado aquí : "Para vistas tipo set, todas las operaciones definidas para la clase base abstracta collections.abc.Setestán disponibles"
augurar
1
@RodrigoMartins Si está preocupado por futuros mantenedores, envuelva la operación en una función con un nombre claro o agregue un comentario de código. Bajar los estándares de su código al nivel de desarrolladores incompetentes es una idea terrible.
augurar
36

Nota para las personas que necesitan esto para las pruebas unitarias: también hay un assertDictContainsSubset()método en la TestCaseclase de Python .

http://docs.python.org/2/library/unittest.html?highlight=assertdictcontainssubset#unittest.TestCase.assertDictContainsSubset

Sin embargo, está obsoleto en 3.2, no estoy seguro de por qué, tal vez haya un reemplazo para él.

gitaarik
fuente
29
Era curioso, encontré esto en las novedades de 3.2 : El método assertDictContainsSubset () estaba en desuso porque no se implementó correctamente con los argumentos en el orden incorrecto. Esto creó ilusiones ópticas difíciles de depurar en las que pruebas como TestCase (). AssertDictContainsSubset ({'a': 1, 'b': 2}, {'a': 1}) fallarían. (Contribuido por Raymond Hettinger.)
Pedru
2
Espera, se espera el lado izquierdo y el lado derecho es real ... ¿No debería fallar? Lo único malo con la función es que ¿cuál va en qué lugar es confuso?
JamesHutchison
21

para claves y valores, verifique el uso: set(d1.items()).issubset(set(d2.items()))

si necesita verificar solo las claves: set(d1).issubset(set(d2))

kashchey
fuente
11
La primera expresión no funcionará si algún valor en cualquiera de los diccionarios no es hash.
Pedro Romano
6
El segundo ejemplo se puede acortar ligeramente eliminando el conjunto (d2), ya que "issubset acepta cualquier iterable". docs.python.org/2/library/stdtypes.html#set
trojjer
Esto está mal: d1={'a':1,'b':2}; d2={'a':2,'b':1}-> el segundo fragmento volverá True...
Francesco Pasa
1
@FrancescoPasa El segundo fragmento dice explícitamente: "si necesita verificar solo las claves". {'a', 'b'}es de hecho un subconjunto de {'a', 'b'};)
DylanYoung
19

Para completar, también puede hacer esto:

def is_subdict(small, big):
    return dict(big, **small) == big

Sin embargo, no hago ningún reclamo con respecto a la velocidad (o falta de ella) o legibilidad (o falta de ella).

blubberdiblub
fuente
Una nota al margen: las otras respuestas mencionadas small.viewitems() <= big.viewitems()fueron prometedoras, pero con una advertencia: si su programa también se puede usar en Python 2.6 (o incluso en una versión inferior), en d1.items() <= d2.items()realidad se están comparando 2 listas de tuplas, sin un orden en particular, por lo que el resultado final probablemente será no fiable. Por esa razón, cambio a la respuesta de @blubberdiblub. Voto a favor.
RayLuo
Esto es genial, pero no parece funcionar con diccionarios anidados.
Frederik Baetens
@FrederikBaetens no está destinado a hacerlo. Además, creo que no hay una forma generalmente aceptada de cómo hacerlo, porque hay varias formas de hacerlo y existen múltiples estructuras / restricciones posibles que podría imponer a dichos diccionarios. Aquí hay algunas preguntas que me vienen a la mente: ¿Cómo se determina si se debe acceder a un diccionario más profundo? ¿Qué pasa con los objetos de un tipo que tiene dictcomo clase base? ¿Qué pasa si no lo ha hecho y todavía se comporta como un dict? ¿Qué pasa si smally bigcontienen valores de diferente tipo en una clave coincidente que todavía se comporta como dict?
blubberdiblub
Esos son puntos válidos, pero una función básica que funcionó con dictados anidados simples debería ser agradable. Publiqué un ejemplo aquí , pero la solución de @NutCracker es mejor
Frederik Baetens
Claro, si hubiera sido una pregunta sobre diccionarios anidados (y si se hubieran resumido los requisitos exactos para los diccionarios), podría haberlo hecho. El punto es que una solución para diccionarios anidados no da la respuesta correcta cuando quiere saber si un dictado es un subdictorio de otro de una manera plana (es decir, cuando quiere que la respuesta sea estrictamente Falsecuando los valores de los dictados pasados son diferentes para las claves coincidentes). O en otras palabras: la solución para los dictados anidados no es necesariamente un reemplazo directo según el caso de uso.
blubberdiblub
10
>>> d1 = {'a':'2', 'b':'3'}
>>> d2 = {'a':'2', 'b':'3','c':'4'}
>>> all((k in d2 and d2[k]==v) for k,v in d1.iteritems())
True

contexto:

>>> d1 = {'a':'2', 'b':'3'}
>>> d2 = {'a':'2', 'b':'3','c':'4'}
>>> list(d1.iteritems())
[('a', '2'), ('b', '3')]
>>> [(k,v) for k,v in d1.iteritems()]
[('a', '2'), ('b', '3')]
>>> k,v = ('a','2')
>>> k
'a'
>>> v
'2'
>>> k in d2
True
>>> d2[k]
'2'
>>> k in d2 and d2[k]==v
True
>>> [(k in d2 and d2[k]==v) for k,v in d1.iteritems()]
[True, True]
>>> ((k in d2 and d2[k]==v) for k,v in d1.iteritems())
<generator object <genexpr> at 0x02A9D2B0>
>>> ((k in d2 and d2[k]==v) for k,v in d1.iteritems()).next()
True
>>> all((k in d2 and d2[k]==v) for k,v in d1.iteritems())
True
>>>
Robert King
fuente
4

Mi función para el mismo propósito, haciendo esto de forma recursiva:

def dictMatch(patn, real):
    """does real dict match pattern?"""
    try:
        for pkey, pvalue in patn.iteritems():
            if type(pvalue) is dict:
                result = dictMatch(pvalue, real[pkey])
                assert result
            else:
                assert real[pkey] == pvalue
                result = True
    except (AssertionError, KeyError):
        result = False
    return result

En su ejemplo, dictMatch(d1, d2)debería devolver True incluso si d2 tiene otras cosas, además de que también se aplica a niveles inferiores:

d1 = {'a':'2', 'b':{3: 'iii'}}
d2 = {'a':'2', 'b':{3: 'iii', 4: 'iv'},'c':'4'}

dictMatch(d1, d2)   # True

Notas: Podría haber una solución aún mejor que evite la if type(pvalue) is dictcláusula y se aplique a una gama aún más amplia de casos (como listas de hashes, etc.). Además, la recursividad no está limitada aquí, así que úsala bajo tu propio riesgo. ;)

Alois Mahdal
fuente
4

Aquí hay una solución que también se repite correctamente en listas y conjuntos contenidos en el diccionario. También puede usar esto para listas que contengan dictados, etc.

def is_subset(subset, superset):
    if isinstance(subset, dict):
        return all(key in superset and is_subset(val, superset[key]) for key, val in subset.items())

    if isinstance(subset, list) or isinstance(subset, set):
        return all(any(is_subset(subitem, superitem) for superitem in superset) for subitem in subset)

    # assume that subset is a plain value if none of the above match
    return subset == superset
Frederik Baetens
fuente
2

Este problema aparentemente sencillo me cuesta un par de horas de investigación para encontrar una solución 100% confiable, así que documenté lo que encontré en esta respuesta.

  1. Hablando con "Pythonic-ally", small_dict <= big_dictsería la forma más intuitiva, pero es una lástima que no funcione . {'a': 1} < {'a': 1, 'b': 2}aparentemente funciona en Python 2, pero no es confiable porque la documentación oficial lo menciona explícitamente. Vaya a la búsqueda "Los resultados distintos de la igualdad se resuelven de forma coherente, pero no se definen de otra manera". en esta sección . Sin mencionar que comparar 2 dictados en Python 3 da como resultado una excepción TypeError.

  2. La segunda cosa más intuitiva es solo small.viewitems() <= big.viewitems()para Python 2.7 y small.items() <= big.items()para Python 3. Pero hay una advertencia: es potencialmente defectuoso . Si su programa podría potencialmente usarse en Python <= 2.6, en d1.items() <= d2.items()realidad está comparando 2 listas de tuplas, sin un orden particular, por lo que el resultado final no será confiable y se convertirá en un error desagradable en su programa. No estoy interesado en escribir otra implementación para Python <= 2.6, pero todavía no me siento cómodo con que mi código tenga un error conocido (incluso si está en una plataforma no compatible). De modo que abandono este enfoque.

  3. Me establezco con la respuesta de @blubberdiblub (el crédito es para él):

    def is_subdict(small, big): return dict(big, **small) == big

    Vale la pena señalar que esta respuesta se basa en el ==comportamiento entre dictados, que está claramente definido en el documento oficial, por lo que debería funcionar en todas las versiones de Python . Ir a buscar:

    • "Los diccionarios se comparan igual si y solo si tienen los mismos pares (clave, valor)". es la última oración de esta página
    • "Las asignaciones (instancias de dict) se comparan igual si y solo si tienen pares (clave, valor) iguales. La comparación de igualdad de las claves y los elementos refuerza la reflexividad". en esta pagina
RayLuo
fuente
2

Aquí hay una solución recursiva general para el problema dado:

import traceback
import unittest

def is_subset(superset, subset):
    for key, value in subset.items():
        if key not in superset:
            return False

        if isinstance(value, dict):
            if not is_subset(superset[key], value):
                return False

        elif isinstance(value, str):
            if value not in superset[key]:
                return False

        elif isinstance(value, list):
            if not set(value) <= set(superset[key]):
                return False
        elif isinstance(value, set):
            if not value <= superset[key]:
                return False

        else:
            if not value == superset[key]:
                return False

    return True


class Foo(unittest.TestCase):

    def setUp(self):
        self.dct = {
            'a': 'hello world',
            'b': 12345,
            'c': 1.2345,
            'd': [1, 2, 3, 4, 5],
            'e': {1, 2, 3, 4, 5},
            'f': {
                'a': 'hello world',
                'b': 12345,
                'c': 1.2345,
                'd': [1, 2, 3, 4, 5],
                'e': {1, 2, 3, 4, 5},
                'g': False,
                'h': None
            },
            'g': False,
            'h': None,
            'question': 'mcve',
            'metadata': {}
        }

    def tearDown(self):
        pass

    def check_true(self, superset, subset):
        return self.assertEqual(is_subset(superset, subset), True)

    def check_false(self, superset, subset):
        return self.assertEqual(is_subset(superset, subset), False)

    def test_simple_cases(self):
        self.check_true(self.dct, {'a': 'hello world'})
        self.check_true(self.dct, {'b': 12345})
        self.check_true(self.dct, {'c': 1.2345})
        self.check_true(self.dct, {'d': [1, 2, 3, 4, 5]})
        self.check_true(self.dct, {'e': {1, 2, 3, 4, 5}})
        self.check_true(self.dct, {'f': {
            'a': 'hello world',
            'b': 12345,
            'c': 1.2345,
            'd': [1, 2, 3, 4, 5],
            'e': {1, 2, 3, 4, 5},
        }})
        self.check_true(self.dct, {'g': False})
        self.check_true(self.dct, {'h': None})

    def test_tricky_cases(self):
        self.check_true(self.dct, {'a': 'hello'})
        self.check_true(self.dct, {'d': [1, 2, 3]})
        self.check_true(self.dct, {'e': {3, 4}})
        self.check_true(self.dct, {'f': {
            'a': 'hello world',
            'h': None
        }})
        self.check_false(
            self.dct, {'question': 'mcve', 'metadata': {'author': 'BPL'}})
        self.check_true(
            self.dct, {'question': 'mcve', 'metadata': {}})
        self.check_false(
            self.dct, {'question1': 'mcve', 'metadata': {}})

if __name__ == "__main__":
    unittest.main()

NOTA: El código original fallaría en ciertos casos, los créditos por la reparación van a @ olivier-melançon

BPL
fuente
el código falla con un superconjunto que tiene un dict anidado dentro de una lista, en la líneaif not set(value) <= set(superset[key])
Eelco Hoogendoorn
2

Si no les importa usar pydash existe is_matchallí, lo que hace exactamente eso:

import pydash

a = {1:2, 3:4, 5:{6:7}}
b = {3:4.0, 5:{6:8}}
c = {3:4.0, 5:{6:7}}

pydash.predicates.is_match(a, b) # False
pydash.predicates.is_match(a, c) # True
Zaro
fuente
1

Sé que esta pregunta es antigua, pero aquí está mi solución para verificar si un diccionario anidado es parte de otro diccionario anidado. La solución es recursiva.

def compare_dicts(a, b):
    for key, value in a.items():
        if key in b:
            if isinstance(a[key], dict):
                if not compare_dicts(a[key], b[key]):
                    return False
            elif value != b[key]:
                return False
        else:
            return False
    return True
Cascanueces
fuente
0

Esta función funciona para valores no hash. También creo que es claro y fácil de leer.

def isSubDict(subDict,dictionary):
    for key in subDict.keys():
        if (not key in dictionary) or (not subDict[key] == dictionary[key]):
            return False
    return True

In [126]: isSubDict({1:2},{3:4})
Out[126]: False

In [127]: isSubDict({1:2},{1:2,3:4})
Out[127]: True

In [128]: isSubDict({1:{2:3}},{1:{2:3},3:4})
Out[128]: True

In [129]: isSubDict({1:{2:3}},{1:{2:4},3:4})
Out[129]: False
Timthelion
fuente
0

Una implementación recursiva corta que funciona para diccionarios anidados:

def compare_dicts(a,b):
    if not a: return True
    if isinstance(a, dict):
        key, val = a.popitem()
        return isinstance(b, dict) and key in b and compare_dicts(val, b.pop(key)) and compare_dicts(a, b)
    return a == b

Esto consumirá los dictados ayb. Si alguien conoce una buena manera de evitar eso sin recurrir a soluciones parcialmente iterativas como en otras respuestas, dímelo. Necesitaría una forma de dividir un dictado en cabeza y cola según una clave.

Este código es más útil como ejercicio de programación, y probablemente sea mucho más lento que otras soluciones aquí que mezclan recursividad e iteración. La solución de @ Nutcracker es bastante buena para los diccionarios anidados.

Frederik Baetens
fuente
1
Falta algo en el código. Simplemente desciende por el primer valor comenzando en a(y cualquier primer valor posterior) popitemencuentra. También debe examinar otros elementos del mismo nivel. Tengo pares de dictados anidados en los que devuelve la respuesta incorrecta. (es difícil presentar un ejemplo a prueba de futuro aquí, ya que se basa en el orden de popitem)
blubberdiblub
Gracias, debería arreglarse ahora :)
Frederik Baetens
0

Utilice este objeto contenedor que proporciona una comparación parcial y diferencias agradables:


class DictMatch(dict):
    """ Partial match of a dictionary to another one """
    def __eq__(self, other: dict):
        assert isinstance(other, dict)
        return all(other[name] == value for name, value in self.items())

actual_name = {'praenomen': 'Gaius', 'nomen': 'Julius', 'cognomen': 'Caesar'}
expected_name = DictMatch({'praenomen': 'Gaius'})  # partial match
assert expected_name == actual_name  # True
kolypto
fuente