Repository Bitbucket


Da qualche giorno ho attivato il mio custom domain su bitbucket.org. Con molta fantasia, il mio repository di sorgenti/progetti software è hg.calogerosanfilippo.net.

Annunci

Performance di alcuni linguaggi di programmazione


Non avendo nulla di meglio da fare, mi son messo a valutare le performance di esecuzione dei linguaggi che conosco nella risoluzione del “Problema di Flavio Giuseppe”, la cui soluzione vi permetterà di salvarvi nel caso abbiate deciso all’ultimo minuto di salvarvi da un suicidio di massa (leggete prima in cosa consiste il problema per capire la battutaccia 🙂 ).

Ho testato le prestazioni di C, Java, Python, Ruby, C# usando per tutti le stesse condizioni:

  • 100000 iterazioni
  • risoluzione, ad ogni iterazione, del problema che dovette affrontare Flavio Giuseppe in persona: 40 partecipanti al suicidio e determinazione del prossimo suicida contando a 3 a 3 a giro

I test sono stati fatti con questa configurazione:

OS: Mac OS 10.5.4

CPU: Intel(R) Core(TM)2 CPU T7600 @ 2.33GHz

RAM :2 GB

Il risultato del test è dato dal tempo medio (su 10 test )per ogni iterazione espresso in microsecondi.

Ecco la tabella dei risultati.

Linguaggio Versione Note Tempo medio per iterazione (microsecondi)
Ansi C Compilatore: i686-apple-darwin9-gcc-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465) Compilazione con flag -O3 0.235951
Ansi C++ Compilatore: i686-apple-darwin9-g++-4.0.1 (GCC) 4.0.1 (Apple Inc. build 5465) Compilazione con flag -O3
Uso di funzioni inline
0.205846
C# Mono Framework – 1.9.1_3 0.846871
Java java version “1.5.0_13” 1.898368
java version “1.6.0_5” 0.665434
Python Python 2.5.1 (r251:54863, Jan 17 2008, 19:35:17) 24.0439097881
Uso del compilatore JIT Psyco 1.6 5.55800628662
Ruby ruby 1.8.6 (2008-03-03 patchlevel 114) 55.700048

Per analizzare i risultati occorre precisare che mi sono rifatto allo standard C89 per il C (che non prevede le funzioni inline); ecco perchè il C++ con le funzioni inline risulta più performante.

Se provate a compilare i sorgenti C che seguono mettendo la parola chiave inline nell’implementazione della funzione e compilando usando il flag -std=c99 vedrete che le prestazioni di C e C++ saranno uguali. Nel C++ ciò che fa perder prestazioni è il binding tardivo: polimorfismo, template ecc.

Con notevole sorpresa, ho constatato come la JVM non sfigura affato; addirittura con Java 6 i tempi medi sono più che dimezzati.

I fanalini di coda (c’era da aspettarselo) sono Python e Ruby, col primo in vantaggio sul secondo; per l’occasione ho sperimentato in Python l’uso di Psyco, un compilatore JIT, e devo dire che i risultati si vedono: l’esecuzione del codice col modulo Psyco attivo è più veloce di circa l’80% rispetto a quella senza Psyco.

L’algoritmo che ho usato per risolvere il problema è trattato in questa pubblicazione; tale algoritmo ha una complessità pari a O(m + \log_{\frac{m}{m-1}} \left ( \frac{n}{m} \right ) ), dove n è il numero di persone nel gruppo e m è il numero usato per la conta.

Di seguito troverete il codice usato per fare il test nei vari linguaggi.

Codice C:
Continua a leggere “Performance di alcuni linguaggi di programmazione”

registerimage 1.0.2


Il rilascio della versione 1.6 di VirtualBox della Sun mi ha portato ad effettuare qualche importante modifica al mio software registerimage per la registrazione automatica delle immagini virtuale create per il progetto VirtualBox Images.

L’ultima versione rilasciata è quindi la 1.0.2 (come si evince dal titolo del post).

L’ultima versione di VirtualBox ha introdotto delle novità nella struttura del file di configurazione di ciascuna macchina virtuale; questo ha reso inutilizzabile la versione 1.0.1 di registerimage, la quale è implementata per gestire solo la versione 1.2 del file xml.

La versione 1.0.2 introduce alcune novità:

  1. modifiche “stilistiche” nel codice.
  2. meccanismo di parsing dell’input da terminale più “intelligente” di quello usato nella versione 1.0.1.
  3. miglioramento nella procedura di registrazione delle immagini virtuali (adesso il programma sa gestire in maniera più funzionare i casi in cui l’hard disk virtuale è stato precedentemente registrato o i casi in cui si prova a ri-registrare un’immagine).
  4. meccanismo di conversione dei vecchi file xml versione 1.2 in file xml versione 1.3 (è quindi garantita la compatibilità tra le vecchie immagini presenti online e la nuova versione di VirtualBox)

Come al solito potete scaricare i sorgenti cliccando qui e il binario per Windows cliccando qui.

Non scaricate questa versione. Scaricate l’ultima versione (la 1.0.3) qui

Quickselect


Il Quickselect è un algoritmo randomizzato ricorsivo che trova l’elemento che si troverebbe in k-esima posizione se l’array in cui si trova fosse ordinato.

Su un array di grandezza n l’algoritmo esegue O(n^2) confronti nel caso peggiore e O(n) nel caso atteso. Si basa sull’algoritmo Quicksort.

L’idea di base che sta alla base dell’algoritmo è molto semplice: se si deve estrarre l’elemento che si troverebbe in k-esima posizione se l’array fosse ordinato, basta ordinare di volta in volta la porzione dell’array in cui l’elemento si troverebbe, trascurando il resto dell’array.

Ecco un’implementazione in C di questo algoritmo:
Continua a leggere “Quickselect”

registerimage 1.0.1!


Ho corretto qualche piccolo bug della prima versione del mio software di registrazione di immagini virtuali VirtualBox.

A causa di una mia disattenzione, la versione 1.0 prendeva in input 3 argomenti; mi sono ricordato dopo che il terzo argomento poteva esser ricavato automaticamente, senza alcuna interazione con l’utente (che può sempre sbagliare).
Potete scaricare adesso la versione 1.0.1 di registerimage .

I parametri da riga di comando (ho intenzione di scrivere un’interfaccia grafica al più presto) sono:

  1. File .xml dell’immagine virtuale che volete aggiungere alla vostra VirtualBox;
  2. File VirtualBox.xml che trovate nella cartella di installazione di VirtualBox;

Cliccando qui potrete scaricare sia i sorgenti che i binari per Windows.

Non scaricate questa versione. Scaricate l’ultima versione (la 1.0.3) qui

Per qualsiasi problema, non esitate a contattarmi!

PS: naturalmente per usare il mio programma, dovrete scaricare qualcuna delle nostre immagini!!!

registerimage 1.0 released!!


In un post precedente ho parlato della mia partecipazione al progetto VirtualBox® Images.

Uno dei principali problemi relativi all’utilizzo delle nostre immagini è quello legato alla difficile portabilità delle immagini su macchine virtuali diverse da quella dove sono state create.

Per risolvere il problema occorrerebbe modificare i file xml di configurazione dell’immagine e di VirtualBox® in modo da registrare correttamente l’immagine.

Visto che non è molto piacevole fare queste modifiche a mano, ho scritto un programmino in C (usando la libxml2) che fa tutte le operazioni necessarie.

I sorgenti possono esser scaricati qui

Non scaricate questa versione. Scaricate l’ultima versione qui

.

I binary per Windows li trovate qui

Non scaricate questa versione. Scaricate l’ultima versione qui

.

Una volta scompattato l’archivio, occorre compilare i sorgenti usando make.

Il programma prende in input:

  • Il file xml della macchina virtuale che si vuole usare
  • Il file VirtualBox.xml
  • Il sistema operativo su cui gira la macchina virtuale (linux, windows, macosx)

Ecco un esempio di utilizzo:
valinor:registerimage feanor$ ./registerimage ../Machines/MINIX\ 3.1.2/MINIX\ 3.1.2.xml ../../Library/VirtualBox/VirtualBox.xml macosx

Una volta modificati i file xml usando il mio programmino, potete copiare il file .xml e.vdi che avete scaricato dal sito del progetto nelle rispettive directory di VirtualBox®.

Per qualsiasi problema, non esitate a contattarmi!!

Usare Graphviz e DOT per stampare un albero binario


Graphviz è un pacchetto di software open source sviluppato dagli AT&T Research Labs per la rappresentazione di grafi descritti mediante il linguaggio di scripting DOT.

DOT è un linguaggio abbastanza semplice ed immediato. Per esempio, il codice DOT che mi ha permesso di realizzare l’immagine della rotazione di un albero, presente nel post sugli alberi AVL, è il segunete:
Continua a leggere “Usare Graphviz e DOT per stampare un albero binario”