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

Learning Emacs Lisp: the fast track!

Ops I did it again. Although I repeatedly said I didn’t love emacs Lisp, I finally managed to learn it.
So I want to share with you my tips, to help entering in the Emacs Lisp world in a fast, fun and easy way.

First of all Lisp is a very elegant language, as you may expect.
Lisp is so elegant you will have to take your time to learn it, because it is a bit cryptic. To make things even worst, emacs function names are less than intuitive. The solution anyway is here: cookbooks!

The following web page will show you a set of tips for making small steps into emacs lisp. The scratch buffer will execute the code interactively (just press C-j)

The second thing you must learn to master is the C-h f (describe-function) key bindings, because will help you a lot. Take the time to study the code of the basic functions you find in your way.

Learn by Example

The best way to start is to use ert unit testing framework which is built in in the last version of Emacs…

(ert-deftest testname ()
(let (...)
....
(should ....)
))

To start playing, see the example on this web page http://steve-yegge.blogspot.it/2008/01/emergency-elisp.html

Lisp magical constructs
To understand better lisp, take a look to this “useless” library http://www.emacswiki.org/emacs/SyntacticSugar
which simply create “alias” to the same function (!)

Other Tips

This web page will teach you a bunch of other tips I find very userful.

 

Exception handling

unwind-protect is the emacs lisp function for “try……finally” idiom. It is very important to use it because will avoid you fatal error on the go. Anyway I like also this form

(condition-case nil
(progn
(do-something)
(do-something-else))
(error
(message "oh no!")
(do-recovery-stuff)))

Userful links

Arduino Esplora

Arduino Esplora is here!
The Arduino Esplora is a microcontroller board derived from the Arduino Leonardo. The Esplora differs from all preceding boards in that it provides a number of built-in, ready-to-use setof onboard sensors for interaction.

News said the price will be around 45 euros
http://www.tgdaily.com/hardware-features/67998-arduino-esplora-is-ready-out-of-the-box-sans-soldering http://www.wired.com/beyond_the_beyond/2012/12/the-arduino-esplora/

Take a look at the board here
http://arduino.cc/en/Main/ArduinoBoardEsplora