jump to navigation

Repository Bitbucket 5 ottobre 2010

Posted by fripp in About me, C, C++, Informatica, Programmazione, Python.
Tags: , ,
add a comment

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 14 luglio 2008

Posted by fripp in About me, Algoritmi, C, GNU/Linux, Informatica, Java, Mac OS X, Matematica, Programmazione, Python, Ruby, Sistemi Operativi, Unix.
Tags: , , , , , , , , , , , ,
add a comment

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:
(altro…)

registerimage 1.0.2 12 maggio 2008

Posted by fripp in C, Debian, GNU/Linux, Informatica, Mac OS X, Programmazione, Sistemi Operativi, Ubuntu, Unix, VirtualBox Images, Windows.
Tags: , , , , ,
1 comment so far

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 8 maggio 2008

Posted by fripp in Algoritmi, C, C++, Debian, GNU/Linux, Informatica, Java, Mac OS X, Matematica, Ordinamento, Programmazione, Quickselect, Quicksort, Selezione, Sistemi Operativi, Unix.
Tags: , , , , ,
add a comment

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:
(altro…)

registerimage 1.0.1! 27 aprile 2008

Posted by fripp in C, GNU/Linux, Informatica, Mac OS X, Programmazione, Sistemi Operativi, Unix, VirtualBox Images, Windows.
Tags: , , , , , ,
add a comment

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!! 21 aprile 2008

Posted by fripp in C, Debian, Gnome, GNU/Linux, Informatica, Mac OS X, Programmazione, Sistemi Operativi, Ubuntu, Unix, VirtualBox Images.
Tags: , , ,
add a comment

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 20 febbraio 2008

Posted by fripp in Algoritmi, C, C++, Debian, DOT, Gnome, GNU/Linux, Informatica, Mac OS X, Programmazione, Scripting, Sistemi Operativi, Ubuntu, Unix.
Tags: , , , , , , ,
2 comments

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:
(altro…)

Alberi AVL 19 febbraio 2008

Posted by fripp in Algoritmi, C, C++, Informatica, Programmazione.
Tags: , , , , , , ,
5 comments

Gli alberi AVL sono degli alberi binari bilanciati in altezza. Un albero binario si dice bilanciato in altezza se, per ciascun nodo dell’albero, l’altezza del sottoalbero sinistro differisce dall’altezza del sottoalbero destro al più di una unità.

Per gli alberi AVL si parla anche di fattore di sbilanciamento di un nodo e lo si definisce come la differenza tra l’altezza del sottoalbero sinistro e l’altezza del sottoalbero destro. Banalmente, in un albero AVL il fattore di sbilanciamento di ciascun nodo è, in valore assoluto, \leq 1.

A differenza di un albero binario “tradizionale”, un albero AVL mantiene la proprietà di bilanciamento in qualsiasi circostanza, sia dopo un inserimento di un nuovo valore che dopo la cancellazione.

Si può dimostrare che l’altezza di un albero AVL di n nodi è sempre O(\log n) e quindi tutte le operazioni di gestione dell’albero (ricerca, inserimento e cancellazione) hanno costo O(\log n).
(altro…)

Radix sort 5 febbraio 2008

Posted by fripp in Algoritmi, C, GNU/Linux, Informatica, Ordinamento, Programmazione, Radix sort, Unix.
Tags: , , , ,
add a comment

Il radix sort è un algoritmo di ordinamento che permette di ordinare un insieme di n record con chiavi intere comprese tra 1 e k con un costo computazionale pari a O(n(1+\frac{\log k}{\log n})).

L’algoritmo utilizza un altro algoritmo di ordinamento per chiavi intere, chiamato Bucketsort; in particolare, il Radix sort effettua un numero di chiamata di Bucketsort pari al numero di cifre in cui si può esprimere la chiave più grande della collezione in una data base. Il radix ordina le chiavi a partire dalla loro cifra meno significativa.

Il costo di esecuzione O(n(1+\frac{\log k}{\log n})) si riferisce al caso in cui la base b=O(n).

Per maggiori informazioni sull’algoritmo, cliccate qui.

Ecco l’implementazione in C dell’algoritmo. Il codice in questione si limita ad ordinare un array di interi, ma è possibile estenderlo in modo da ordinare un qualsiasi array di record con chiavi intere.

Nell’implementazione si è fatto utilizzo della struttura dati GQueue, una lista doppiamente linkata messa a disposizione dalla libreria Glib:
(altro…)

Levenshtein distance – An optimized version 15 gennaio 2008

Posted by fripp in Algoritmi, C, Informatica, Matematica, Programmazione.
Tags:
1 comment so far

We can adapt the algorithm to use less space, O(m) instead of O(mn), since it only requires that the previous row and current row be stored at any one time.
This is the second version of the algorithm

int levenshtein_distance(char *x, char *y){
int m=strlen(x);
int n=strlen(y);

register int i,j;
int distance;
int *prev=malloc((n+1)*sizeof(int));
int *curr=malloc((n+1)*sizeof(int));
int *tmp=0;

for(i=0;i<=n;i++) prev[i]=i; for(i=1;i<=m;i++){ curr[0]=i; for(j=1;j<=n;j++){ if(x[i-1]!=y[j-1]){ int k=min(curr[j-1],prev[j-1],prev[j]); curr[j]=k+1; }else{ curr[j]=prev[j-1]; } } tmp=prev; prev=curr; curr=tmp; memset((void*)curr,0,sizeof(int)*(n+1)); } distance=prev[n]; free(curr); free(prev); return distance; } [/sourcecode]