Usare la memoria non inizializzata per divertimento e profitto

This entry is part 4 of 5 in the series Formazione

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

Storia Super Rapida di Internet

This entry is part 3 of 5 in the series Formazione

Si parla molto di Internet su… Internet, ma tutte le pagine che trattano della storia di Internet hanno due classici difetti: (a) sono verbosissime e (b) sono in inglese. Così abbiamo pensato di fare un riassunto super compatto nelle pagine di Gioorgi.com…

La prima rete interconnessa è quella creata dal dipartimento di difesa americano, e chiamata ARPANET. Siamo all’inizio degli anni 70.

Continue reading “Storia Super Rapida di Internet”

Percorso Formativo Completo

This entry is part 1 of 5 in the series Formazione

(Updated on 2014)
Programma suggerito del percorso formativo:

  1. Object Oriented Programming (OOP) & Java
  2. Consulenza
  3. Design Patterns
  4. ToolBox as a plus:
    1. JUnit e HttpUnit Cookbook
    2. Regular Expressions
      Esempio animato
      Editor per esercitarsi
    3. Linux
      Filosofia alla base di Unix, da “The Art of Unix Programming” di Eric Steven Raymond
    4. Linguaggio open a scelta, diverso da Java: Python, Perl o Ruby
      Cosa provare: RubyOnRails, GoogleAPI in python, librerie CPAN del Perl
  5. Approfondimenti