[pyar] Necesito una estructura para deduplicar diccionarios complejos

[Tordek]

O sea que en mi mail original entendí bien: tu data es hasheable.

El hash es recursivo, pero como estás guardando referencias a las copias
que ya existen, no hace falta hashear el contenido de los valores, solo su
ID. (Aunque no sé qué guardas en las hojas, supongo que una marca única,
para mantener el id de la marca constanet)

def hash(node):
    return md5.new(str([(k, id(v)) for (k, v) in node.items])).digest()

y para deduplicar usas un defaultdict

dedup_store = defaultdict(list)

def dedup(data):
    cache = dedup_store[hash(data)]
    for node in cache:
        if node == data:
            return node
    cache.append(data)
    return data

Buscás en dedup_store todos los árboles con el mismo hash. Si existe
alguno, recorrés la lista y te fijás si alguno es lo que buscás. (Ahí
depende de vos como se implemente ==, aunque imagino que el default
alcanza). Si lo es, retornás el dato viejo.

Si no lo encontraste en la lista es por 2 motivos: colisión, o no había
nodos con ese hash y defaultdict te da una lista vacía. Simplemente agregás
el nuevo elemento a la lista y lo retornás.


2015-04-30 9:14 GMT-03:00 Facundo Batista <facundobatista en gmail.com>:

> Mi problema es: estoy construyendo un árbol gigante (en las pruebas,
> con un 1% de los datos, termino con 660 mil nodos), me di cuenta que
> al final, MUCHOS nodos tienen el mismo subtree abajo.
>
> Como tengo problemas de memoria, se me ocurrió deduplicarlos (esto es,
> en vez de tener dos diccionarios iguales, tener el mismo dos veces).
>
> El código que hace esto bien (pero de forma terriblemente lenta), es
> el siguiente:
>
>         # llego acá con "data" que es el dict a deduplicar
>         for prev in self._deduplic:
>             if prev == data:
>                 data = prev
>                 break
>         else:
>             self._deduplic.append(data)
>
> (mismo código: http://linkode.org/C3r3o25PETWAB3nL57LqI2 )
>
> ¿Cómo se les ocurre hacer esto mismo pero más rápido?
>
> ¡Gracias! Slds.
>
> --
> .    Facundo
>
> Blog: http://www.taniquetil.com.ar/plog/
> PyAr: http://www.python.org/ar/
> Twitter: @facundobatista
> _______________________________________________
> pyar mailing list pyar en python.org.ar
> http://listas.python.org.ar/listinfo/pyar
>
> PyAr - Python Argentina - Sitio web: http://www.python.org.ar/
>
> La lista de PyAr esta Hosteada en USLA - Usuarios de Software Libre de
> Argentina - http://www.usla.org.ar
>
------------ próxima parte ------------
Se ha borrado un adjunto en formato HTML...
URL: <http://listas.python.org.ar/pipermail/pyar/attachments/20150430/32db92e9/attachment.html>