Usare la memoria non inizializzata per divertimento e profitto

Ciao a tutti, è venerdì!
Se avete due minuti di tempo, volevo indicarvi un articolo su un algoritmo non banale, molto ben descritto qui:

http://research.swtch.com/sparse

This is the story of a clever trick that’s been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array.

In soldoni, viene descritto come implementare un “Set sparso” in modo che quasi tutte le sue operazioni avvengano in tempo costante:

Operation Bit Vector Sparse set
is-member O(1) O(1)
add-member O(1) O(1)
clear-set O(m) O(1)
iterate O(m) O(n)

The sparse set is as fast or faster than bit vectors for every operation. The only problem is the space cost: two words replace each bit. Still, there are times when the speed differences are enough to balance the added memory cost.

E voi vi chiederete: cosa me ne faccio di un set ordinato e veloce?

I set molto grandi di interi sono una struttura base usata da Google per il calcolo del PageRank, ed in generale fanno capolino in qualunque database NoSQL

Altri approfondimenti:
http://infolab.stanford.edu/~ullman/mmds/ch5.pdf

http://www.fc.up.pt/dcc/Pubs/TReports/TR06/dcc-2006-06.pdf

Series NavigationStoria Super Rapida di InternetLicenze OSS: cartina tornasole

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.