[pyar] Necesito una estructura para deduplicar diccionarios complejos

[Claudio Freire]

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

PS2: Porque si no, o mejor si no es necesario que sea pure-python, hay
una implementación eficiente como dependencia de la CDpedia (el suffix
tree).