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