[pyar] Necesito una estructura para deduplicar diccionarios complejos

[Facundo Batista]

2015-04-30 17:20 GMT-03:00 Tordek <kedrot en gmail.com>:

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

La idea de usar el id() es muy buena!

La tomo.


> 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.

Al principio hice eso. Después miré, con un ejemplo de 100 mil
palabras (casi tres millones de nodos), y todas las listas tenía 1 de
largo. Así que dejé de usar esas listas (que consumen memoria!) y puse
un if para que de última, si son distintos, devuelva el nuevo (sin
cachearlo... es un caso que creo que no va a pasar nunca, pero si
pasara, igual funca).

-- 
.    Facundo

Blog: http://www.taniquetil.com.ar/plog/
PyAr: http://www.python.org/ar/
Twitter: @facundobatista