[pyar] Necesito una estructura para deduplicar diccionarios complejos

[Claudio Freire]

2015-05-08 22:15 GMT-03:00 Claudio Freire <klaussfreire en gmail.com>:
> 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


PS: tiene esto que ver con la construcción de los índices de la
cdpedia en pure-python?