pattern discovery in python con Apriori Method

Parlerò in questo post di uno script python per effettuare la pattern discovery: voglio cioè estrarre i pattern più frequenti da una lista di transazioni.

Lo script utilizza l'”Apriori Method” come algoritmo per la determinazione dei Frequent Pattern e al momento non si occupa della determinazione delle “association rules”.

L'”apriori method” è uno dei più semplici algoritmi non Brute Force per la Pattern Discovery e si basa sulla considerazione che se una data sequenza ha una certa frequenza nelle transazioni, tutte le sue sottosequenza devono avere una frequenza uguale o periore. E’ quindi possibile partire dalla sequenza più corte, selezionare quelle frequenti secondo una soglia predeterminata e costruire le sequenze più lunghe a partire da quelle selezionate in precedenza.

L’algoritmo è quindi costituito da un ciclo di due step che continua fino a che è possibile generare potenziali sequenze frequenti. Gli step sono

  1. generazione della lista di potenziali sequenze a partire dalla combinazione delle sequenze prodotte dal ciclo precedente
  2. puliza (pruning) della lista basata sul calcolo dell’effettiva frequenza.

Lo script ricalca questa metologia e presenta un ciclo e due funzioni.

Iniziamo quindi ad esaminare lo script:

from pprint import pprint

debug = False;
file = 'elenco.txt';
sep= ',';
minSup = 0.07;

a = open(file, 'r')
itemList = a.readlines()
a.close()

# used sorted for simplicity, so that same 2 items but in different order
# won't be added to 2-itemsets (i.e. Beer,Diaper and Diaper,Beed)
itemList = [sorted(item.rstrip('\n').split(sep)) for item in itemList]

Lo script legge i dati da un file denominato elenco.txt in cui ogni riga rappresenta una transazione e contiene una lista separata da virgole di elementi. Ad es:

farina,uova,latte,banana,patata,biscotto,cioccolatino
farina,uova,latte,biscotto,tavolino,cioccolatino
farina,uova,latte,patata,carne,cavolfiore

I dati sono inseriti, ordinati, in una lista di liste per le successive elaborazioni.

Prima di entrare nel ciclo vero e proprio eseguo separatamente i due step per il primo run; questo è infatti anomalo perché la lista di elementi da esaminare viene generata in modo speciale: si prendono tutte le sequenze di lunghezza uno non essendoci una sequenza precedente da cui partire.

elementList = generateNextItemsetList( [], itemList );

frequencies = FrequentElements( elementList, itemList , minSup );
pprint( frequencies );

Le due due funzioni che qui compaiono corrispondono esattamente ai due step dell’algoritmo:

generateNextItemsetList()

        : genera la lista di elementi da esaminare

FrequentElements( elementList, itemList , minSup )

      : verifica la frequenza degli elementi della lista

La prima funzione restituisce una lista di liste ognuna contenente una data sequenza

[
 ['latte', 'uova'],
 ['farina', 'latte'],
 ['codetta', 'farina']
]

mentre la seconda un dizionario che ha per chiave una stringa costruita con gli elementi della sequenza e per valore una lista con le frequenze assoluta e relativa della sequenza stessa

{
 'banana,biscotto': [2, 0.08333333333333333],
 'biscotto,cioccolatino': [2, 0.08333333333333333],
 'biscotto,farina': [3, 0.125]
}

Questa parte si conclude con la stampa della frequenza degli elementi interessanti. Per la stampa ho utilizzato la funzione pprint che restituisce un output un poco più leggibile per liste e dizionari.

Inizia poi il ciclo vero e proprio che non fa nulla di realmente differente:

while ( True ):
    elementList = [];
    for a in frequencies.keys():
        elementList.append( a.split(',') );
    if debug : print ( elementList );

    elementList = generateNextItemsetList( elementList, itemList, debug );
    if debug : print ( elementList );

    frequencies = FrequentElements( elementList, itemList , minSup );
    pprint( frequencies );
 
    if len( frequencies ) == 0:
        break;

Per prima cosa costruisco la lista degli elementi a partire dalle chiavi del dizionario generato nel ciclo precedente, genero poi la nuova lista di elementi da esaminare ed esamino infine la nuova lista.

Come accennato nella premessa, se la lista generata è vuota il ciclo is interrompe.

Esaminiamo ora in maggior dettaglio le due funzioni iniziando da def generateNextItemsetList( previousList = [], transactions = [] , debug = False ).

def generateNextItemsetList( previousList = [], transactions = [] , debug = False ):
    """ This function generates (k+1)-itemset candidates starting from k-itemset
        if the previousList is empty the function generates the 1-itemset
        The function requires a sorted list as input and generate a sorted list for a new call of this function
    """
    if debug: print( previousList );
    k = len(previousList);
    elements = [];
    # if the list is empty i generate all the possible 1-itemset
    if ( k == 0 ):
        for transaction in transactions:
            for element in transaction:
               try:
                   elements.index( [element] );
                   break;
               except:
                   elements.append( [element] );
    # if the itemset is not empty join as for apriori
    # yes else is part of the for cicle
    else:
        count = 0;
        for i in range( 0, k ):
            for j in range ( 0, i ):
                if (i != j):
                    for l in range ( 0, len(previousList[i])-1 ):
                        if ( previousList[i][l] != previousList[j][l] ):
                            break;
                    else:
                        elements.append( [] );
                        if debug : print( elements[count] );
                        if debug : print( previousList[i][0] );
                        for l in range ( 0, len(previousList[i])-1 ):
                            elements[count].append( previousList[i][l] );
                        elements[count].append( previousList[i][len(previousList[i])-1] );
                        elements[count].append( previousList[j][len(previousList[j])-1] );
                        elements[count] = sorted( elements[count] ); 
                        if debug : print( elements[count] );
                        count += 1;

    if debug : print( sorted(elements) );
    return sorted(elements);

Come già detto, questa funzione si occupa di generare la lista degli elementi che è utile esaminare. Lo fa in due modi differenti: se la lista delle sequenze del ciclo precedente è vuota, esamina la lista delle transazioni ed estrae tutti gli elementi singoli. Altrimenti accoppia tutte le sequenze che differiscono per un solo elemento e genera la sequenza che contiene l’unione degli elementi di queste due sottosequenze.

Ho usato qui il costrutto for … else…: in questo modo i comandi nel blocco dell’else vengono eseguiti se il ciclo for non viene interrotto. Ovvero solo se i primi n-1 elemnti sono uguali costruisco la stringa di lunghezza n+1.

La seconda funzione è def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ).

def FrequentElements( elements = [], transactions = [], minSup = 0.5, debug = False ):
    """ This function get as input the list of the element to be tested, the list of transactions and the values of minimun support.
        The function returns a dictionary that has as keys the frequent elements and values a list with the count and the support
    """
    frequencies = {};
    allFrequencies = {};
    label = '';
    numTransactions = len(transactions);

    # calculate frequencies
    for element in elements:
        if isinstance( element, str ):
            for transaction in transactions:
                try:
                    allFrequencies[ element ] += transaction.count( element );
                except:
                    allFrequencies[ element ] = transaction.count( element );
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            for transaction in transactions:
                flag = 0;
                for field in element:
                    if ( transaction.count( field ) == 0 ):
                        flag -= 1;
                        break;

                if flag >= 0:
                    try:
                        allFrequencies[ label ] += 1;
                    except:
                        allFrequencies[ label ] = 1;

    # purging dictionary
    for element in elements:
        if isinstance( element, str ):
            if allFrequencies[ element ] / numTransactions >= minSup:
                frequencies[ element ] = [ allFrequencies[ element ], allFrequencies[ element ] / numTransactions ];
        else:
            label = '';
            for a in element:
                label += ','+a;

            label=label.lstrip(',');

            if label in allFrequencies and allFrequencies[ label ] / numTransactions >= minSup:
                frequencies[ label ] = [ allFrequencies[ label ], allFrequencies[ label ] / numTransactions ];

    return frequencies;

In questa funzione ci sono due parti: per prima cosa vengono contate le occorrenze delle sequenze in esame e come secondo step vengono selezionate le sequenze sufficientemente frequenti.

In entrambi gli step vengono considerati due casi: un primo passaggio in cui l’elemento della lista è una stringa ed i cicli successivi in cui l’elemento della lista esterna è anch’esso una lista.

E’ interessante notare che la frequenza viene determinata confrontando ogni elemento della lista di sequenze con ogni elemento della lista delle transazioni. Io ho eseguito i cicli in questo ordine: nel caso la lista delle transazioni fosse stata così grande da non poter essere mantenuta in memoria sarebbe stato conveniente invertire i due cicli in modo da dover leggere le transazioni da disco una volta sola (per una data lunghezza delle sequenze). In altre parole sarebbe convenuto prendere una transazione alla volta e incrementare dei contatori associati alle sequenze presenti.

Questa considerazione mette in evidenza uno dei limiti più importanti dell’ apriori method: richiede inevitabilmente molti “sequential scan” della lista delle transazioni: operazione che può essere molto costosa nel caso sia necessario mantenere la lista su disco.

Altro limite importante che deriva dall’effettuare la Pattern Discovery con l’Apriori Method è che la lista delle sequenze da esaminare, può essere, in determinate condizioni, estremamente lunga. Si pensi ad esempio al caso in cui esistono sequenze interessanti di centinaia o migliaia di elementi: ogni sottosequenza è potenzialmente interessante e il numero di sottosequenze non ordinate di una sequnza di lunghezza m è (2^m-1); un numero che diventa presto enorme.

Il codice di questo script può essere recuperato all’indirizzo https://github.com/grimli/pattern_discovery.

python e automi cellulari – griffeath circular cellular automata

Vediamo qui un esempio diverso di automa cellulare: L’automa circolare di Griffeath.

Il sitema è analogo a quello di life trattato qui e qui. Abbiamo una tabella costituita da punti di una mappa ognuno con un suo stato, un tempo di evoluzione costituito da istanti discreti e delle regole che determinano lo stato successivo di ogni punto sulla base degli stati dei vicini.

Il sistema rimane quindi definito da:

  • una matrice di punti ad ognuno dei quali deve essere associato uno stato individuato da un intero. Utilizzaremo una lista di liste il cui valore corrisponde allo stato. 10 stati possibili  è un volore ragionevole per questo sistema e lo utilizzerò nell’esempio. Il programma sarà comunque facilmente modificabile per gestire un numero di stati differenti
  • una regola di evoluzione: un punto mangia tutti i vicini nello stato immediatamente inferiore. Se avessi 4 stati il 3 mangia il 2, il 2 mangia l’1, l’1 mangia lo 0 e lo 0 mangia il 3. Se una casella viene mangiata nell’istante successivo assumerà lo stato della casella da cui è stata mangiata.
    Ogni elemento può mangiare ed essere mangiato nello stesso step
    In questo sistema per vicini si intendono le sole 4 caselle che condividono un lato.

Questo sistema, più ricco di quello del gioco life ha un comportamento molto diverso: passa sempre attraverso tre fasi:

  • una prima fase con una distribuzione casuale di punti
  • una fase in cui si formano delle grandi macchie
  • la comparsa di spirali che crescono fino a riempire completamente il sistema.

Per realizzare questo automa cellulare ho ripreso la classe del precedente adattando i metodi al nuovo sistema. Il codice completo è disponibile a questo indirizzo.

Come per il sistema life, non ho fatto un gramde sforzo per ottimizzare il metodo che calcola l’evoluzione del sistema dato che il grosso del tempo viene speso per rappresentarlo graficamente. Vorrei comunque in futuro almeno sfruttare i thread per suddividere il calcolo tra più CPU e magari trovare un metodo migliore per rappresentare il risultato.

L’automa cellulare è basata su una classe che mostra tre metodi: il cosrtruttore, una funzione per farlo evolvere e una funzione per rappresentarlo graficamente.

Il costruttore fa proprio quello che ci si aspetterebbe da un costruttore: definisce le strutture dati che costituiscono l’oggetto e gli assegna dei valori iniziali:

class CellularAutoma:
   def __init__(self, lenght=500, scale=1, levels=10):
      """genera la tabella iniziale quadrata e di dimensione iniziale lenght""
      self.board = [[]]
      self.pantone = []
      self.scale = scale
      self.levels = levels
      self.time = 0
      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

      #inizializzo ambiente grafico 
      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

self.board è una lista di liste che conterrà lo stato corrente del sistema
self.pantone conterrà una tavolozza di colori necessaria per la rappresentazione grafica del sistema
scales e levels sono rispettivamente la dimensione del punto nella rappresentazione grafica e il numero di stati che può assumere un elemento del sistema.

Per scales, e per altri valori ho cambiato i valori di default rispetto all’esempio precedente per ottenere un effetto grafico più adatto a questo sistema.

self.time è un contatore che conta il numero di step di evoluzione che ha subito l’oggetto. Verrà mostrato su consolle al completamento di ogni step di evoluzione: questo rende evidente che il grosso del tempo viene speso a generare la rappresentazione grafica per inciso.

Segue un blocco di codice che assegna ad ogni elemento del sistema un valore iniziale casuale

      line = []
      random.seed()

      for a in range( lenght ):
         line = []
         for b in range( lenght ):
             line.append( random.randint( 0, self.levels-1 ))
         self.board.append( line )

      self.board.remove([])

è abbastanza semplice e non mi dilunog a spiegarlo.

Inizializzo poi l’ambiente tkinter

      self.master = Tk()
      self.master.title('Griffeath circular cellular automata')
      self.w = Canvas(self.master, width=lenght*self.scale, height=lenght*self.scale)
      self.w.pack()

come si vede creo una finestra con dentro un widget canvas su cui andrò poi a disegnare la rappresentazione grafica del sistema

Il metodo si conclude con la generazione della tavolozza di colori:

      #generate pantone
      for a in range( self.levels ):
         self.pantone.append( "#"+str(random.randint( 100000,999999 )))

Ho optato per una selezione casuale dei colori che mi ha permesso di mantenere il numero di stati un semplice parametro numerico. C’è ovviamente il rischio che due stati vengano rappresentati con lo stesso colore ma direi che è abbastanza remoto.

Il secondo metodo della classe è evolve()

   def evolve( self ):
      """esegue lo step di evoluzione del gioco life su una tabella sferica"""
      rows = len(self.board)
      columns = len(self.board[0])
      board2 = [[0 for j in range(rows)] for i in range(columns)]


      for i in range( 0, rows ):
         for j in range( 0, columns ):
            if (self.board[(i-1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j-1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[i%(rows)][(j+1)%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            elif (self.board[(i+1)%(rows)][j%(columns)]-1)%self.levels  == self.board[i][j]:
               board2[i][j] = (self.board[i][j]+1)%self.levels
            else:
               board2[i][j] = self.board[i][j]

      self.board = board2
      print("time: %d" %self.time )
      self.time = self.time+1

dopo alcune definizioni iniziali di variabili che verranno sfruttate nel metodo si inizia l’esame di tutti i punti del sistema. Ogni punto viene confrontato con i vicini e se il suo stato è quello immediatamente inferiore a quello di uno dei 4 vicini viene salvato nel punto corrispondente della tabella temporanea il suo valore incrementato di uno. Altrimenti viene salvato il suo valore.
L’operatore modulo viene sfruttato qui per gestire la circolarità del sistema, sia geometrica sia sugli stati.

A esame concluso lo stato attuale viene scambiato con quello calcolato, viene stampato in consolle il numero dello step e incrementato il tempo di uno.

L’ultimo metodo su cui è stato necessario intervenire è il metodo show().

Quì era necessario un sistema più generale che permettesse di rappresentare un numero arbitrario di stati. Ne è risultata, come a volte accade, una funzione anche più semplice di quella usata negli articoli precedenti:

   def show( self ):
      """Gives a graphical representation of the data"""
      self.w.delete(ALL)
      for i,v in enumerate(self.board):
         for j,w in enumerate( self.board[i] ):
               self.w.create_rectangle(i*self.scale, j*self.scale, i*self.scale+self.scale, j*self.scale+self.scale, fill=self.pantone[self.board[i][j]], outline=self.pantone[self.board[i][j]] )

Dato che questo sistema è più gradevole alla vista se costituito da tabelle grandi e punti piccoli, ho sfruttato il parametro outline per evitare il bordino nero del rettangolo che rappresenta il punto che in questo caso era di dimensioni confrontabili con il punto stesso e, quindi, piuttosto fastidioso.

tkinter, python e automi cellulari – life

lifeRiprendiamo l’esempio del gioco life, già visto in un precedente articolo, per esaminare l’utilizzo della libreria tkinter del python. Questa libreria permette l’utilizzo della GUI in questo linguaggio.

Il codice integrale di questo esempio è disponibile a questo indirizzo; riporto qui solo gli stralci relativi alla libreria tkinter.

Il corpo principale del programma inizia ovviamente importando i moduli necessari:

import random
from tkinter import *

random per la generazione casuale della configurazione iniziale e tkinter per la GUI.

Viene poi richiesta la dimensione della tabella che si vuole gestire e, a seguire, creato un oggetto CellularAutoma.

dim = input( "Inserisci la dimensione della board: ")
board = CellularAutoma( int(dim) )

CellularAutoma è la classe su cui si basa tutto l’applicativo e, oltre a contenere una tabella (lista di liste per la precisione) con i dati dell’ultimo stato del sistema definisce i metodi per rappresentarlo graficamente (show) e calcolare lo stato successivo (evolve).

board.show()

while True:
   board.evolve( )
   board.show()
   board.master.update()

Il programma, come si vede, contiene poco più che chiamate a questi metodi; infatti, dopo lo show della configurazione iniziale, entra in un loop nel quale viene calcolato lo stato successivo, viene mostrato a video lo stato e si utilizza la funzione update della libreria per permettere al ciclo di procedere e non rimanere bloccato nei loop degli eventi dell’interfaccia grafica.

Passiamo ora ad esaminare la classe: non entreremo nel dettaglio di tutti i metodi, come detto, perché alcuni di questi non hanno differenze rilevanti dalle funzioni esaminate nel precedente articolo sul gioco life.

La struttura della classe è:

class CellularAutoma:
   def __init__(self, lenght=6):
      """genera la tabella iniziale quadrata e di dimensione iniziale lenght"""
      self.board = [[]]
 
   def evolve( self ):
      """esegue lo step di evoluzione del gioco life su una tabella sferica"""
 
   def show( self ):
      """Gives a representation of the data"""

Esaminiamo ora i metodi iniziando dal costruttore dove oltre all’inizializzazione dei dati, che qui non vediamo nel dettaglio ma che si basa sulla generazione di numeri casuali, viene anche creato un’oggetto per la GUI:

   def __init__(self, lenght=6):
      """genera la tabella iniziale quadrata e di dimensione iniziale lengoht"""
      self.board = [[]]
      
      [...]

      #inizializzo ambiente grafico 
      self.master = Tk()
      self.master.title('life game')
      self.w = Canvas(self.master, width=lenght*10, height=lenght*10)
      self.w.pack()

Viene infatti inizializzato l’ambiente grafico creando un oggetto della classe Tk, assegnato un nome alla finestra, aggiunto un oggetto immagine (Canvas) alla finestra e infine si utilizza il metodo pack() per organizzare gli oggetti nella finestra. In questo caso la chiamata a pack()  è relativamente utile essendoci solamente un oggetto canvas nella finestra.

Non entro nei dettagli del metodo evolve che non è coinvolto nella rappresentazione grafica.

Segue infine il metodo show() che rappresenta graficamente lo stato del sistema.

   def show( self ):
      self.w.delete(ALL)
      for i,v in enumerate(self.board):
         for j,w in enumerate( self.board[i] ):
            if (self.board[i][j] == 0):
               self.w.create_rectangle(i*10, j*10, i*10+10, j*10+10, fill="blue")
            else:
               self.w.create_rectangle(i*10, j*10, i*10+10, j*10+10, fill="yellow")

Anche in questo caso la libreria tkinter rende le cose piuttosto seplici; abbiamo infatti un loop su tutti gli elementi della tabella e andreamo a rappresentare sul nostro oggetto canvas un quadrato blu per le celle vuote ed un quadrato giallo per quelle piene. La funzione che utilizziamo in questo caso è

create_rectangle(x0, y0, x, y, fill="yellow")

La delete() a inizio metodo serve a rimuovere gli oggetti creati in precedenza.

La libreria tkinter mi permette quindi di definire una GUI perfettamente funzionale con pochi passi:

  • definisco un oggetto GUI
  • ne specifico gli elementi grafici
  • controllo il flusso del programma con mainloop, update e funzioni per la gestione dei vari eventi che è necessario controllare

Abbiamo visto qui un esempio di utilizzo della libreria tkinter, documentazione più completa è disponibile nella documentazione ufficiale di python.

esempio thread in python: calcolo della matrice prodotto

Vediamo ora un esempio di programma per il calcolo di una matrice prodotto in python che esegue il calcolo di ogni elemento in un thred differente

Matematicamente l’elemento C{}under{i,j} della matrice prodotto è definito da

C{}under{i,j}=sum{n=1}{K}{A{}under{i,n}B{}under{n,j}}

Il programma andrà quindi a definire una lista di thread, aspetterà il completamento di tutti e scriverà a avideo la matrice prodotto.
Inserisco per prima cosa le tre matrici coinvolte: A e B sono le matrici che verranno moltiplicate e C sarà usato per contenere il risultato.
Il programma è in grado di gestire anche matrici di dimensioni differenti anche se A e B qui hanno una dimensione specifica. Si può quindi rieseguire l’esempio semplicemente sostituendo A e B o modificandolo per andare a leggere da disco i valori.

if __name__ == "__main__":
   """ inizializzo le tre matrici"""
   # definisco le matrici iniziali
   A = [ [1,1,1], [1,1,1]]
   B = [ [1,1], [1,1],[1,1]]
   C = [[0 for j in range(len(A))] for i in range(len(B[0]))]

Definisco una lista in cui raggrupperò i thread che in questo caso utilizzerò per assicurarmi che tutti i thread hanno completato la loro attività prima di stampare il risultato.
Il codice contiene anche, commentata, la definizione di un oggetto lock che può essere utilizzato per controllare la sincronizzazione dei thread. In questo caso però non è utile dato che le operazioni eseguite dai vari thread sono indipendenti.

   
   # acquisizione del lock
   # threadLock = threading.Lock()
   threads = []

Definisco e avvio poi i vari thread sfruttando un’apposita classe myThread che descriveremo più sotto nel dettaglio.

   # avvio in thread per ogni elemento della nuova matrice
   thread_id = 0
   for row in range( len(A) ):
      for column in range( len(B[0]) ):  
         # Create new threads
         threads_a = myThread(thread_id, "Thread-"+str(row)+"_"+str(column), row, column)
         # Start new Threads
         threads_a.start()
         # Add threads to thread list
         threads.append(threads_a)
         thread_id = thread_id + 1

attendo il completamento di tutti i thread

   #    Wait for all threads to complete
   for t in threads:
      t.join()

stampo in fine il risultato

   for i,v in enumerate(C):
      print(C[i])

Passiamo ora alla classe myThread che è costituita ridefinendo la classe threading.Thread.
In particolare ridefiniamo due funzioni: un costruttire e la funzione run che viene eseguita dal thread avviato con lo start().
Il costruttore si limita a definire nell’oggetto alcune variabili passate per argomento

class myThread( threading.Thread ):
   def __init__(self, threadID, name, row, column):
      threading.Thread.__init__(self)
      self.threadID = threadID
      self.name = name
      self.row = row
      self.column = column

la funzione run invece contiene tutto il calcolo dell’elemento di matrice

   def run( self ):
      print ( "Starting " + self.name )
      # Get lock to synchronize threads
      # threadLock.acquire()
      # calculate matrix element
      self.totale = 0
      for a in range(len(A[self.row])):
         for b in range( len(B) ):
            if( a == b ): 
               self.totale = self.totale + A[self.row][a] * B[b][self.column]
            #print("{:s}, self.totale = {:d}".format(self.name, self.totale) )

      C[self.row][self.column] = self.totale
      # Free lock to release next thread
      # threadLock.release()

Decommentando la riga print si può vedere come i thread procedono in parallelo.

Riporto sotto il codice completo

class myThread( threading.Thread ):
def __init__(self, threadID, name, row, column):
threading.Thread.__init__(self)
self.threadID = threadID
self.name = name
self.row = row
self.column = column
def run( self ):
print ( "Starting " + self.name )
# Get lock to synchronize threads
# threadLock.acquire()
# calculate matrix element
self.totale = 0
for a in range(len(A[self.row])):
for b in range( len(B) ):
if( a == b ):
self.totale = self.totale + A[self.row][a] * B[b][self.column]
#print("{:s}, self.totale = {:d}".format(self.name, self.totale) )

C[self.row][self.column] = self.totale
# Free lock to release next thread
# threadLock.release()

if __name__ == "__main__":
""" inizializzo le tre matrici"""
# definisco le matrici iniziali
A = [ [1,1,1], [1,1,1]]
B = [ [1,1], [1,1],[1,1]]
C = [[0 for j in range(len(A))] for i in range(len(B[0]))]

# acquisizione del lock
# threadLock = threading.Lock()
threads = []

# avvio in thread per ogni elemento della nuova matrice
#numThread = A.len() * B[0].len()
thread_id = 0
for row in range( len(A) ):
for column in range( len(B[0]) ):
# Create new threads
threads_a = myThread(thread_id, "Thread-"+str(row)+"_"+str(column), row, column)
# Start new Threads
threads_a.start()
# Add threads to thread list
threads.append(threads_a)
thread_id = thread_id + 1

# Wait for all threads to complete
for t in threads:
t.join()

for i,v in enumerate(C):
print(C[i])


			

python – fork e comunicazione tra processi

Nel seguente programma, utilizzando il calcolo della serie di fibonacci per pretesto, mostro un esempio di utilizzo del fork e della comunicazione tra processi.

Ai fini del calcolo dei termini della successione di fibonacci utilizzo una funzione ricorsiva che richiama se stessa fino a che non arriva a termini noti: non è il massimo per quel che riguarda le prestazioni ma è comoda e compatta e in questo caso è solo un pretesto.

Iniziamo dal listato del programma:

#!/usr/bin/env python3 
import os, sys

def fib_rec(n):
    """calculate Fibonacci series up to n"""
    if n == 1:
       return 1
    elif n == 2:
       return 1
    else:
       return fib_rec(n-1)+fib_rec(n-2)

while 1:
    r,w=os.pipe()

    num = int(input("Please enter an integer: "))

    pid = os.fork()
    if pid:          # Parent
        while 1:
            data=os.read(r,64)
            if data == (" ").encode():
                break
            else:
                print (str(pid)+": child calculate: " + str(data))
    else:           # Child
        count=1;
        while count <= num:
            fibn =  fib_rec(count)
            # il loop serve a passare parole di 64 byte fisse visto che poi leggo byte per byte
            count2 = 1
            while count2 <= 64 - len(str(fibn)):
                os.write(w, ("").encode());
                count2 = count2 + 1
            msg = (str(fibn)).encode()
            os.write(w, msg)
            count = count+1
        # invio stringa vuota per chiudere pipe
        count2 = 1
        while count2 < 64 :
            os.write(w, ("").encode());
            count2 = count2 + 1
        os.write(w, (" ").encode());
        exit(0)

Non spieghiamo nel dettaglio fib_rec che è semplicemente una funzione ricorsiva per il calcolo della successione di fibonacci.

Il programma è costituito da un loop infinito nel quale viene chiesto quanto deve essere lunga la successione da calcolare. Ad ogni ciclo il programma definisce una pipe, genera un processo child per eseguire il calcolo e mostra a video i risultati calcolati dal processo figlio e passati al processo padre.

Vediamo più nel dettaglio:

    r,w=os.pipe()

definisce la pipe e restituisce due file descriptor; il primo è utilizzabile per leggere ed il secondo per scrivere.

Una volta ottenuta la lunghezza della sequenza da calcolare, il programma genera il figlio

pid = os.fork()

l'esecuzione del programma procede da qui sia per il processo padre sia per quello figlio ma nel caso del padre pid conterrà il pid del figlio, nel caso del figlio pid conterrà il valore 0. Questo viene usato per distinguere il comportamento di padre e figlio.

Il processo padre entra in un loop infinito in cui legge parole di 64 byte dalla pipe e da cui esce se il valore ritornato è uno spazio.

    if pid:          # Parent
        while 1:
            data=os.read(r,64)
            if data == (" ").encode():
                break
            else:
                print (str(pid)+": child calculate: " + str(data))

Il processo figlio, di contro, calcola i termini della successione di fibonacci e li scrive nella pipe assieme a tanti caratteri vuoti quanti ne servono per completare la parola di 64 byte. Terminata la sequenza, invia una stringa contenente un solo spazio per dire al processo padre di concludere il suo ciclo ed esce.

        count=1;
        while count <= num:
            fibn =  fib_rec(count)
            # il loop serve a passare parole di 64 byte fisse visto che poi leggo byte per byte
            count2 = 1
            while count2 <= 64 - len(str(fibn)):
                os.write(w, ("").encode());
                count2 = count2 + 1
            msg = (str(fibn)).encode()
            os.write(w, msg)
            count = count+1
        # invio stringa vuota per chiudere pipe
        count2 = 1
        while count2 < 64 :
            os.write(w, ("").encode());
            count2 = count2 + 1
        os.write(w, (" ").encode());
        exit(0)

python e automi cellulari – life

Volendo farmi un’idea del python, dopo aver letto il tutorial ho pensato di provare a fare un piccolo programma e, avendo recentemente letto un articolo sugli automi cellulari la scelta è caduta su un’implementazione del famoso gioco life.

Per chi non lo conoscesse, life è un automa cellulare, ovvero un sistema che evolve sulla base di regole di interazione tra gli elementi del sistema. Nel caso specifico di life il sistema è costituito da una tabella in cui ogni elemento è costituito da una casella che può essere in due stati: morto o vivo. Ogni casella ha 8 vicini:

  1. Se una casella è morta ed ha esattamente 3 vicini vivi, diventa viva. Altrimenti rimane morta
  2. Se una casella è viva ed ha 2 o 3 vicini vivi rimane viva altrimenti muore

nell’implementazione che ho realizzato il sistema è a topologia toroidale:

  1. l’elemento a destra di quello a più a destra è l’elemento più a sinistra della stessa riga,
  2. l’elemento a sinistra di quello più a sinistra è l’elemento più a destra della stessa riga
  3. l’analogo per le colonne

Riporto ora il programma da copiare in un file ed eseguire con python 3.
In questa implementazione ho trovato comodo dare valore 0 alle cellule more ed 1 a quelle vive.

import random

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

# i=0, j=0 
   totale = array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]+array[1][columns-1]+array[1][0]+array[1][1]
   if    array[0][0] == 0:
      if totale == 3:
         array2[0][0]=1
      else:
         array2[0][0]=0
   if array[0][0] == 1:
      if totale <= 2:
         array2[0][0]=0
      elif totale <= 4:
         array2[0][0]=1
      else:
         array2[0][0]=0
# i=rows-1, j=0 
   totale = array[rows-2][columns-1]+array[rows-2][0]+array[rows-2][1]+array[rows-1][columns-1]+array[rows-1][0]+array[rows-1][1]+array[0][columns-1]+array[0][0]+array[0][1]
   if    array[rows-1][0] == 0:
      if totale == 3:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0
   if array[rows-1][0] == 1:
      if totale <= 2:
         array2[rows-1][0]=0
      elif totale <= 4:
         array2[rows-1][0]=1
      else:
         array2[rows-1][0]=0

# i=0, j=columns-1
   totale = array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]+array[1][columns-2]+array[1][columns-1]+array[1][0]
   if    array[0][columns-1] == 0:
      if totale == 3:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0
   if array[0][columns-1] == 1:
      if totale <= 2:
         array2[0][columns-1]=0
      elif totale <= 4:
         array2[0][columns-1]=1
      else:
         array2[0][columns-1]=0

# i=rows-1, j=columns-1 
   totale = array[rows-2][columns-2]+array[rows-2][columns-1]+array[rows-2][0]+array[rows-1][columns-2]+array[rows-1][columns-1]+array[rows-1][0]+array[0][columns-2]+array[0][columns-1]+array[0][0]
   if    array[rows-1][columns-1] == 0:
      if totale == 3:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0
   if array[rows-1][columns-1] == 1:
      if totale <= 2:
         array2[rows-1][columns-1]=0
      elif totale <= 4:
         array2[rows-1][columns-1]=1
      else:
         array2[rows-1][columns-1]=0

# i=0
   for j in range( 1, columns-2 ):
      totale = array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]+array[1][j-1]+array[1][j]+array[1][j+1]
      #print( totale )
      if    array[0][j] == 0:
         if totale == 3:
            array2[0][j]=1
         else:
            array2[0][j]=0
      if array[0][j] == 1:
         if totale <= 2:
            array2[0][j]=0
         elif totale <= 4:
            array2[0][j]=1
         else:
            array2[0][j]=0

# i=rows-1
   for j in range( 1, columns-2 ):
      totale = array[rows-2][j-1]+array[rows-2][j]+array[rows-2][j+1]+array[rows-1][j-1]+array[rows-1][j]+array[rows-1][j+1]+array[0][j-1]+array[0][j]+array[0][j+1]
      #print( totale )
      if    array[rows-1][j] == 0:
         if totale == 3:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0
      if array[rows-1][j] == 1:
         if totale <= 2:
            array2[rows-1][j]=0
         elif totale <= 4:
            array2[rows-1][j]=1
         else:
            array2[rows-1][j]=0

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

# j=0
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-1]+array[i-1][0]+array[i-1][1]+array[i][columns-1]+array[i][0]+array[i][1]+array[i+1][columns-1]+array[i+1][0]+array[i+1][1]
      #print( totale )
      if    array[i][0] == 0:
         if totale == 3:
            array2[i][0]=1
         else:
            array2[i][0]=0
      if array[i][0] == 1:
         if totale <= 2:
            array2[i][0]=0
         elif totale <= 4:
            array2[i][0]=1
         else:
            array2[i][0]=0

# j=columns-1
   for i in range( 1, rows-2 ):
      totale = array[i-1][columns-2]+array[i-1][columns-1]+array[i-1][0]+array[i][columns-2]+array[i][columns-1]+array[i][0]+array[i+1][columns-2]+array[i+1][columns-1]+array[i+1][0]
      #print( totale )
      if    array[i][columns-2] == 0:
         if totale == 3:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0
      if array[i][columns-2] == 1:
         if totale <= 2:
            array2[i][columns-2]=0
         elif totale <= 4:
            array2[i][columns-2]=1
         else:
            array2[i][columns-2]=0

# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:                
               array2[i][j]=1
            else:
               array2[i][j]=0
    return array2 

def start_configuration( lenght = 6 ): 
### genera la tabella iniziale quadrata e di dimensione iniziale lenght
    board = [[]]
    line = []
    random.seed()

    for a in range( lenght ):
       line = []
       for b in range( lenght ):
           tmp = random.randint( -1, 1 )
           if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

   board.remove([])
   return board

board = [[]]
board = start_configuration( 20 )

for i,v in enumerate(board):
   print(board[i])

print("\n")

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

Dopo aver importato il modulo random che utilizzerò per generare la configurazione iniziale, il programma definisce due funzioni: la prima per calcolare uno step di evoluzione, la seconda per generare una configurazione iniziale. Segue poi il corpo principale.

Iniziamo ad esaminare il programma a partire dal corpo principale che è piuttosto semplice:

board = [[]]
board = start_configuration( 20 )

inizio dichiarando la tabella come lista di liste e gli assegno una configurazione con una funzione che esamineremo in seguito. Alla funzione start_configuration() passo come parametro il numero di righe e colonne: ho presupposto che fosse quadrata.

for i,v in enumerate(board):
   print(board[i])

stampo a video la configurazione iniziale con un semplice loop sugli elementi della lista. enumerate restituisce come primo valore l’indice numerico dell’elemento di una lista, indice che poi uso per stampare l’elemento.

while True:
   ok = input()
   board = evolve( board )
   for i,v in enumerate(board):
      print(board[i])

entro infine in un loop infinito per il calcolo degli stati successivi del sistema. Per avere controllo sul processo ad ogni ciclo attendo un invio da parte dell’utente e poi calcolo e stampo a video lo stato successivo.

Esaminiamo ora la prima funzione.

import random

start_configuration() genera casualmente la configurazione iniziale e per farlo ho importato il modulo random

def start_configuration( length = 6 ):
### genera la tabella iniziale quadrata e di dimensione iniziale length

segue poi la definizione della funzione nella quale ho impostato un valore di default per la variabile passata e una riga di commento.
Questa riga di commento ad inizio funzione e preceduta da tre # è in qualche modo speciale e serve a documentare il codice. Appositi tool possono essere utilizzati per esaminare il codice in python alla loro ricerca e generare automaticamente della documentazione.

   board = [[]]
   line = []

definisco le liste che mi serviranno

   random.seed()

inizializzo il generatore di numeri casuali.

   for a in range( length ):
      line = []
      for b in range( length ):
          tmp = random.randint( -1, 1 )
          if tmp > 0:
             line.append( 1 )
          else:
             line.append( 0 )
      board.append( line )

entro nel loop che genera la tabella casuale. Dato che la tabella è in realtà una lista di liste la cosa che mi è sembrata funzionare meglio è stata genereare una riga alla volta per poi aggiungerla alla tabella utilizzando la funzione append delle liste.

   board.remove([])

per come l’ho generata, la tabella conteneva una riga vuota che quindi rimuovo.

   return board

Restituisco infine la tabella generata.

La funzione evolve() sebbene molto lunga non è particolarmente complicata. La sua lunghezza deriva dalla casistica articolata necessaria per gestire cosa accade sui bordi della tabella.

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

[...]
# other cases
   for i in range( 1, rows-2 ):
      for j in range( 1, columns-2 ):
         totale = array[i-1][j-1]+array[i-1][j]+array[i-1][j+1]+array[i][j-1]+array[i][j]+array[i][j+1]+array[i+1][j-1]+array[i+1][j]+array[i+1][j+1]
         #print( totale )
         if    array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2

ho riportato quindi solo il caso generico.

Dato che lo stato nel tempo successivo dipende dal numero di vicini e dato che si è scelto di assegnare 1 per il caso cella viva e 0 per quello cella morta, tutto quello che serve è sommare i valori delle caselle coinvolte e confrontare il risultato con le regole che definiscono il gioco.

Il programma andrebbe migliorato sotto diversi aspetti. In particolare:

  • trovare un modo più elegante per gestire la variegata casistica dell’evoluzione per le caselle lungo il bordo.
  • stampare lo stato in modo più visibile
  • dare al  programma un aspetto più unix like, permettendo di eseguirlo passando dei parametri, come le dimensioni delle tabelle, un fiel con una configurazione iniziale, se si vuole che il programma aspetti l’ok dell’esecutore per passare allo stato successivo o eseguire un numero predeterminato di step, altro.
  • capire se il python ha strutture dati più adatte
  • molto altro probabilmente.

PS 1

Si può usare l’operatore modulo per scrivere in modo più compatta la funzione evolve() che diverrà

def evolve( array ):
### esegue lo step di evoluzione del gioco life su una tabella sferica
   rows = len(array)
   columns = len(array[0])
   array2 = [[0 for j in range(rows)] for i in range(columns)]

   for i in range( 0, rows ):
      for j in range( 0, columns ):
         totale = array[(i-1)%(rows)][(j-1)%(columns)]+array[(i-1)%(rows)][j%(columns)]+array[(i-1)%(rows)][(j+1)%(columns)]+array[i%(rows)][(j-1)%(columns)]+array[i%(rows)][j%(columns)]+array[i%(rows)][(j+1)%(columns)]+array[(i+1)%(rows)][(j-1)%(columns)]+array[(i+1)%(rows)][j%(columns)]+array[(i+1)%(rows)][(j+1)%(columns)]
         #print( totale )
         if array[i][j] == 0:
            if totale == 3:
               array2[i][j]=1
            else:
               array2[i][j]=0
         if array[i][j] == 1:
            if totale <= 2:
               array2[i][j]=0
            elif totale <= 4:
               array2[i][j]=1
            else:
               array2[i][j]=0

   return array2