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.

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 , dove è il numero di persone nel gruppo e è il numero usato per la conta.

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

Codice C:

#include <stdio .h>
#include <stdlib .h>
#include <sys /time.h>
#include <math .h>

int solve(int,int);
int josephus(int,int);

int main(int argc, char **argv){
    int ITER;
    double DITER;
    int sec, msec, time;
    double mtime,tottime;
    struct timeval start, end;
    register int i,j; 

    ITER = 100000;
    DITER = 100000.0;

    tottime = 0.0;

    for(j=0;j&lt;10;j++){
        gettimeofday(&start,NULL);
        for(i = 0 ; i < ITER ; i++)
            josephus(40,3);

        gettimeofday(&end,NULL);

        msec = end.tv_usec - start.tv_usec;
        sec = end.tv_sec - start.tv_sec;
        time = sec * 1000000 + msec;

        mtime = time/DITER;
        tottime += mtime;

    }

    fprintf(stdout,"Mean time per iteration= %f microseconds\n\r", tottime/10);
    return 0;
}

int solve(int n, int q){
    int jn = 0;

    register int i;

    for(i=1; i<=n; i++)
        jn = (jn + q - 1) % i + 1;

    return jn;
}

int josephus(int n, int q){
    int t;
    if(n <= q) return solve(q,q);
    else{
        int jn = josephus(((int) (n - floor(n/q))),q);

        if(jn <= (n%q))
            return jn + ((int) (floor(n/q)) * q);
        else{
            jn -= n % q;

            t = ((int) (floor(jn/(q-1))) * q);

            return !(jn%(q-1)) ? t-1 : t+jn%(q-1);
        }
    }
}

Codice C++:

#include <iostream>
#include <cmath>
#include <sys /time.h>

using std::cout;
using std::endl;

int solve(int,int);
int josephus(int,int);

int main(int argc, char **argv){
    int ITER;
    double DITER;
    int sec, msec, time;
    double mtime,tottime;
    struct timeval start, end;

    ITER = 100000;
    DITER = 100000.0;

    tottime = 0.0;

    for(int j=0;j&lt;10;j++){
        gettimeofday(&start,NULL);
        for(int i = 0 ; i < ITER ; i++)
            josephus(40,3);

        gettimeofday(&end,NULL);

        msec = end.tv_usec - start.tv_usec;
        sec = end.tv_sec - start.tv_sec;
        time = sec * 1000000 + msec;

        mtime = time/DITER;
        tottime += mtime;

    }

    cout << "Mean time per iteration = " << tottime/10 <<" microseconds" << endl;
    return 0;
}

inline int solve(int n, int q){
    int jn = 0;

    register int i;

    for(i=1; i<=n; i++)
        jn = (jn + q - 1) % i + 1;

    return jn;
}

inline int josephus(int n, int q){
    int t;
    if(n <= q) return solve(q,q);
    else{
        int jn = josephus(((int) (n - floor(n/q))),q);

        if(jn <= (n%q))
            return jn + ((int) (floor(n/q)) * q);
        else{
            jn -= n % q;

            t = ((int) (floor(jn/(q-1))) * q);

            return !(jn%(q-1)) ? t-1 : t+jn%(q-1);
        }
    }
}

Codice  C#:

using System;

class MainClass{
    public static void Main(string[] args){
        double tottime=0.0;

        for(int j=0;j<10;j++){
            DateTime start = DateTime.Now;
            for(int i=0;i<100000;i++)
                josephus(40,3);

            TimeSpan elapsed = DateTime.Now - start;

            double time = (elapsed.TotalMilliseconds * 1000.0)/100000.0;
            tottime+=time;
        }

        Console.WriteLine("Time per iteration: {0} microseconds" ,tottime/10.0);

    }

    public static int solve(int n, int q){
        int jn = 0;

        for(int i=1;i<=n;i++)
            jn = (jn + q -1) % i +1;

        return jn;
    }

    public static int josephus(int n, int q){
        if(n<=q)
            return solve(q,q);
        else{
            int jn = josephus(n - ((int) Math.Floor(((double) n)/q)) ,q);

            if(jn <= (n%q))
                return jn + (int) (Math.Floor(((double) n)/q) * q);
            else{
                jn -= n%q;

                int t = (int) (Math.Floor(((double) jn)/(q-1)) * q);

                if(jn % (q-1) == 0)
                    return t-1;
                else
                    return t + jn % (q-1);
            }

        }
    }
}

Codice Java:

public class jjos {
    public static void main(String[] args) throws Exception {
        int iter = 100000;
        double tottime=0.0;

        for(int j=0;j<10;j++){
            long start = System.nanoTime();
            for (int i = 0; i < iter; i++)
                josephus(40, 3);

            long end = System.nanoTime();

            double time = (end - start)/1000.0;
            double mtime = time/100000.0;

            tottime+=mtime;
        }

        System.out.println("Mean time per iteration = " + tottime/10.0
                + " microseconds.");
    }

    public static int josephus(int n, int q) {
        int jn;
        if (n <= q)
            return solve(q, q);
        else {
            jn = josephus(n - (int) Math.round(Math.floor(n / q)), q);

            if (jn <= (n % q)) {

                return jn + (int) (Math.round(Math.floor(n / q)) * q);
            } else {

                jn = jn - (n % q);

                int t = (int) (Math.round(Math.floor(jn / (q - 1))) * q);

                if (jn % (q - 1) == 0)
                    return t - 1;
                else
                    return t + jn % (q - 1);
            }
        }

    }

    public static int solve(int n, int q) {
        int jn = 0;

        for (int i = 1; i <= n; i++)
            jn = (jn + q - 1) % i + 1;

        return jn;
    }
}

Codice Python (con Psyco):

#!/usr/bin/python

import time
import sys
import math
import psyco

def solve(n,q):
    jn = 0
    for i in xrange(1,n+1):
        jn = (jn +q -1) % i +1

    return jn

def josephus(n,q):
    if n <= q: return solve(q,q)
    else:
        jn = josephus(n-int(math.floor(n/q)),q)

        if jn <= (n % q):
            return jn + int(math.floor(n/q) * q)
        else:
            jn -= n % q

            t = int(math.floor(jn/(q - 1)) * q)

            if not jn % (q - 1):
                return t-1
            else:
                return t + jn % (q - 1)

if __name__ == "__main__":

    psyco.full()

    k = 100000

    tottime = 0.0

    for i in xrange(10):
        start = time.time()

        for i in xrange(k):
            josephus(40,3)

        end = time.time()

        tottime += ((end - start) * 1000000 )/ k

    print 'Mean time per iteration = %s microseconds ' % (tottime / 10.0)

Codice Ruby:

#!/usr/bin/ruby -w

def solve(n,q)
    jn = 0

    for i in 1..n
        jn = (jn + q - 1) % i + 1
    end

    jn

end

def josephus(n,q)
    if n <= q
        solve(q,q)
    else
        jn = josephus(n-(n/q).floor,q)

        if jn <= (n % q)
            jn + (n/q).floor * q
        else
            jn -= n % q

            t = (jn/(q-1)).floor * q

            if jn % (q-1) == 0
                t-1
            else
                t + jn % (q-1)
            end
        end

    end

end

ITER = 100000

tottime = 0.0

10.times{
    start = Time.now
    ITER.times{
        josephus(40,3)
    }
    ends=Time.now

    tottime += ((ends - start) * 1000000) / ITER
}

puts 'Mean time per iteration = ' + (tottime / 10).to_s() + ' microseconds'

Ho completamente riscritto in Python registerimage, la mia applicazioncina per registrare le immagini virtuali preconfezionate del progetto VirtualBox Images.

Ho deciso di usare Python per vari motivi:

• per imparare un nuovo linguaggio;
• per aumentare la portabilità;
• per realizzare un’applicazione self-contained;

Questa nuova versione di registerimage non usa alcuna libreria esterna, ma solo moduli nativi della Python Standard Library; non uso più la libxml2 per fare il parsing dei file .xml, ma uso il modulo built-in xml.dom.minidom.

Ho semplificato pure l’interfaccia del programma; questa nuova versione prende sempre due argomenti in input dalla riga di comando:

1. il path del file .xml di configurazione della macchina virtuale scaricata dal nostro progetto;
2. il path del file .vdi della macchina virtuale;

L’utente non avrà più la necessità di spostare a mano i file .xml e .vid: ci pensa il mio programma a farlo.

Per usare la nuova versione di registerimage avrete bisongno di un interprete Python (versione >= 2.5); potete scaricare quello per Windows cliccando qui. Nei sistemi GNU/Linux e Mac OS X spesso Python è già preinstallato.

Prima di lasciarvi, devo fare un altro piccolo appunto per gli utenti Window: per usare l’interprete Python dalla riga di comando occorre che modifichiate la variabile d’ambiente PATH in modo che contenga il path dove avete installato l’interprete. A chi non sapesse come modificare tale variabile, consiglio di leggere questa guida.
Nell’immagine seguente trovate uno screenshot di come dovreste settare la variabile PATH

Ecco uno screenshot che mostra come ho usato registerimage per registrare l’immagine del sistema MINIX 3.1.2

Potete scaricare lo script cliccando qui.

Una delle canzoni più apocalittiche dei “The cure” e una delle mie preferite:

In questi giorni ho contribuito ad aumentare la temperatura della mia stanza facendo lavorare come un matto il mio povero computer.

Mi sono ritrovato con una wordlist da 700MB con più di 75 milioni di parole; mi sono accorto che era piena di ripetizioni: la sola lettera “a” compariva 59 volte!

Mi sono ingegnato per risolvere il problema.

Occorreva innanzitutto ordinare la wordlist.

Per fare questo ho pensato di usare il comando sort dei sistemi Unix. Purtroppo il file gigante è codificato in unicode e sort si incazza un poco.

Per risolvere il problema ho reimpostato la variabile LC_ALL in questo modo:

export LC_ALL=C; sort wordlist.txt > sortedwordlist.txt


Dopo un poco di elaborazione, mi sono ritrovato con un bel file ordinato.

Occorreva eliminare le ripetizioni. Per fare questo ho implementato un piccolo script Python.
Ecco il codice:

#!/usr/bin/python

from __future__ import with_statement
import sys

with open(sys.argv[1],'w' ) as fileoutput:
	with open(sys.argv[2],'r' ) as fileinput:

		oldline=''

		for line in fileinput:

			if line!=oldline:
				fileoutput.write(line)

			oldline=line

Il primo argomento dello script è il file di output, il secondo è il file di input.

Dopo un poco di elaborazione, mi sono ritrovato una bella wordlist di 441 MB, 260MB in meno di quella di partenza; nella wordlist iniziale c’erano circa 35 milioni di ripetizioni!

In questi giorni ho avuro l’esigenza di redigere il mio CV per mandarlo ad alcune aziende che me ne hanno fatto richiesta. L’idea di usare i modelli di MS Word non mi andava affatto e pertanto mi sono affiadato al mio “amico” (adoro scrivere e non LaTeX!!!!!!).

Mi sono messo a spulciare su ctan.org e ho trovato quello che cercavo: la classe europecv, un’implementazione non ufficiale del formato europeo del CV.

Potete scarica il pacchetto qui.

Come al solito, ogni pacchetto contiene una buona dose di esempi e documentazione; se si ha una buona dimenstichezza con , è molto semplice scrivere immediatamente un documento completo.

Questa è l’intestazione del mio sorgente:

\documentclass[totpages,helvetica,nologo,flagCMYK,italian]
{europecv}
\usepackage[T1]{fontenc}
\usepackage{graphicx}
\usepackage[a4paper,top=1.27cm,left=1cm,right=1cm,bottom=2cm]
{geometry}
\usepackage[italian]{babel}
\usepackage{url}


Per maggiori informazioni sulle varie opzioni, leggete la documentazione.

Vediamo alcuni comandi importanti.

\ecvname{Sanfilippo Calogero}
\ecvaddress{Via Pippo Pappo 26}
\ecvtelephone[555-555]{555-555}
\ecvemail{\url{a@b.c}}
\ecvnationality{Italiana}
\ecvdateofbirth{17/6/1985}
\ecvgender{Maschile}

I nomi sono molto autoesplicativi: \ecvname{} serve per impostare il nome, \ecvaddress{} per impostare l’indirizzo, \ecvtelephone[555-555]{555-555} per impostare il numero di telefono (tra parentesi quadre va il cellulare), \ecvemail{\url{a@b.c}} imposta l’email, ecc…

Per fare comparire nel CV tutte queste info, basta inserire il codice:

\ecvpersonalinfo


all’interno del corpo del documento, in questo modo:

\begin{document}
\begin{europecv}
\ecvpersonalinfo
\end{europecv}
\end{document}


Il pacchetto prevede dei tag per impostare le varie sezioni in cui suddividere il curriculum; questo è il codice relativo alla sezione Istruzione e formazione:

\ecvsection{Istruzione e formazione}
\ecvitem{Date}{Iniziare con le informazioni pi\’u recenti ed elencare separatamente ciascun corso frequentato con successo. Facoltativo.}
\ecvitem{Certificato o diploma ottenuto}{\ldots}
\ecvitem{Principali materie/Competenze professionali apprese}{\ldots}
\ecvitem{Nome e tipo d’istituto di istruzione o formazione}{\ldots}
\ecvitem{Livello nella classificazione nazionale o internazionale\footnote{Se pertinente.}}{\ldots}


Da questo link potete scaricare un esempio di curriculum generico prodotto col pacchetto europecv. Cliccando qui potrete scarica il sorgente relativo al precedente esempio.

Buon divertimento!

The end

Questa è la settimana “calda”, l’ultima prima delle elezioni di giorno 15 e 16 giugno.

Sul blog del gruppo LiberaMente trovate i programmi dei 3 candidati a sindaco.

Scaricateli, leggeteli e ………………… meditate!

La scelta del sindaco deve esser attenta e ponderata; è un momento di altissima democrazia da non sottovalutare e nemmeno da banalizzare.

Noi siamo cittadini in quanto detentori del diritto al voto!

Potete trovare i file qui.

Mi capita spesso di dover mandare la stessa email a tutte le persone del gruppo LiberaMente, di cui faccio parte.

Per automatizzare la cosa, ho creato un piccolo script AppleScript.

Ecco il sorgente:

set date_dialog to display dialog "Inserisci l'oggetto" default answer ""
set the_subject to text returned of date_dialog

tell application "Address Book"
    set name_list to every person of group "Liberamente"

    set email_value_list to {}

    repeat with p in name_list

        set end of email_value_list to value of every email of p

    end repeat

end tell

tell application "Mail"
    activate

    set new_message to make new outgoing message with properties {subject:the_subject, visible:true}

    tell new_message
        repeat with i from 1 to (count email_value_list)

            repeat with j from 1 to (count item i of email_value_list)
                make new to recipient with properties {address:item j of item i of email_value_list}
            end repeat

        end repeat

    end tell

end tell

Vediamo in breve come funziona.

Il primi due righi di codice
set date_dialog to display dialog "Inserisci l'oggetto" default answer ""
set the_subject to text returned of date_dialog
fanno comparire una finestra di dialogo che permette all’utente di inserire l’oggetto della mail.

Il blocco di codice

tell application "Address Book"
	set name_list to every person of group "Liberamente"

	set email_value_list to {}

	repeat with p in name_list

		set end of email_value_list to value of every email of p

	end repeat

end tell

estrae dalla Rubrica Indirizzi tutti i membri del gruppo “Liberamente” e li memorizza nella variabile name_list.
Il successivo ciclo repeat estrae le email di tutti i membri del gruppo e li aggiunge alla lista email_value_list.

Il successivo blocco tell dice a Mail di creare un nuovo messaggio di posta avente come oggetto quello inserito dall’utente:
set new_message to make new outgoing message with properties {subject:the_subject, visible:true}.

Il successivo blocco tell serve per inizializzare la lista dei destinatari con tutte le email contenute in email_value_list.

In questi giorni mi sono “immerso” nello studio del Python, un interessante linguaggio di scripting che mi ero promesso di imparare data la sua crescente diffusione nel mondo del software open (e non).

La rete mi ha aiutato tantissimo: su Internet trovate tonnellate di documentazione, a partire dal sito ufficiale del linguaggio.

Come prima prova con Python, ho provato ad implementare registerimage-1.0.2, il software che ho scritto per automatizzare la registrazione delle immagini virtuali del progetto VirtualBox Images con il software VirtualBox della SUN.

La cosa che colpisce del Python è la semplicità enorme di codificazione; abituato a certe “astrusità” del C, programmare in Python è molto semplice e scorrevole.

Ecco un piccolo confronto tra l’implementazione in C di una funzione di registerimage-1.0.2 e quella in Python.

La funzione in questione effettua un parsing del file di configurazione della macchina virtuale che si vuole registrare per ottenere i parametri salienti della macchina virtuale stessa.

Versione C:

vm_parameters* get_machine_parameters(char *docname) {
    printf("%s\ndocname: %s\n",__FUNCTION__,docname);
    vm_parameters *param;

    xmlDocPtr doc;
    xmlNodePtr cur, cur2,cur3;

    param=new_vm_parameters();

    doc = xmlParseFile(docname);

    if (!doc) {
        fprintf(stderr,"Document not parsed successfully. \n");
        return NULL;
    }

    cur = xmlDocGetRootElement(doc);

    if (!cur) {
        fprintf(stderr,"empty document\n");
        xmlFreeDoc(doc);
        return NULL;
    }

    if (xmlStrcmp(cur->name, BAD_CAST "VirtualBox")) {
        fprintf(stderr,"document of the wrong type");
        xmlFreeDoc(doc);
        return NULL;
    }

    cur = cur->xmlChildrenNode;

    while (cur) {

        if (!xmlStrcmp(cur->name, BAD_CAST "Machine")){
            param->machine_uuid=xmlStrdup(xmlGetProp(cur, BAD_CAST "uuid"));
            param->machine_name=xmlStrdup(xmlGetProp(cur, BAD_CAST "name"));

            //printf("uuid=%s\n",param->machine_uuid);
            //printf("machine name=%s\n",param->machine_name);

            cur2=cur->xmlChildrenNode;

            while(cur2){
                if (!xmlStrcmp(cur2->name, BAD_CAST "HardDiskAttachments")){

                    cur3=cur2->xmlChildrenNode;

                    while(cur3){
                        if (!xmlStrcmp(cur3->name, BAD_CAST "HardDiskAttachment"))
                            param->hd_id=xmlStrdup(xmlGetProp(cur3,BAD_CAST "hardDisk"));

                            //printf("hardDisk=%s\n",param->hd_id);

                        cur3 = cur3->next;
                    }

                }
                cur2 = cur2->next;
            }

        }

        cur = cur->next;
    }

    xmlFreeDoc(doc);

    return param;
}

Versione Python:

def getMachineParameters(docname):
    try:
        param = MachineParameters()
        xmldoc = minidom.parse(docname)

        root = xmldoc.documentElement

        if root.nodeName == "VirtualBox":
            machineNode = root.childNodes[1]

            param["uuid"] = machineNode.getAttribute("uuid" )
            param["name"] = machineNode.getAttribute("name" )

            machineNodeChildrens = machineNode.childNodes

            for i in machineNodeChildrens:
                if i.nodeName == "HardDiskAttachments":
                    for j in i.childNodes:
                        if j.nodeName == "HardDiskAttachment":
                            param["hdid"] = j.getAttribute("hardDisk" )

                            return param

        else:
            print "Document of the wrong type"
            return None

    except IOError:
        print "Error parsing ", docname
        return None

La versione C della funzione usa la libxml2, mentre quella Python usa il modulo xml.dom.minidom.