giovedì 8 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 :-)
 

def quicksort(V):
    l = len(V)
    if l<=1:
        return V

    else:
        #ak = 0
      
        V1 = []
        V2 = []
        Z = []
        
        p = V[l-1]
                 
        for e in V:
            
            if ep:
                V2.append(e)
            else:
                Z.append(e)

        A1 = quicksort(V1)
        A2 = quicksort(V2)
        
        return A1+Z+A2

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!

lunedì 25 luglio 2011

Sono in ferie!

Ragazzi, da un po'di tempo sono in ferie, perciò il blog è un po'morto :(
Appena ritorno a Leuven mi rimetto a scrivere, promesso ;)
Saluti a tutti!

domenica 3 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!


sabato 2 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.