Pagine

08 settembre 2011

Quicksort

Ciao gente,
da quanto tempo! Come state? Io benone :-)
Da qualche giorno ho iniziato a seguire il corso di algoritmi del MIT, molto bello.
Il corso è fruibile sul loro sito su cui sono presenti le videolezioni, le trascrizioni, appunti, ecc...
Ora... Invogliato da questo corso di algoritmi ho deciso di togliermi dalla scarpa un sassolino che avevo sin dai tempi dell'università ovvero capire il misterioso quicksort.
Lo so, sarò una zappa io, però mi ha sempre messo in difficoltà :-/
Comunque l'altra mattina in un momento di calma in ufficio ho deciso di dedicarmici e sono riuscito al primo tentativo :-)
 

Ovviamente questa implementazione è più lenta del sorted() della libreria standard che: a) Non sono sicuro sia un quicksort b) Probabilmente è fatta in C e compilata. In ogni caso è stato un bell'esercizio e comunque è anche molto molto comprensibile come codice :-) Ma come funziona? Se la lunghezza di V è 1 o 0 vuol dire che il vettore è già ordinato. altrimenti: Inizializziamo 3 sottovettori: V1 contiene gli elementi minori del pivot, V2 contiene gli elementi maggiori del pivot e Z contiene l'elemento pivot e quelli a lui uguali. L'elemento pivot è p che ho preso come ultimo elemento della lista. Ora il ciclo for smista gli elementi tra le tre liste e la funzione viene richiamata ricorsivamente sulle sotto liste. Alla fine le 3 liste ordinate vengono concatenate assieme dall'istruzione return A1+Z+A2. Chiaro no? :-) Saluti a tutti!

03 luglio 2011

Una macchina a stati finiti

Buon pomeriggio gioventù,
Ieri sera mi sono imbattuto nell'avventurosa creazione di un automa a stati finiti usando Python. La cosa mi ha messo un po'in difficoltà, soprattutto perché viene difficile non pensare all'automa come ad un circuito ma come un software. In fondo con poche porte logiche e qualche flip flop si fanno anche automi complessi.
In ogni caso, parlandone col mio buon amico e consulente informatico Ennio ne sono venuto a capo :-)
Facciamo un esempio:
Supponiamo di avere un automa fatto da 3 stati:
IDLE, WORK, COMMUNICATION
gli input che uniscono i tre stati sono:
- lavora
- dimmi
- fatto


Fig.1 - Diagramma dell'automa dell'esempio

Partiamo quindi col definire la struttura base di uno stato:

class State:
    def lavora(self):
        return None
    def dimmi(self):
        return None
    def fatto(self):
        return None

Questa classe apparentemente inutile è l'equivalente di una classe astratta di Java.
Le classi che rappresentano gli stati non faranno altro che ereditare i metodi di questa classe in modo da implementare solo quelli che sono realmente necessari.
In pratica ciascuno stato implementerà solo i metodi relativi alle sue transizioni.

class IDLE(State):
    
    def lavora(self):
        return "WORK"
    
class WORK(State):
        
    def dimmi(self):
        return "COMMUNICATE"
    
class COMMUNICATE(State):
        
    def fatto(self):
        return "IDLE"

E fino a qui direi che è tutto chiaro. In pratica i metodi associati ad una transizione restituiscono il nome dello stato successivo, altrimenti restituiscono None.
Implementiamo infine la classe che fa girare l'automa vero e proprio:

class Machine:
    current_state = IDLE()

    def esegui(self,messaggio):
        try:
            s = getattr(self.current_state,messaggio)()
            if s<>None and s == "WORK":
                self.current_state=WORK()
            if s<>None and s == "COMMUNICATE":
                self.current_state=COMMUNICATE()
            if s<>None and s == "IDLE":
                self.current_state=IDLE()
            print(s)
        except:
            print(":-P")

    def current(self):
        if isinstance(self.current_state,IDLE):
            return "IDLE"
        if isinstance(self.current_state,WORK):
            return "WORK"
        if isinstance(self.current_state,COMMUNICATE):
            return "COMMUNICATE"


In pratica come funziona?
Nel momento in cui da istanzio la classe Machine creo l'automa:
m = Machine()
Io stato corrente è IDLE e facendo da riga di comando:
m.current()
A video ci viene stampato "IDLE".
e se voglio cambiare stato?
m.esegui('lavora')
la macchina cambia stato e 
m.current() 
restituirà ora "WORK".
Ma come funziona esegui?
Sfrutta l'introspezione, una caratteristica molto potente di Python.
getattr cerca nell'oggetto referenziato da self.current_state un attributo che si chiama come la stringa passata e se è un metodo lo esegue.
Se il metodo non esiste si genera un'eccezione e viene stampata una linguaccia.
Ora... se il metodo viene eseguito si ha una transizione e l'automa cambia stato,
altrimenti ci prendiamo la nostra linguaccia :-P
Carino vero?
Saluti a tutti!


02 luglio 2011

Gaming can make a better world



Ci tengo a riportare questo talk della mitica Jane McGonigal in cui viene spiegato il potenziale dei gamers (gli appassionati di videogiochi) e come secondo lei questo potenziale potrebbe essere sfruttato per salvare il mondo e renderlo migliore.
Jane McGonigal per chi non lo sapesse è una game designer di fama internazionale,
lavora in questo campo da anni e fa ricerca proprio nel campo di creare giochi educativi
e di rendere positivo il comportamento umano tramite i videogame.
Il suo sito è:
http://janemcgonigal.com
Fateci un salto, vi assicuro che persone come Jane sono veramente da considerare modelli a cui ispirarsi.

28 giugno 2011

Applicazioni web partendo da zero! Parte 2

Ben tornati a tutti!
Oggi parliamo di come fa il web server a comunicare con le applicazioni web. A quanti fosse sfuggito suggerisco di leggere la prima parte prima di questa, dato che contiene la prima parte del discorso!


Common Gateway Interface
Il sistema CGI è il più vecchio in assoluto e forse concettualmente anche il più semplice. In sostanza quando il server riconosce un URL che punta ad un programma invece che ad un documento statico il server esegue il programma e restituisce sotto forma di pagina HTML il risultato del programma lanciato.
Il passaggio di parametri avviene tramite variabili d'ambiente oppure tramite standard input e la risposta del programma viene letta dal server sullo standard output.
Il problema principale di questa tecnologia è che viene avviato un processo per ogni chiamata e questo sistema è lento, soprattutto se il programma in questione è scritto in perl per cui va anche interpretato.
Ma in ogni caso c'è anche un limite al numero massimo di processi che possono essere avviati in memoria e quindi anche la cosiddetta scalabilità ne risente.
La scalabilità è la capacità di un'applicazione di funzionare correttamente e di rispondere in tempi ragionevoli al crescere del numero di utenti. L'ottimo si ha quando un'applicazione risponde sempre bene e sempre in tempi ragionevoli per un numero infinito di utenti, ovviamente ciò non è possibile ma in ogni caso si riescono a gestire parecchi milioni di utenti senza tantissimi problemi con le tecnologie attuali (vedi Facebook).

Fast Common Gateway Interface
La principale differenza tra FastCGI e CGI tradizionale è che FastCGI non crea un processo quando il webserver chiama l'applicazione ma semplicemente i processi risiedono in memoria e vengono interpellati per rispondere alle chiamate. In pratica la gestione delle chiamate diventa un problema di comunicazione tra processi residenti in memoria. La gestione di chiamate multiple può essere fatta sia a livello di webserver (che può inoltrare chiamate ad altri processi uguali se uno è occupato) oppure a livello di processo (un processo può essere "attrezzato" internamente per gestire più chiamate). In pratica ciò che avviene è una combinazione dei due sistemi.
Uno dei grossi vantaggi "velocistici" di FastCGI è che può sfruttare il caching o non chiudere le connessioni ai database per risparmiare tempo nelle chiamate successive.
Un'altro vantaggio è che le applicazioni FastCGI sono indipendenti dal webserver e possono quindi essere riavviate senza arrecare troppi guai al server né subiscono alcuna conseguenza se il server si riavvia perché loro possono rimanere in esecuzione.

Web Server Gateway Interface
Questa tecnologia è specifica delle applicazioni web scritte in python. Questo per fronteggiare il problema delle varie tecnologie implementate dai vari host provider che tipicamente mettono discretamente in crisi il programmatore python limitando di fatto moltissimo le sue scelte.
WSGI è basata sullo standard CGI.
Il middleware WSGI è composto da due lati, uno server e uno applicazione. Il lato server è quello che dialoga direttamente col web server indirizzandone le richieste al lato applicazione e restituendo le risposte ottenute. Il lato applicazione riceve le richieste che vengono indirizzate alle applicazioni e restituisce al lato server le risposte ricevute. In questa maniera è possibile ad esempio indirizzare correttamente le richieste alle applicazioni in memoria in base all'URL e cambiare il contenuto delle variabili d'ambiente di conseguenza, oppure far girare assieme applicazioni diverse nello stesso processo oppure ancora bilanciare il carico per le applicazioni ed eventualmente indirizzare richieste ad(e ovviamente ricevere risposte da) applicazioni remote comunicando tramite rete (a tutto vantaggio della scalabilità!).
Il sistema funziona perché il server o il gateway chiamano per ogni richiesta la funzione preposta a rispondere e che restituisce il risultato cercato.

Java Servlet
Come al solito il mondo Java fa specie a se. In pratica il web server include un application server che al suo interno ha in esecuzione una Java virtual machine. Quando l'URL indirizza una servlet (o una pagina jsp), la servlet riceve la richiesta e i dati che le servono a girare e risponde di conseguenza generando la risposta nel formato adeguato. Le servlet non sono legate a HTTP e possono essere implementate per generare risposte in base a protocolli diversi. Wikipedia ci dice che le servlet sono come applet che invece di girare nel browser girano sul server.
I vantaggi nell'usare le servlet sono molteplici. In primis non c'è bisogno di chiamare un processo per ogni chiamata, semplicemente l'application server lancia un nuovo thread che gestisce la richiesta. Ciò implica che ogni richiesta è gestita da un thread diverso ma che la memoria occupata dall'applicazione è sempre quella (cambia ovviamente la memoria dati). Inoltre le servlet possono girare in un ambiente protetto (detto sandbox) che fa si che possano essere avviate, riavviate e stoppate (oppure limitate in funzionalità) senza interferire con altre applicazioni scritte per altri scopi (vedi il caso di server condivisi che fanno girare più applicazioni web in contemporanea).
Uno dei più famosi application server per Java è Tomcat creato dalla Apache Software Foundation.

E le altre tecnologie?
Ci sono un sacco di altre tecnologie come SCGI, ISAPI, NSAPI, moduli di apache, ecc... che meriterebbero di essere trattate, ma io non mi ritengo sufficientemente competente per farlo. Non le ho studiate e per cominciare mi sono accontentato di capire come funzionano le basi. Alla fine ad esempio i moduli di apache, non sono altro che estensioni del programma server che girano in memoria e richiamano le applicazioni web sul momento riducendo l'overhead di chiamare un interprete (come nel caso di mod_python) o una CGI compilata. Siccome girano "assieme al server" non chiamano processi separati. Però non sono abbastanza competente per descriverle. Ad esempio per chi usa php c'è mod_php che interpreta le pagine/script. Vi consiglio caldamente se avete tempo e voglia di studiarle, magari assieme ad altri ambienti particolari come Google App Engine.

I framework per applicazioni web
Che cosa sono i framework per applicazioni web? Non sono altro che un insieme di librerie e strumenti creati per agevolare lo sviluppo di applicazioni web secondo una ben precisa metodologia.
Un tipico esempio di framework per applicazioni web per Python è Django che racchiude al suo interno un sacco di moduli già pronti come meccanismi per gestire le sessioni e gli utenti, un sistema ORM (object relational mapping), altre librerie varie ed assortite per gestire i contenuti e le interfacce con basi di dati e infine  un meccanismo di templating. Vi consiglio di dare un'occhiata a https://www.djangoproject.com/ per maggiori dettagli. Altri framework molto popolari sono Zend (http://framework.zend.com/) per PHP oppure per Java vanno citati Struts(http://struts.apache.org/) e sicuramente Java Server Faces 

Aspetta un attimo, che diavolo vuol dire ORM?!?!?
Non è una cosa difficile innanzitutto e soprattutto non è quella cosa che si lascia con le scarp XD. ORM sta per Object Relational Mapping. In pratica è un sistema di rappresentazione e di interrogazione per basi di dati che rappresenta le tuple come oggetti e le query come chiamate a metodi di altri oggetti. In pratica mascherano al programmatore la base di dati e soprattutto le tonnellate di SQL che andrebbero scritte per gestirla, riempirla e interrogarla. Due esempi che vanno assolutamente citati sono Hibernate (http://www.hibernate.org/)  per Java e l'ORM di Django per Python.
Ma è proprio necessario usare un ORM? No, dipende sempre dall'applicazione e dal contesto. Ovviamente un'applicazione grande richiede un sacco di lavoro extra se non si fa uso di un ORM e soprattutto il codice SQL non è esattamente il massimo da gestire e manutenere. Inoltre l'ORM maschera anche un eventuale cambio tecnologico alla base di dati (ad esempio si passa da MySQL a Postgres) risparmiando ore di lavoro e fatica da fare sull'applicazione. L'ORM è un layer di disaccoppiamento.

Ma in giro ho letto anche la sigla MVC. Che cos'è?
MVC è un pattern di programmazione che vuol dire Model View Controller. Non si tratta di un rituale magico ma semplicemente di un approccio allo sviluppo di applicazioni web che vengono divise in tre parti distinte:
1) Model = il modello dei dati e la loro rappresentazione nella base di dati
2) View = L'interfaccia utente vera e propria, si tratta proprio della parte che restituisce le risposte al browser e ne raccoglie le richieste.
3) Controller = sta in mezzo tra model e view ed è la logica dell'applicazione ovvero quel pezzo di software che in base alle richieste della parte view, interroga la parte model, rielabora i dati e rispedisce la risposta alla parte view che la restituisce "imbellettata" al browser.
Più avanti faremo degli esempi pratici per chiarire meglio come funziona MVC, state tranquilli!

E ora?
E ora siamo ancora in alto mare :-)
Prima di mettersi a scrivere codice occorrerebbe prendere un po' di dimestichezza con alcune tecnologie di base come HTML.
Il sito principe per studiare tutte le tecnologie relative al web è http://www.html.it
Questo sito è una vera e propria miniera di informazioni sia sulla programmazione sia sulla parte grafica.

La prossima volta cominceremo col vedere un po' di esempi pratici in Python!
Saluti pirateschi a tutti!