Python: Sprawdź, czy jeden słownik jest podzbiorem innego większego słownika

103

Próbuję napisać niestandardową metodę filtru, która pobiera dowolną liczbę kwarg i zwraca listę zawierającą elementy listy podobnej do bazy danych, która zawiera te kwargi .

Na przykład załóżmy, że d1 = {'a':'2', 'b':'3'}i d2= to samo. d1 == d2wyniki w True. Ale przypuśćmy, że d2= to samo plus kilka innych rzeczy. Moja metoda musi być w stanie stwierdzić, czy d1 w d2 , ale Python nie może tego zrobić ze słownikami.

Kontekst:

Mam klasy słowo, a każdy obiekt ma właściwości takie jak word, definition, part_of_speechi tak dalej. Chcę mieć możliwość wywołania metody filtrującej na głównej liście tych słów, na przykład Word.objects.filter(word='jump', part_of_speech='verb-intransitive'). Nie mogę dowiedzieć się, jak jednocześnie zarządzać tymi kluczami i wartościami. Ale może to mieć większą funkcjonalność poza tym kontekstem dla innych ludzi.

Jamey
źródło

Odpowiedzi:

109

Zamień na pary przedmiotów i sprawdź, czy nie zawierają.

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

Optymalizacja jest pozostawiona czytelnikowi jako ćwiczenie.

Ignacio Vazquez-Abrams
źródło
18
Jeśli wartości dict są hashable korzystając viewitems () jest najbardziej optimizied sposób mogę myśleć: d1.viewitems() <= d2.viewitems(). Testy Timeit wykazały ponad 3-krotną poprawę wydajności. Jeśli nie można haszować, nawet użycie iteritems()zamiast items()prowadzi do około 1,2-krotnej poprawy. Dokonano tego za pomocą Pythona 2.7.
Czad
34
Nie sądzę, aby optymalizacja była pozostawiona czytelnikowi - obawiam się, że ludzie faktycznie będą go używać, nie zdając sobie sprawy, że utworzy kopię superset.items () i będzie ją iterować dla każdego elementu w podzbiorze.
robert king
4
Z Pythonem 3 items()zwróci lekkie widoki zamiast kopii. Nie jest wymagana dalsza optymalizacja.
Kentzo
3
A co z zagnieżdżonymi katalogami?
Andreas Profous
5
to przezabawne. Temat dopracowania humoru pozostawiam czytelnikowi.
deepelement
97

W Pythonie 3 możesz użyć, dict.items()aby uzyskać podobny do zestawu widok elementów dict. Następnie możesz użyć <=operatora, aby sprawdzić, czy jeden widok jest „podzbiorem” drugiego:

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

W Pythonie 2.7 użyj, dict.viewitems()aby zrobić to samo:

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

W Pythonie 2.6 i starszych będziesz potrzebować innego rozwiązania, takiego jak użycie all():

all(key in d2 and d2[key] == d1[key] for key in d1)
augurar
źródło
1
dla pythona3 staje się tod1.items() <= d2.items()
radu.ciorba
Uwaga: jeśli twój program mógłby potencjalnie być użyty w Pythonie 2.6 (lub nawet poniżej), d1.items() <= d2.items()faktycznie porównują 2 listy krotek, bez określonej kolejności, więc ostateczny wynik prawdopodobnie nie będzie wiarygodny. Z tego powodu przełączam się na odpowiedź @blubberdiblub.
RayLuo,
1
d1.items() <= d2.items()jest niezdefiniowanym zachowaniem. Nie jest to udokumentowane w oficjalnej dokumentacji i, co najważniejsze, nie jest to testowane: github.com/python/cpython/blob/… Więc to zależy od implementacji.
Rodrigo Martins de Oliveira
2
@RodrigoMartins Jest to udokumentowane tutaj : „W przypadku widoków typu zestawu collections.abc.Setdostępne są wszystkie operacje zdefiniowane dla abstrakcyjnej klasy bazowej ”
augurar,
1
@RodrigoMartins Jeśli martwisz się o przyszłych opiekunów, zawiń operację w wyraźnie nazwaną funkcję lub dodaj komentarz do kodu. Obniżenie standardów kodu do poziomu niekompetentnych programistów to fatalny pomysł.
augurar
36

Uwaga dla osób, które potrzebują tego do testów jednostkowych: assertDictContainsSubset()w TestCaseklasie Pythona jest również metoda .

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

Jest jednak przestarzały w wersji 3.2, nie wiem dlaczego, może jest dla niego zamiennik.

gitaarik
źródło
29
był ciekawy, znalazłem to w nowościach w 3.2 : Metoda assertDictContainsSubset () została uznana za przestarzałą, ponieważ została błędnie zaimplementowana z argumentami w złej kolejności. Stworzyło to trudne do debugowania iluzje optyczne, w których testy takie jak TestCase (). AssertDictContainsSubset ({'a': 1, 'b': 2}, {'a': 1}) kończyły się niepowodzeniem. (
Nadesłał
2
Czekaj, lewa strona jest oczekiwana, a prawa strona jest rzeczywista ... Czy to nie powinno zawieść? Jedyną wadą tej funkcji jest to, że to, co się dzieje w którym miejscu, jest mylące?
JamesHutchison
21

do sprawdzania kluczy i wartości użyj: set(d1.items()).issubset(set(d2.items()))

jeśli chcesz sprawdzić tylko klucze: set(d1).issubset(set(d2))

kashchey
źródło
11
Pierwsze wyrażenie nie zadziała, jeśli żadna wartość w żadnym ze słowników nie podlega haszowaniu.
Pedro Romano
6
Drugi przykład można nieco skrócić, usuwając zbiór (d2), ponieważ „issubset akceptuje każdą iterację”. docs.python.org/2/library/stdtypes.html#set
trojjer
To źle: d1={'a':1,'b':2}; d2={'a':2,'b':1}-> drugi fragment powróci True...
Francesco Pasa
1
@FrancescoPasa Drugi fragment mówi wprost: „jeśli chcesz sprawdzić tylko klucze”. {'a', 'b'}jest w rzeczywistości podzbiorem {'a', 'b'};)
DylanYoung
19

Aby uzyskać kompletność, możesz również zrobić to:

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

Jednak nie składam żadnych roszczeń dotyczących szybkości (lub jej braku) lub czytelności (lub jej braku).

blubberdiblub
źródło
Na marginesie: inne wspomniane odpowiedzi small.viewitems() <= big.viewitems()były obiecujące, ale z jednym zastrzeżeniem: jeśli twój program może być również używany w Pythonie 2.6 (lub nawet poniżej), w d1.items() <= d2.items()rzeczywistości porównują 2 listy krotek, bez określonej kolejności, więc ostateczny wynik prawdopodobnie nie wiarygodny. Z tego powodu przełączam się na odpowiedź @blubberdiblub. Głosowano za.
RayLuo,
To jest fajne, ale wydaje się, że nie działa z zagnieżdżonymi słownikami.
Frederik Baetens
@FrederikBaetens to nie jest przeznaczone. Uważam również, że nie ma ogólnie przyjętego sposobu, jak to zrobić, ponieważ można to zrobić na wiele sposobów i istnieje wiele możliwych struktur / ograniczeń, które można nałożyć na takie słowniki. Oto kilka pytań, które nasuwają się na myśl: W jaki sposób ustalasz, czy należy zejść do głębszego słownika? A co z obiektami typu, który ma dictklasę bazową? A jeśli tak nie jest i nadal zachowuje się jak dict? Co jeśli smalli bigzawierają wartości innego typu w pasującym kluczu, który nadal zachowuje się jak dict?
blubberdiblub
To są ważne punkty, ale podstawowa funkcja, która działała ze zwykłymi zagnieżdżonymi poleceniami, powinna być ładna. Umieściłem tutaj przykład , ale rozwiązanie @ NutCracker jest lepsze
Frederik Baetens
Jasne, gdyby chodziło o słowniki zagnieżdżone (i nakreślono dokładne wymagania dotyczące słowników), mógłbym się nad tym zastanowić. Chodzi o to, że rozwiązanie dla zagnieżdżonych słowników nie daje poprawnej odpowiedzi, gdy chcesz wiedzieć, czy dykt jest subdyktem innego w sposób płaski (tj. Gdy chcesz, aby odpowiedź była ściśle zgodna z Falsewartościami przekazanych nakazów są różne dla pasujących kluczy). Innymi słowy: rozwiązanie dla zagnieżdżonych dykt niekoniecznie jest zastępstwem typu drop-in w zależności od przypadku użycia.
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

kontekst:

>>> 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
źródło
4

Moja funkcja w tym samym celu, robiąc to rekurencyjnie:

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

W twoim przykładzie dictMatch(d1, d2)powinno zwrócić True, nawet jeśli d2 zawiera inne rzeczy, a ponadto ma to zastosowanie również do niższych poziomów:

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

dictMatch(d1, d2)   # True

Uwagi: Mogłoby być jeszcze lepsze rozwiązanie, które pozwala uniknąć if type(pvalue) is dictklauzuli i ma zastosowanie do jeszcze szerszego zakresu przypadków (takich jak listy skrótów itp.). Rekurencja nie jest tutaj ograniczona, więc korzystaj z niej na własne ryzyko. ;)

Alois Mahdal
źródło
4

Oto rozwiązanie, które również poprawnie powraca do list i zestawów zawartych w słowniku. Możesz również użyć tego do list zawierających dykty itp ...

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
źródło
2

Ten pozornie prosty problem kosztuje mnie kilka godzin w poszukiwaniu w 100% niezawodnego rozwiązania, więc udokumentowałem to, co znalazłem w tej odpowiedzi.

  1. Mówienie „sojusznik Pythona” small_dict <= big_dictbyłoby najbardziej intuicyjnym sposobem, ale szkoda, że nie zadziała . {'a': 1} < {'a': 1, 'b': 2}pozornie działa w Pythonie 2, ale nie jest wiarygodny, ponieważ oficjalna dokumentacja wyraźnie to określa. Przejdź do wyszukiwania „Wyniki inne niż równość są rozwiązywane konsekwentnie, ale nie są zdefiniowane w inny sposób”. w tej sekcji . Nie wspominając o tym, że porównanie 2 dykt w Pythonie 3 powoduje wyjątek TypeError.

  2. Druga najbardziej intuicyjna rzecz dotyczy small.viewitems() <= big.viewitems()tylko Pythona 2.7 i small.items() <= big.items()Pythona 3. Jest jednak jedno zastrzeżenie: potencjalnie zawiera błędy . Jeśli twój program mógłby potencjalnie być użyty w Pythonie <= 2.6, d1.items() <= d2.items()to faktycznie porównuje 2 listy krotek, bez określonej kolejności, więc ostateczny wynik będzie niewiarygodny i stanie się paskudnym błędem w twoim programie. Nie mam ochoty pisać kolejnej implementacji dla Pythona <= 2.6, ale nadal nie czuję się komfortowo, że mój kod zawiera znany błąd (nawet jeśli jest na nieobsługiwanej platformie). Dlatego porzucam to podejście.

  3. Zgadzam się z odpowiedzią @blubberdiblub (zasługa go):

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

    Warto zaznaczyć, że ta odpowiedź opiera się na ==zachowaniu między dyktami, które jest jasno zdefiniowane w oficjalnym dokumencie, stąd powinno działać w każdej wersji Pythona . Szukaj:

    • „Słowniki porównują równe sobie wtedy i tylko wtedy, gdy mają te same pary (klucz, wartość)”. to ostatnie zdanie na tej stronie
    • „Odwzorowania (instancje dyktowania) porównują się równo wtedy i tylko wtedy, gdy mają równe pary (klucz, wartość). Porównanie równości kluczy i elementów wymusza refleksyjność”. na tej stronie
RayLuo
źródło
2

Oto ogólne rekurencyjne rozwiązanie podanego problemu:

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

UWAGA: W niektórych przypadkach oryginalny kod zawodzi, a kredyty za naprawienie trafiają do @ olivier-melançon

BPL
źródło
kod kończy się niepowodzeniem z nadzbiorem, który ma dyktowanie zagnieżdżone w liście, w wierszuif not set(value) <= set(superset[key])
Eelco Hoogendoorn
2

Jeśli nie masz nic przeciwko używaniu pydash , jest is_matchtam, który dokładnie to robi:

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
źródło
1

Wiem, że to pytanie jest stare, ale oto moje rozwiązanie umożliwiające sprawdzenie, czy jeden słownik zagnieżdżony jest częścią innego słownika zagnieżdżonego. Rozwiązanie jest rekurencyjne.

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
Orzechówka
źródło
0

Ta funkcja działa dla wartości, których nie można mieszać. Myślę też, że jest przejrzysty i łatwy do odczytania.

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
źródło
0

Krótka rekurencyjna implementacja, która działa dla zagnieżdżonych słowników:

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

Spowoduje to zużycie dykt a i b. Jeśli ktoś zna dobry sposób na uniknięcie tego bez uciekania się do częściowo iteracyjnych rozwiązań, jak w innych odpowiedziach, proszę, powiedz mi. Potrzebowałbym sposobu na podzielenie dyktu na głowę i ogon na podstawie klucza.

Ten kod jest bardziej przydatny jako ćwiczenie programistyczne i prawdopodobnie jest dużo wolniejszy niż inne rozwiązania tutaj, które łączą rekurencję i iterację. Rozwiązanie @ Dziadek do orzechów jest całkiem dobre dla zagnieżdżonych słowników.

Frederik Baetens
źródło
1
W kodzie czegoś brakuje. Po prostu opada w dół o pierwszą wartość zaczynającą się w a(i każdą kolejną pierwszą wartość) popitemznalezionych. Powinien również zbadać inne elementy na tym samym poziomie. Mam pary zagnieżdżonych poleceń, w których zwraca nieprawidłową odpowiedź. (trudno tu przedstawić przykład przyszłościowy, ponieważ opiera się on na kolejności popitem)
blubberdiblub
Dzięki, powinno być teraz naprawione :)
Frederik Baetens
0

Użyj tego obiektu opakowującego, który zapewnia częściowe porównanie i ładne różnice:


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
źródło