python 'defaultdict' - ¿Cómo funciona collections.defaultdict?





name is (11)


Los diccionarios son una forma conveniente de almacenar datos para su posterior recuperación por nombre (clave). Las claves deben ser objetos únicos e inmutables, y suelen ser cadenas. Los valores en un diccionario pueden ser cualquier cosa. Para muchas aplicaciones, los valores son tipos simples como enteros y cadenas.

Se vuelve más interesante cuando los valores de un diccionario son colecciones (listas, dictados, etc.) En este caso, el valor (una lista vacía o dict) debe inicializarse la primera vez que se usa una clave determinada. Si bien esto es relativamente fácil de hacer manualmente, el tipo defaultdict automatiza y simplifica este tipo de operaciones. Un valor predeterminado funciona exactamente igual que un dict normal, pero se inicializa con una función ("fábrica predeterminada") que no toma argumentos y proporciona el valor predeterminado para una clave inexistente.

Un defaultdict nunca generará un KeyError. Cualquier clave que no exista obtiene el valor devuelto por la fábrica predeterminada.

from collections import defaultdict
ice_cream = defaultdict(lambda: 'Vanilla')

ice_cream = defaultdict(lambda: 'Vanilla')
ice_cream['Sarah'] = 'Chunky Monkey'
ice_cream['Abdul'] = 'Butter Pecan'
print(ice_cream['Sarah'])
>>>Chunky Monkey
print(ice_cream['Joe'])
>>>Vanilla

Aquí hay otro ejemplo. Cómo usar defaultdict cómo podemos reducir la complejidad

from collections import defaultdict
# Time complexity O(n^2)
def delete_nth_naive(array, n):
    ans = []
    for num in array:
        if ans.count(num) < n:
            ans.append(num)
    return ans

# Time Complexity O(n), using hash tables.
def delete_nth(array,n):
    result = []
    counts = defaultdict(int)

    for i in array:
        if counts[i] < n:
            result.append(i)
            counts[i] += 1
    return result


x = [1,2,3,1,2,1,2,3]
print(delete_nth(x, n=2))
print(delete_nth_naive(x, n=2))

En conclusión, siempre que necesite un diccionario, y el valor de cada elemento debe comenzar con un valor predeterminado, use un valor predeterminado.

He leído los ejemplos en documentos de Python, pero aún no puedo entender qué significa este método. ¿Alguien puede ayudar? Aquí hay dos ejemplos de los documentos de Python

>>> from collections import defaultdict

>>> s = 'mississippi'
>>> d = defaultdict(int)
>>> for k in s:
...     d[k] += 1
...
>>> d.items()
[('i', 4), ('p', 2), ('s', 4), ('m', 1)]

y

>>> s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4), ('red', 1)]
>>> d = defaultdict(list)
>>> for k, v in s:
...     d[k].append(v)
...
>>> d.items()
[('blue', [2, 4]), ('red', [1]), ('yellow', [1, 3])]

Los parámetros int y list son para que?




Dado que la pregunta es sobre "cómo funciona", algunos lectores pueden querer ver más tuercas y tornillos. Específicamente, el método en cuestión es el __missing__(key) . Consulte: https://docs.python.org/2/library/collections.html#defaultdict-objects .

Más concretamente, esta respuesta muestra cómo utilizar __missing__(key) de forma práctica: https://.com/a/17956989/1593924

Para aclarar lo que significa 'callable', aquí hay una sesión interactiva (de 2.7.6, pero también debería funcionar en v3):

>>> x = int
>>> x
<type 'int'>
>>> y = int(5)
>>> y
5
>>> z = x(5)
>>> z
5

>>> from collections import defaultdict
>>> dd = defaultdict(int)
>>> dd
defaultdict(<type 'int'>, {})
>>> dd = defaultdict(x)
>>> dd
defaultdict(<type 'int'>, {})
>>> dd['a']
0
>>> dd
defaultdict(<type 'int'>, {'a': 0})

Ese fue el uso más típico de defaultdict (excepto por el uso sin sentido de la variable x). Puede hacer lo mismo con 0 como valor predeterminado explícito, pero no con un valor simple:

>>> dd2 = defaultdict(0)

Traceback (most recent call last):
  File "<pyshell#7>", line 1, in <module>
    dd2 = defaultdict(0)
TypeError: first argument must be callable

En cambio, lo siguiente funciona porque pasa en una función simple (crea sobre la marcha una función sin nombre que no toma argumentos y siempre devuelve 0):

>>> dd2 = defaultdict(lambda: 0)
>>> dd2
defaultdict(<function <lambda> at 0x02C4C130>, {})
>>> dd2['a']
0
>>> dd2
defaultdict(<function <lambda> at 0x02C4C130>, {'a': 0})
>>> 

Y con un valor por defecto diferente:

>>> dd3 = defaultdict(lambda: 1)
>>> dd3
defaultdict(<function <lambda> at 0x02C4C170>, {})
>>> dd3['a']
1
>>> dd3
defaultdict(<function <lambda> at 0x02C4C170>, {'a': 1})
>>> 



Mi propio 2 ¢: también puede subclase defaultdict:

class MyDict(defaultdict):
    def __missing__(self, key):
        value = [None, None]
        self[key] = value
        return value

Esto podría ser útil para casos muy complejos.




Aquí hay una gran explicación de los defaultdicts: http://ludovf.net/blog/python-collections-defaultdict/

Básicamente, los parámetros int y list son funciones que se pasan. Recuerde que Python acepta nombres de funciones como argumentos. int devuelve 0 de forma predeterminada y la lista devuelve una lista vacía cuando se llama entre paréntesis.

En los diccionarios normales, si en su ejemplo intento llamar d[a] , obtendré un error (KeyError), ya que solo existen las claves m, s, iyp y la clave a no se ha inicializado. Pero en un punto predeterminado, toma el nombre de una función como un argumento, cuando intenta usar una clave que no se ha inicializado, simplemente llama a la función que ha pasado y asigna su valor de retorno como el valor de la nueva clave.







Sin el defaultdict , es probable que pueda asignar nuevos valores a las claves que no se defaultdict , pero no puede modificarlo. Por ejemplo:

import collections
d = collections.defaultdict(int)
for i in range(10):
  d[i] += i
print(d)
# Output: defaultdict(<class 'int'>, {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9})

import collections
d = {}
for i in range(10):
  d[i] += i
print(d)
# Output: Traceback (most recent call last): File "python", line 4, in <module> KeyError: 0



Por lo general, un diccionario de Python lanza un KeyError si intenta obtener un elemento con una clave que no está actualmente en el diccionario. En cambio, el defaultdict simplemente creará los elementos a los que intenta acceder (siempre que, por supuesto, aún no existan). Para crear tal elemento "predeterminado", llama al objeto de función que se pasa en el constructor (más precisamente, es un objeto "llamable" arbitrario, que incluye objetos de tipo y función). Para el primer ejemplo, los elementos predeterminados se crean utilizando int() , que devolverá el objeto entero 0 . Para el segundo ejemplo, los elementos predeterminados se crean utilizando list() , que devuelve un nuevo objeto de lista vacía.




defaultdict significa que si no se encuentra una clave en el diccionario, en lugar de que se KeyError un KeyError , se crea una nueva entrada. El tipo de esta nueva entrada viene dado por el argumento de defaultdict.

Por ejemplo:

somedict = {}
print(somedict[3]) # KeyError

someddict = defaultdict(int)
print(someddict[3]) # print int(), thus 0



La herramienta defaultdict es un contenedor en la clase de colecciones de Python. Es similar al contenedor de diccionario (dict) habitual, pero tiene una diferencia: el tipo de datos de los campos de valor se especifica en la inicialización.

Por ejemplo:

from collections import defaultdict

d = defaultdict(list)

d['python'].append("awesome")

d['something-else'].append("not relevant")

d['python'].append("language")

for i in d.items():

    print i

Esto imprime:

('python', ['awesome', 'language'])
('something-else', ['not relevant'])



Creo que es mejor utilizarlo en lugar de una declaración de cambio de caso. Imagínese si tenemos una declaración de caso de cambio como a continuación:

option = 1

switch(option) {
    case 1: print '1st option'
    case 2: print '2nd option'
    case 3: print '3rd option'
    default: return 'No such option'
}

No hay declaraciones de casos de switch disponibles en Python. Podemos lograr lo mismo usando defaultdict .

from collections import defaultdict

def default_value(): return "Default Value"
dd = defaultdict(default_value)

dd[1] = '1st option'
dd[2] = '2nd option'
dd[3] = '3rd option'

print(dd[4])    
print(dd[5])    
print(dd[3])

Imprime:

Default Value
Default Value
3rd option

En el fragmento de dd anterior, dd no tiene teclas 4 o 5 y, por lo tanto, imprime un valor predeterminado que hemos configurado en una función auxiliar. Esto es bastante mejor que un diccionario sin KeyError donde se lanza un KeyError clave si la clave no está presente. A partir de esto, es evidente que defaultdict parece más a una declaración de caso de cambio donde podemos evitar los complicados bloques if-elif-elif-else .

Otro buen ejemplo que me impresionó mucho de este sitio es:

>>> from collections import defaultdict
>>> food_list = 'spam spam spam spam spam spam eggs spam'.split()
>>> food_count = defaultdict(int) # default value of int is 0
>>> for food in food_list:
...     food_count[food] += 1 # increment element's value by 1
...
defaultdict(<type 'int'>, {'eggs': 1, 'spam': 7})
>>>

Si intentamos acceder a cualquier elemento que no sea eggs y spam no spam , obtendremos un recuento de 0.




Por defecto, cin está sincronizado con stdio, lo que hace que evite cualquier búfer de entrada. Si agrega esto a la parte superior de su main, debería ver un rendimiento mucho mejor:

std::ios_base::sync_with_stdio(false);

Normalmente, cuando un flujo de entrada se almacena en búfer, en lugar de leer un carácter a la vez, el flujo se leerá en partes más grandes. Esto reduce el número de llamadas al sistema, que suelen ser relativamente caras. Sin embargo, dado que el stdio y iostreams basados ​​en FILE* menudo tienen implementaciones separadas y, por lo tanto, buffers separados, esto podría llevar a un problema si ambos se usaron juntos. Por ejemplo:

int myvalue1;
cin >> myvalue1;
int myvalue2;
scanf("%d",&myvalue2);

Si cin leyó más entradas de las que realmente necesitaba, entonces el segundo valor entero no estaría disponible para la función scanf , que tiene su propio búfer independiente. Esto llevaría a resultados inesperados.

Para evitar esto, de forma predeterminada, las secuencias se sincronizan con stdio . Una forma común de lograr esto es hacer que el cin lea cada personaje uno a la vez, según sea necesario, utilizando stdio funciones de stdio . Desafortunadamente, esto introduce una gran cantidad de gastos generales. Para pequeñas cantidades de información, esto no es un gran problema, pero cuando estás leyendo millones de líneas, la penalización de rendimiento es significativa.

Afortunadamente, los diseñadores de la biblioteca decidieron que también debería poder deshabilitar esta función para obtener un mejor rendimiento si supiera lo que estaba haciendo, por lo que proporcionaron el método sync_with_stdio .







python dictionary default-value defaultdict