usar - objeto tipo diccionario python

dict personalizado que permite eliminar durante la iteración

Question

ACTUALIZADO según la respuesta de Lennart Regebro

Supongamos que itera a través de un diccionario y, a veces, necesita eliminar un elemento. El siguiente es muy eficiente:

remove = []
for k, v in dict_.items():
  if condition(k, v):
    remove.append(k)
    continue
  # do other things you need to do in this loop
for k in remove:
  del dict_[k]

El único encabezado aquí es construir la lista de claves para eliminar; a menos que crezca en comparación con el tamaño del diccionario, no es un problema. Sin embargo, este enfoque requiere una codificación adicional, por lo que no es muy popular.

El popular enfoque de comprensión dict:

dict_ = {k : v for k, v in dict_ if not condition(k, v)}
for k, v in dict_.items():
  # do other things you need to do in this loop

da como resultado una copia completa del diccionario, y también tiene el riesgo de un rendimiento tonto si los diccionarios crecen demasiado o se llama a menudo la función contenedora.

Un enfoque mucho mejor es copiar las claves solo en lugar de todo el diccionario:

for k in list(dict_.keys()):
  if condition(k, dict_[k]):
    del dict_[k]
    continue
  # do other things you need to do in this loop       

(Tenga en cuenta que todos los ejemplos de código están en Python 3, por lo que keys() , items() devuelve una vista, no una copia).

En la mayoría de los casos, no afectará mucho el rendimiento, ya que el momento de verificar incluso la condición más simple (sin mencionar otras cosas que está haciendo en el ciclo) suele ser mayor que el tiempo para agregar una clave a una lista.

Aún así, me pregunto si es posible evitar incluso eso con un diccionario personalizado que permita eliminar al iterar:

for k, v in dict_.items():
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

Tal vez un iterador siempre podría mirar hacia el futuro, de modo que cuando se __next__ el __next__ , el iterador sepa a dónde ir sin siquiera mirar el elemento actual (solo tendría que mirar el elemento cuando llegue por primera vez). Y si no hay un elemento siguiente, el iterador podría simplemente establecer el indicador que provocaría que la excepción __next__ se __next__ cada __next__ se vuelva a llamar a __next__ .

Si el elemento que el iterador intenta avanzar resulta eliminado, está bien hacer una excepción; no es necesario admitir eliminaciones mientras se realizan varias iteraciones simultáneamente.

¿Hay algún problema con este enfoque?

Un problema es que no estoy seguro de que se pueda hacer sin gastos indirectos en comparación con el dict existente; de lo contrario, ¡sería más rápido usar el enfoque de list(dict_) !

ACTUALIZAR:

Probé todas las versiones. No informo el momento, ya que claramente dependen mucho de la situación exacta. Pero parece seguro decir que, en muchos casos, el enfoque más rápido probablemente sea la list(dict_) . Después de todo, si lo piensas, la copia es la operación más rápida que crece linealmente con el tamaño de la lista; casi cualquier otro gasto general, siempre y cuando sea proporcional al tamaño de la lista, es probable que sea más grande.

Realmente me gustan todas las ideas, pero dado que tengo que seleccionar solo una, estoy aceptando la solución del administrador de contexto ya que permite usar el diccionario como normal o "mejorado" con cambios de código muy pequeños.

Answer 1

1. Puede hacer una copia de la lista de claves (no es necesario que copie los valores te) al comienzo de la iteración, e iterar sobre ellas (verificando que la clave esté allí). Esto es ineficiente si hay muchas claves.
2. Puede organizar incrustar su primer código de ejemplo dentro de una clase. __iter__ y __delitem__ y otros métodos especiales deben colaborar para mantener eliminada una lista de elementos mientras se produce una iteración. Cuando no hay iteraciones actuales, __delitem__ puede simplemente eliminar un elemento, pero cuando ocurre al menos una iteración, simplemente debe agregar la clave que se eliminará en una lista. Cuando termine la última iteración activa, en realidad debería eliminar cosas. Esto es algo ineficiente si hay muchas claves para eliminar y, por supuesto, explotará si siempre hay al menos una iteración.

Answer 2

Como nota, puede almacenar los elementos para eliminar en algún lugar y aplazar la eliminación de ellos hasta más tarde. El problema entonces es cuándo purgarlos y cómo asegurarse de que finalmente se llame al método de purga. La respuesta a esto es un administrador de contexto que también es una subclase de dict .

class dd_dict(dict):    # the dd is for "deferred delete"
    _deletes = None
    def __delitem__(self, key):
        if key not in self:
            raise KeyError(str(key))
        dict.__delitem__(self, key) if self._deletes is None else self._deletes.add(key)
    def __enter__(self):
        self._deletes = set()
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                dict.__delitem__(self, key)
            except KeyError:
                pass
        self._deletes = None

Uso:

# make the dict and do whatever to it
ddd = dd_dict(a=1, b=2, c=3)

# now iterate over it, deferring deletes
with ddd:
    for k, v in ddd.iteritems():
        if k is "a":
            del ddd[k]
            print ddd     # shows that "a" is still there

print ddd                 # shows that "a" has been deleted

Si no estás en un bloque with , por supuesto, las eliminaciones son inmediatas; como esta es una subclase dict , funciona igual que un dict regular fuera de un administrador de contexto.

También podría implementar esto como una clase contenedora para un diccionario:

class deferring_delete(object):
    def __init__(self, d):
        self._dict = d
    def __enter__(self):
        self._deletes = set()
        return self
    def __exit__(self, type, value, tb):
        for key in self._deletes:
            try:
                del self._dict[key]
            except KeyError:
                pass
        del self._deletes
    def __delitem__(self, key):
        if key not in self._dict:
            raise KeyError(str(key))
        self._deletes.add(key)

d = dict(a=1, b=2, c=3)

with deferring_delete(d) as dd:
    for k, v in d.iteritems():
        if k is "a":
            del dd[k]    # delete through wrapper

print d

Incluso es posible hacer que la clase contenedora sea completamente funcional como diccionario, si lo desea, aunque eso es un poco más de código.

En lo que respecta al rendimiento, no se trata de una victoria, pero me gusta desde el punto de vista de la facilidad con los programadores. El segundo método debe ser muy ligeramente más rápido ya que no está probando un indicador en cada eliminación.

Answer 3

Esto podría funcionar como un compromiso entre los dos ejemplos: dos líneas más largas que la segunda, pero más cortas y ligeramente más rápidas que la primera. Python 2:

dict_ = {k : random.randint(0, 40000) for k in range(0,200000)}

dict_remove = [k for k,v in dict_.iteritems() if v < 3000]
for k in dict_remove:
    del dict_[k]

Dividirse en una función y cada llamada debe ser de una línea (ya sea que su llamada sea más legible o no):

def dict_remove(dict_, keys):
    for k in keys:
        del dict_[k]

dict_remove(dict_, [k for k,v in dict_.iteritems() if v < 3000])

Independientemente de dónde esté almacenado el código, tendrá que almacenar las claves que necesitan eliminación en algún lugar. La única forma de evitarlo es usar expresiones generadoras, que explotarán en el momento en que elimine una clave por primera vez.

Answer 4

Implementación ingenua para Python 2.xy 3.x:

import sys
from collections import deque


def _protect_from_delete(func):
    def wrapper(self, *args, **kwargs):
        try:
            self._iterating += 1
            for item in func(self, *args, **kwargs):
                yield item
        finally:
            self._iterating -= 1
            self._delete_pending()
    return wrapper

class DeletableDict(dict):
    def __init__(self, *args, **kwargs):
        super(DeletableDict, self).__init__(*args, **kwargs)
        self._keys_to_delete = deque()
        self._iterating = 0

    if sys.version_info[0] != 3:
        iterkeys = _protect_from_delete(dict.iterkeys)
        itervalues = _protect_from_delete(dict.itervalues)
        iteritems = _protect_from_delete(dict.iteritems)
    else:
        keys = _protect_from_delete(dict.keys)
        values = _protect_from_delete(dict.values)
        items = _protect_from_delete(dict.items)  
    __iter__ = _protect_from_delete(dict.__iter__)

    def __delitem__(self, key):
        if not self._iterating:
            return super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.append(key)

    def _delete_pending(self):
        for key in self._keys_to_delete:
            super(DeletableDict, self).__delitem__(key)
        self._keys_to_delete.clear()

if __name__ == ''__main__'':
    dct = DeletableDict((i, i*2) for i in range(15))
    if sys.version_info[0] != 3:
        for k, v in dct.iteritems():
            if k < 5:
                del dct[k]
        print(dct)
        for k in dct.iterkeys():
            if k > 8:
                del dct[k]
        print(dct)
        for k in dct:
            if k < 8:
                del dct[k]
        print(dct)
    else:
        for k, v in dct.items():
            if k < 5:
                del dct[k]
        print(dct)

Al iterar sobre claves, elementos o valores, establece el self._iterating . En __delitem__ comprueba la posibilidad de eliminar elementos y almacena claves en la cola temporal. Al final de las iteraciones, elimina todas las claves pendientes.

Es una implementación muy ingenua, y no recomendaría su uso en el código de producción.

EDITAR

Se agregó soporte para Python 3 y mejoras de los comentarios de @jsbueno .

Python 3 corre en Ideone.com

Answer 5

Lo que debe hacer es no modificar la lista de claves que itera. Puedes hacer esto de tres maneras:

1. Haga una copia de las claves en una lista separada e itere sobre eso. A continuación, puede eliminar las claves de forma segura en el diccionario durante la iteración. Este es el más fácil y el más rápido, a menos que el diccionario sea enorme, en cuyo caso debería empezar a pensar en utilizar una base de datos en cualquier caso. Código:

   for k in list(dict_):
     if condition(k, dict_[k]):
       del dict_[k]
       continue
     # do other things you need to do in this loop

2. Haga una copia no de las claves que está iterando, sino una copia de las claves que debe eliminar. En otras palabras, no elimine estas claves mientras itera en su lugar, agréguelas a una lista, luego borre las claves en esa lista una vez que termine de iterar. Esto es un poco más complicado que 1. pero mucho menos que 3. También es rápido. Esto es lo que haces en tu primer ejemplo.

   delete_these = []
   for k in dict_:
     if condition(k, dict_[k]):
       delete_these.append(k)
       continue
     # do other things you need to do in this loop
   
   for k in delete_these:
       del dict_[k]

3. La única manera de evitar hacer una especie de lista nueva es, como sugiere, hacer un diccionario especial. Pero eso requiere que cuando elimines las teclas, no las borre, sino que las marques como eliminadas y luego las borres de verdad solo cuando llames a un método de purga. Esto requiere una gran cantidad de implementación y hay casos límite y te olvidarás de olvidarte de purgar, etc. Y repetir el diccionario aún debe incluir las claves eliminadas, lo que te morderá en algún momento. Entonces no recomendaría esto. Además, sin importar cómo implemente esto en Python, es probable que acabe una vez más con una lista de cosas para eliminar , por lo que es probable que sea una versión complicada y propensa a errores de 2. Si lo implementa en C, podría Probablemente salga con la copia al agregar las banderas directamente en la estructura de clave hash. Pero como se mencionó, los problemas realmente eclipsan los beneficios.

Answer 6

Puede lograr esto al iterar sobre una lista estática de los pares clave / valor del diccionario, en lugar de iterar sobre una vista del diccionario.

Básicamente, iterar sobre la list(dict_.items()) lugar de dict_.items() funcionará:

for k, v in list(dict_.items()):
  if condition(k, v):
    del dict_[k]
    continue
  # do other things you need to do in this loop

Aquí hay un ejemplo ( ideone ):

dict_ = {0: ''a'', 1: ''b'', 2: ''c'', 3: ''d'', 4: ''e'', 5: ''f'', 6: ''g''}
for k, v in list(dict_.items()):
    if k % 2 == 0:
        print("Deleting  ", (k, v))
        del dict_[k]
        continue
    print("Processing", (k, v))

y el resultado:

Deleting   (0, ''a'')
Processing (1, ''b'')
Deleting   (2, ''c'')
Processing (3, ''d'')
Deleting   (4, ''e'')
Processing (5, ''f'')
Deleting   (6, ''g'')

Answer 7

Python 3.2 tiene tal dict en el stdlib:

#!/usr/bin/env python3
from collections import OrderedDict as odict

d = odict(zip(range(3), "abc"))
print(d)
for k in d:
    if k == 2:
       del d[k]
print(d)

Salida

OrderedDict([(0, ''a''), (1, ''b''), (2, ''c'')])
OrderedDict([(0, ''a''), (1, ''b'')])

La iteración se realiza sobre una lista enlazada, vea la implementación del método __iter__() . La eliminación es segura (en Python 3.2) a pesar de que los elementos son referencias débiles.