[pyar] Necesito una estructura para deduplicar diccionarios complejos

[Claudio Freire]

2015-04-30 11:19 GMT-03:00 Facundo Batista <facundobatista en gmail.com>:
> 2015-04-30 11:14 GMT-03:00 Daniel Moisset <dmoisset en machinalis.com>:
>
>> Podes hacer content-based adressing (es lo que se hace en los repos git).
>> Usas un hash con mas bits, y supones que si el hash es igual, el contenido
>> es igual. Si tu hash de k bits es bueno, la probabilidad de colicion es 2 **
>> (-k), que puede ser tan chico como quieras.
>
> Sí, y no me joden esos falsos negativos. Pero volvemos al tema de
> hashear el diccionario, que es lo complicado.
>
> Tendría que recorrerlo con las claves (ordenadas o no), e ir
> acumulando hashes o alguna cosa así


Podés construir un frozendict (que tendrías que codear), hasheable,
que cachee el hash.

Luego te sale en O(n) (creo) la deduplicación (asumiendo bondad suprema):

http://linkode.org/8HQ1DjMe4OTMhZEEp6x7S6

Funciona, no sé si es rápido