Lorsqu'une clé manquante est interrogée dans un objet defaultdict, la clé est ajoutée automatiquement au dictionnaire:

from collections import defaultdict

d = defaultdict(int)
res = d[5]

print(d)
# defaultdict(<class 'int'>, {5: 0})
# we want this dictionary to remain empty

Cependant, nous souhaitons souvent ajouter des clés uniquement lorsqu'elles sont affectées explicitement ou implicitement:

d[8] = 1  # we want this key added
d[3] += 1 # we want this key added

Un cas d'utilisation est le comptage simple, pour éviter le surcoût plus élevé de collections.Counter, mais cette fonctionnalité peut également être souhaitable de manière générale.


Contre-exemple [pardonnez le jeu de mots]

Voici la fonctionnalité que je souhaite:

from collections import Counter
c = Counter()
res = c[5]  # 0
print(c)  # Counter()

c[8] = 1  # key added successfully
c[3] += 1 # key added successfully

Mais Counter est beaucoup plus lent que defaultdict(int). Je trouve que les performances sont généralement 2 fois plus lentes par rapport à defaultdict(int).

De plus, il est évident que Counter n'est comparable qu'à l'argument int dans defaultdict, tandis que defaultdict peut prendre list, set, etc.


Existe-t-il un moyen de mettre en œuvre efficacement le comportement ci-dessus; par exemple, en sous-classant defaultdict?


Exemple d'analyse comparative

%timeit DwD(lst)           # 72 ms
%timeit dd(lst)            # 44 ms
%timeit counter_func(lst)  # 98 ms
%timeit af(lst)            # 72 ms

Code de test:

import numpy as np
from collections import defaultdict, Counter, UserDict

class DefaultDict(defaultdict):
    def get_and_forget(self, key):
        _sentinel = object()
        value = self.get(key, _sentinel)

        if value is _sentinel:
            return self.default_factory()
        return value

class DictWithDefaults(dict):
    __slots__ = ['_factory']  # avoid using extra memory

    def __init__(self, factory, *args, **kwargs):
        self._factory = factory
        super().__init__(*args, **kwargs)

    def __missing__(self, key):
        return self._factory()

lst = np.random.randint(0, 10, 100000)

def DwD(lst):
    d = DictWithDefaults(int)
    for i in lst:
        d[i] += 1
    return d

def dd(lst):
    d = defaultdict(int)
    for i in lst:
        d[i] += 1
    return d

def counter_func(lst):
    d = Counter()
    for i in lst:
        d[i] += 1
    return d

def af(lst):
    d = DefaultDict(int)
    for i in lst:
        d[i] += 1
    return d

Remarque concernant le commentaire sur la prime :

La @ solution d'Aran-Fey a été mise à jour depuis l'offre de Bounty, veuillez donc ignorer le commentaire Bounty.

4
jpp 11 avril 2018 à 18:03

3 réponses

Meilleure réponse

Plutôt que de jouer avec collections.defaultdict pour faire faire ce que nous voulons, il semble plus facile de mettre en œuvre le nôtre:

class DefaultDict(dict):
    def __init__(self, default_factory, **kwargs):
        super().__init__(**kwargs)

        self.default_factory = default_factory

    def __getitem__(self, key):
        try:
            return super().__getitem__(key)
        except KeyError:
            return self.default_factory()

Cela fonctionne comme vous le souhaitez:

d = DefaultDict(int)

res = d[5]
d[8] = 1 
d[3] += 1

print(d)  # {8: 1, 3: 1}

Cependant, il peut se comporter de manière inattendue pour les types mutables:

d = DefaultDict(list)
d[5].append('foobar')

print(d)  # output: {}

C'est probablement la raison pour laquelle defaultdict se souvient de la valeur lors de l'accès à une clé non existante.


Une autre option consiste à étendre defaultdict et à ajouter une nouvelle méthode qui recherche une valeur sans s'en souvenir:

from collections import defaultdict

class DefaultDict(defaultdict):
    def get_and_forget(self, key):
        return self.get(key, self.default_factory())

Notez que la méthode get_and_forget appelle à chaque fois le default_factory(), que la clé existe déjà ou non dans le dict. Si cela n'est pas souhaitable, vous pouvez l'implémenter avec une valeur sentinelle à la place:

class DefaultDict(defaultdict):
    def get_and_forget(self, key):
        _sentinel = object()
        value = self.get(key, _sentinel)

        if value is _sentinel:
            return self.default_factory()
        return value

Cela prend mieux en charge les types mutables, car cela vous permet de choisir si la valeur doit être ajoutée au dict ou non.

7
Aran-Fey 14 avril 2018 à 18:48

Votre message de prime indique que la réponse d'Aran-Fey "ne fonctionne pas avec les types mutables". (Pour les futurs lecteurs, le message de prime est "La réponse actuelle est bonne, mais elle ne fonctionne pas avec les types mutables. Si la réponse existante peut être adaptée, ou une autre solution d'option proposée, pour répondre à cet objectif, ce serait l'idéal." ")

Le fait est que cela fonctionne pour les types mutables:

>>> d = DefaultDict(list)
>>> d[0] += [1]
>>> d[0]
[1]
>>> d[1]
[]
>>> 1 in d
False

Ce qui ne fonctionne pas est quelque chose comme d[1].append(2):

>>> d[1].append(2)
>>> d[1]
[]

C'est parce que cela n'implique pas une opération de magasin sur le dict. La seule opération de dict impliquée est une récupération d'élément.

Il n'y a aucune différence entre ce que l'objet dict voit dans d[1] ou d[1].append(2). Le dict n'est pas impliqué dans l'opération append. Sans inspection de pile désagréable et fragile ou quelque chose de similaire, le dict ne peut pas stocker la liste uniquement pour d[1].append(2).


C'est donc sans espoir. Que devez-vous faire à la place?

Eh bien, une option consiste à utiliser un collections.defaultdict normal et à ne pas utiliser [] lorsque vous ne voulez pas stocker les valeurs par défaut. Vous pouvez utiliser in ou get:

if key in d:
    value = d[key]
else:
    ...

Ou

value = d.get(key, sentinel)

Vous pouvez également désactiver la valeur par défaut lorsque vous ne le souhaitez pas. Ceci est souvent raisonnable lorsque vous avez des phases "build" et "read" distinctes, et que vous ne voulez pas la fabrique par défaut pendant la phase de lecture:

d = collections.defaultdict(list)
for thing in whatever:
    d[thing].append(other_thing)
# turn off default factory
d.default_factory = None
use(d)
2
user2357112 supports Monica 13 avril 2018 à 21:01

Si vous voulez simplement un dict qui renvoie une valeur par défaut lorsque vous accédez à une clé non existante, vous pouvez simplement sous-classer dict et implémenter __missing__:

object.__missing__(self, key)

Appelé par dict.__getitem__() pour implémenter self[key] pour les sous-classes dict lorsque key n'est pas dans le dictionnaire.

Cela ressemblerait à ceci:

class DictWithDefaults(dict):
    # not necessary, just a memory optimization
    __slots__ = ['_factory']  

    def __init__(self, factory, *args, **kwargs):
        self._factory = factory
        super().__init__(*args, **kwargs)

    def __missing__(self, key):
        return self._factory()

Dans ce cas, j'ai utilisé une approche semblable à defaultdict, vous devez donc passer un factory qui devrait fournir la valeur par défaut lors de l'appel:

>>> dwd = DictWithDefaults(int)
>>> dwd[0]  # key does not exist
0 
>>> dwd     # key still doesn't exist
{}
>>> dwd[0] = 10
>>> dwd
{0: 10}

Lorsque vous effectuez des affectations (explicitement ou implicitement), la valeur sera ajoutée au dictionnaire:

>>> dwd = DictWithDefaults(int)
>>> dwd[0] += 1
>>> dwd
{0: 1}

>>> dwd = DictWithDefaults(list)
>>> dwd[0] += [1]
>>> dwd
{0: [1]}

Vous vous êtes demandé comment collections.Counter le faisait et depuis CPython 3.6.5, il utilise également __missing__:

class Counter(dict):
    ...

    def __missing__(self, key):
        'The count of elements not in the Counter is zero.'
        # Needed so that self[missing_item] does not raise KeyError
        return 0

    ...

Meilleure performance?!

Vous avez mentionné que la vitesse est un problème, vous pouvez donc faire de cette classe une classe d'extension C (en supposant que vous utilisez CPython), par exemple en utilisant Cython (j'utilise les commandes magiques de Jupyter pour créer la classe d'extension):

%load_ext cython

%%cython

cdef class DictWithDefaultsCython(dict):
    cdef object _factory

    def __init__(self, factory, *args, **kwargs):
        self._factory = factory
        super().__init__(*args, **kwargs)

    def __missing__(self, key):
        return self._factory()

Référence

En fonction de votre référence:

from collections import Counter, defaultdict

def d_py(lst):
    d = DictWithDefaults(int)
    for i in lst:
        d[i] += 1
    return d

def d_cy(lst):
    d = DictWithDefaultsCython(int)
    for i in lst:
        d[i] += 1
    return d

def d_dd(lst):
    d = defaultdict(int)
    for i in lst:
        d[i] += 1
    return d

Étant donné que cela ne fait que compter, ce serait une erreur (impardonnable) de ne pas inclure de référence simplement en utilisant l'initialiseur Counter.

J'ai récemment écrit un petit outil d'analyse comparative qui, je pense, pourrait être utile ici (mais vous pouvez également le faire en utilisant %timeit):

from simple_benchmark import benchmark
import random

sizes = [2**i for i in range(2, 20)]
unique_lists = {i: list(range(i)) for i in sizes}
identical_lists = {i: [0]*i for i in sizes}
mixed = {i: [random.randint(0, i // 2) for j in range(i)]  for i in sizes}

functions = [d_py, d_cy, d_dd, d_c, Counter]

b_unique = benchmark(functions, unique_lists, 'list size')
b_identical = benchmark(functions, identical_lists, 'list size')
b_mixed = benchmark(functions, mixed, 'list size')

Avec ce résultat:

import matplotlib.pyplot as plt

f, (ax1, ax2, ax3) = plt.subplots(1, 3, sharey=True)
ax1.set_title('unique elements')
ax2.set_title('identical elements')
ax3.set_title('mixed elements')
b_unique.plot(ax=ax1)
b_identical.plot(ax=ax2)
b_mixed.plot(ax=ax3)

Notez qu'il utilise une échelle log-log pour une meilleure visibilité des différences:

enter image description here

Pendant longtemps, le Counter(iterable) a été de loin le plus rapide. DictWithDefaultCython et defaultdict étaient égaux (avec DictWithDefault étant légèrement plus rapide la plupart du temps, même si ce n'est pas visible ici) suivi par DictWithDefault puis Counter puis avec Counter avec la boucle manuelle for. C'est drôle comme Counter est le plus rapide et le plus lent.

Ajoutez implicitement la valeur retournée si elle est modifiée

Quelque chose que j'ai ignoré est le fait qu'il diffère considérablement de defaultdict en raison du "retourne simplement la valeur par défaut ne l'enregistre pas" avec les types mutables:

>>> from collections import defaultdict
>>> dd = defaultdict(list)
>>> dd[0].append(10)
>>> dd
defaultdict(list, {0: [10]})

>>> dwd = DictWithDefaults(list)
>>> dwd[0].append(10)
>>> dwd
{}

Cela signifie que vous devez réellement définir l'élément lorsque vous souhaitez que la valeur modifiée soit visible dans le dictionnaire.

Cependant, cela m'a un peu intrigué, donc je veux partager un moyen de faire fonctionner cela (si vous le souhaitez). Mais ce n'est qu'un test rapide et ne fonctionne que pour les appels append utilisant un proxy. Veuillez ne pas utiliser cela dans le code de production (de mon point de vue, cela n'a qu'une valeur de divertissement):

from wrapt import ObjectProxy

class DictWithDefaultsFunky(dict):
    __slots__ = ['_factory']  # avoid using extra memory

    def __init__(self, factory, *args, **kwargs):
        self._factory = factory
        super().__init__(*args, **kwargs)

    def __missing__(self, key):
        ret = self._factory()
        dict_ = self

        class AppendTrigger(ObjectProxy):
            def append(self, val):
                self.__wrapped__.append(val)
                dict_[key] = ret

        return AppendTrigger(ret)

Il s'agit d'un dictionnaire qui renvoie un objet proxy (au lieu de la valeur par défaut réelle) et il surcharge une méthode qui, si elle est appelée, ajoute la valeur de retour au dictionnaire. Et il fonctionne":

>>> d = DictWithDefaultsFunky(list)
>>> a = d[10]
>>> d
[]

>>> a.append(1)
>>> d
{10: [1]}

Mais il a quelques écueils (qui pourraient être résolus mais ce n'est qu'une preuve de concept, donc je ne vais pas essayer ici):

>>> d = DictWithDefaultsFunky(list)
>>> a = d[10]
>>> b = d[10]
>>> d
{}
>>> a.append(1)
>>> d
{10: [1]}
>>> b.append(10)
>>> d  # oups, that overwrote the previous stored value ...
{10: [10]}

Si vous voulez vraiment quelque chose comme ça, vous devez probablement implémenter une classe qui suit vraiment les changements dans les valeurs (et pas seulement les appels append).

Si vous voulez éviter les affectations implicites

Dans le cas où vous n'aimez pas le fait que += ou des opérations similaires ajoutent la valeur au dictionnaire (contrairement à l'exemple précédent qui a même essayé d'ajouter la valeur de manière très implicite), alors vous devriez probablement l'implémenter comme au lieu d'une méthode spéciale.

Par exemple:

class SpecialDict(dict):
    __slots__ = ['_factory']

    def __init__(self, factory, *args, **kwargs):
        self._factory = factory

    def get_or_default_from_factory(self, key):
        try:
            return self[key]
        except KeyError:
            return self._factory()

>>> sd = SpecialDict(int)
>>> sd.get_or_default_from_factory(0)  
0
>>> sd  
{}
>>> sd[0] = sd.get_or_default_from_factory(0) + 1
>>> sd  
{0: 1}

Ce qui est similaire au comportement de la réponse d'Aran-Feys mais au lieu de get avec une sentinelle, il utilise une approche try et catch.

6
MSeifert 14 avril 2018 à 18:50