On 27/11/17 21:38, Francesc Alted wrote: > En tu > caso creí entender que ordenabas los valores de alguna manera, pero > viendo los ratios que obtienes, y que son bastante más pobres que mi > prueba, posiblemente no entiendo bien a que te refieres cuando dices > 'ordenados'.
Ordeno los hashes de los bloques que tiene cada nodo. Esto tiene la ventaja de que puedo hacer un MMAP de ese fichero y hacer un LOOKUP directo mediante bisección. El problema de eso es que con 2000 páginas por fichero, tengo que hacer 11 accesos a páginas diferentes. Los primeros niveles muy posiblemente estén cacheados en RAM, pero los niveles inferiores son aleatorios y poco cacheables. Muy lejos de los dos accesos a páginas que me da un "cuckoo hash". Otra ventajas de tener una lista ordenada de hashes es que operaciones como la unión, la resta de conjuntos o la intersección son muy sencillos y eficientes. Me basta con revisar un único elemento de cada conjunto y, encima, en streaming secuencial. Eso les encanta a las cachés de la CPU :-). Pasar eso a un "cuckoo hash" supone que, por ejemplo, una intersección, una resta o una unión de conjuntos requieres dos accesos secuenciales y un acceso aleatorio (en vez de dos accesos secuenciales). El acceso aleatorio es costoso pero tolerable, y los "lookups" pasan de requerir once accesos a páginas diferentes a requerir dos como mucho. La complejidad en sí del algoritmo es pequeña. La pregunta es... ¿Se puede hacer mejor? -- Jesús Cea Avión _/_/ _/_/_/ _/_/_/ j...@jcea.es - http://www.jcea.es/ _/_/ _/_/ _/_/ _/_/ _/_/ Twitter: @jcea _/_/ _/_/ _/_/_/_/_/ jabber / xmpp:j...@jabber.org _/_/ _/_/ _/_/ _/_/ _/_/ "Things are not so easy" _/_/ _/_/ _/_/ _/_/ _/_/ _/_/ "My name is Dump, Core Dump" _/_/_/ _/_/_/ _/_/ _/_/ "El amor es poner tu felicidad en la felicidad de otro" - Leibniz
signature.asc
Description: OpenPGP digital signature
_______________________________________________ Python-es mailing list Python-es@python.org https://mail.python.org/mailman/listinfo/python-es
