Archivi Categorie: Teoria e pratica

Python e me

Nei giorni scorsi ero alle prese con la preparazione di uno dei nostri articoli di ricerca, in cui ad un certo punto abbiamo cercato di comparare tre strumenti software di analisi. Ognuno degli strumenti è in realtà un prodotto di ricerca, e ognuno è scritto con un linguaggio diverso: il nostro programma, RTSCAN, è scritto in C++; IMITATOR, un tool che hanno sviluppato qui in Francia, è scritto in OCaml; e infine MAST è uno strumento sviluppato all’Universidad de Cantabria in Spagna, ed è scritto in Ada. Ognuno produce risultati in maniera completamente diversa, e c’era quindi la necessità di elaborare questi dati in output in maniera uniforme, per poi produrre dei grafici “decenti”.

Avevamo quindi bisogno di un po’ di script per generare dei dati in input ai tre strumenti, lanciarli, collezionare e uniformare gli output. Abbiamo cominciato con un grande classico: un po’ di bash scripting. Però dopo un po’ ci siamo resi conto che non saremmo andati molto lontano. Un po’ perché io sono sempre stato lento con bash: non mi piace molto la sintassi, e quindi trovo difficile memorizzarla. Un po’ perché sarebbero stati necessari dei tool esterni non banali, e quindi alla fine il risultato non sarebbe stato molto portabile.

Per fortuna che c’è Python. Io non ho mai davvero imparato il Python, perché non ne ho mai avuto il tempo. Non ho tempo per mettermi davanti a un libro o a un corso (anche di quelli accellerati) per imparare l’ABC di un linguaggio. E soprattutto, non ho tempo per imparare a usare le varie librerie (e ce n’è davvero tante). Ma per fortuna, Python ha due caratteristiche peculiari:

1) E’ facile cominciare. Cioè, in realtà all’inizio potete considerarlo tranquillamente come se fosse un linguaggio di scripting. Non c’è bisogno di astruse direttive, di dichiarare variabili, di scrivere funzioni, non c’è bisogno neanche di un main. Si parte a scrivere codice come viene viene, ed è molto probabile che funzioni subito come avevamo pensato.

2) In linea c’è tutto. Qualunque cosa tu voglia fare, basta googlare, e finisci o sul manuale di Python in linea, o su stackoverflow, dove hanno sempre la ricetta pronta per te.

Naturalmente, bisogna conoscere un minimo le basi della programmazione. Ma dal pensiero alla realizzazione passa davvero molto poco.

E passiamo a scrivere brevemente il nostro lavoro. Come prima cosa, avevamo bisogno di specificare il sistema da far analizzare ai tre strumenti. Per semplicità ed immediatezza, abbiamo scelto il formato JSON, che adesso va per la maggiore.  E naturalmente Python ha una libreria per leggere e interpretare un file JSON con sole due funzioni, e il risultato è una lista di dizionari.

Poi, abbiamo scritto 3 funzioni per visitare la lista di dizionari e produrre tre file di input per i tre strumenti. Poi abbiamo scritto 3 funzioni per lanciare i 3 strumenti. Infine, abbiamo fatto post-processing sugli output. Tutto questo in una mezza giornata. Un altro paio di giornate è passato a mettere a posto le cose (perché c’è sempre qualcosa da sistemare, naturalmente) e a cercare di far produrre dei grafici decenti a gnuplot (e ci siamo riusciti solo parzialmente).

Ma la cosa bella di Python è che non si limita ad essere un semplice linguaggio di scripting, ma ha tutte le potenzialità di un vero linguaggio di programmazione. Costrutti evoluti, Object Orientation, ma anche un po di functional programming. C’è la tipizzazione a run-time (il cosidetto duck-typing), il garbage collector. Utilizzando uno stile di programmazione pulito, Python consente di scrivere programmi molto eleganti e “belli”, senza grosso sforzo.

E’ insomma un linguaggio scalabile: si può andare facilmente dal piccolo script di poche linee, al programma mediamente complesso senza grossi problemi. Inoltre ti consente di fare fast prototyping: se hai un’idea, la butti giù e la testi in pochi minuti e con poco sforzo, e la puoi tenere lì in caldo pronto a riprenderla e ad evolverla in qualcosa di più complesso più avanti.

Ha dei difetti? Non sono sicurissimo di quanto possa scalare Python. Se il progetto diventa veramente grande, e con tanti programmatori, non sono sicuro che Python basti. Per esempio, il codice Python può diventare orribile se scritto male e senza giudizio; il fatto che si usi duck-typing richiede una certa dose di coordinazione sulle interfacce quando si lavora in tanti; e quando un progetto è grande, non è detto che tutti i programmatori siano allo stesso livello.

Insomma, mi sa che mi tocca studiarmelo meglio. Adesso che l’ho provato in un caso quasi reale, penso che comincerò ad utilizzarlo sempre più spesso!

Ottimizzazioni a volte sorprendenti

Nel post precedente riguardante newLISP ho inserito uno scriptino di una dozzina di righe per far vedere quando sia bello ed efficiente newLISP. Ebbene ho barato, solo un pochino (quello che da noi si direbbe na frisa o ‘n cicinin). Ma forse è il caso di raccontare tutta la storia, che ha una morale (laicista), quindi istruttiva.

La prima versione dello script usava (append-file)

syntax: (append-file str-filename str-buffer)
Works similarly to write-file, but the content in str-buffer is appended if the file in str-filename exists. If the file does not exist, it is created (in this case, append-file works identically to write-file). This function returns the number of bytes written.

Questo è lo script

;; versione lenta come raccontato nel post
(set 'k 1000)
(set 'm (* k k))
(set 'tstart (time-of-day))
(append-file "primes" (string 2 "\n"))
(dolist (n (sequence 3 (* 10 m) 2))
    (if (= (length (factor n)) 1)
        (append-file "primes" (string n "\n")))
)
(println (- (time-of-day) tstart))
(exit)

Sul mio ‘puter, con processore Intel Core Duo @ 2.4 GHz, 2 GB di RAM e Ubuntu 10.10 è tutto OK, l’esecuzione richiede circa 42-44 secondi (il dato che compare alla fine dell’esecuzione, viene da (time-of-day) che restituisce millisecondi)

A prima vista esaminando il grafico Cronologia CPU sembra che newLISP sia davvero fatto bene e riesca a utilizzare tutte le risorse disponibili: non è vero. La riga rossa è newlisp, quella arancione è nautilus. Ecco! (append-file) non richiede che il file sia aperto prima con (open) e chiuso alla fine con (close) ma ogni volta che viene chiamata è lei stessa che lo apre e chiude. Se c’è una sola CPU ci dev’essere uno swap continuo e le prestazioni decadono. Di molto.

Sul PC con Windows che uso di solito (XP su AMD Sempron @ 1.67 GHz, 448 MB di RAM) i tempi di esecuzione per la versione con (write-line) sono di 97-103 secondi, con (append-file) di 6440-6840 secondi (1h 38m e 1h 54m), cioè 86-87 volte peggiori!

CPU occupata con la versione (write-line)

 

CPU occupata con la versione (append-file)

 

distribuzione della CPU tra i processi durante l'esecuzione dello script

Ah! dimenticavo: con Windows dovete mettere in conto l’antivirus, che serve (eccome!) ma mangia.

L’esecuzione su un portatile con Vista su Acer Extensa Celeron 560 @ 2.13 MHz, 1 GB di RAM ha dato grafici simili (a proposito adesso Task Manager si chiama Gestione Attività Windows). La versione veloce ha richiesto 70-71 secondi, quella lenta l’ho interrotta.

versione (write-line)

 

versione (append-file)

Conclusione

Ed ecco la morale della storiella: mai fermarsi alla prima versione, se qualcosa non va come ci aspettiamo, prima di dare la colpa al programma, al computer o al mondo, verificare. E leggere tutto il manuale, fino in fondo, ma questo mi sembra di averlo già detto ;-)

Programmare o progettare?

Ultimamente scrivo molto poco sui miei blog perché sto preparando le slides e gli appunti per i due corsi che sto tenendo in questo momento, ed è una cosa che mi prende molto tempo. Per uno di questi corsi in particolare sto preparando tutto il materiale da zero, perché è la prima volta che lo tengo.

Il corso si intitola Object Oriented Software Design, e lo scopo del corso è di formare progettisti di software. Si parte da una introduzione al linguaggio Java, per passare poi al C++ in maniera piuttosto approfondita.  Poi si studiano i cosidetti Design Patterns; poi un po’ di ingegneria del software, elementi di testing, la progettazione agile. In tutto il corso consisterà di 12 crediti, per più di 100 ore tra lezioni frontali ed esercitazioni.

Fino ad adesso ho fatto un po’ di lezioni e sto per concludere la parte su Java. Conto di finire con Java in altre 8-10 ore massimo, dopodiché mi dedicherò al C++.

Dovete sapere che io mi faccio un punto d’onore di rilasciare liberamente tutte le mie slides. E quindi, mi sembra giusto segnalarle anche su questo blog: se volete saperne di più, andate su mio sito web alla pagina del corso. Le slides delle lezioni dalle 03 alle 05 sono prese abbastanza pedissequamente dal libro “Thinking in Java” third edition, di Bruce Eckel (scaricabile liberamente dal sito); dalla lezione 07 in poi, invece, mi distacco abbastanza. In cambio di questa mia liberalità, chiedo solo di segnalarmi errori, omissioni, cose da migliorare, da togliere, da aggiungere. Ogni commento è il benvenuto!

Tra poco rilascerò una lezione su Run-Time Type Identification, Anonymous Inner Classes, Binary Tree. E naturalmente, se vi interessa, andate a guardare ogni tanto e ci troverete le nuove slides man mano che le completo.

E veniamo al titolo del post: che differenza c’è tra programmare e progettare? E, ha senso parlare di progettazione del software? Ovviamente la risposta alla seconda domanda è sì, altrimenti non avrei intitolato così il corso. La progettazione si rende necessaria per grandi programmi. Finché si fanno piccoli programmini o utility, si può anche lavorare da soli e fare un po’ gli artisti (o se volete gli artigiani). Si dice spesso che programmare è un arte; perché l’atto di passare dall’idea alla sua realizzazione tramite un algoritmo è un atto quasi artistico e misterioso e poco compreso del nostro cervello. E va tutto bene finché appunto ci limitiamo a risolvere un problema ben limitato e definito (ad esempio ordinare un insieme di elementi, effettuare un ricerca in un testo, etc.).

Quando però la complessità di un programma supera un certo livello, si rende necessario pianificare attentamente lo sviluppo e dividerlo tra più team di programmatori. Si passa a un livello industriale: bisogna elencare i requisiti, dividere il probelma in sottopobremi più piccoli, dividere il carico di lavoro tra gruppi di programmatori, pianificare il test di unità, il test di integrazione, etc. C’è poco spazio per l’arte qui: si passa dall’artigianato alla produzione industriale.

E veniamo alla prima domanda: la differenza fra il progettista e il programmatore è un po la stessa che c’è fra l’ingegnere e il geometra. Il primo costruisce palazzi, grattacieli, ponti, il secondo ti alza un muro o ti mette la veranda sulla terrazza.

La mia impressione è che in molte università in Italia i docenti insegnino al massimo a fare i programmatori. Ma quasi nessuno insegna a fare il progettista. Ci sono corsi di Ingegneria del Software, ma sono troppo spesso un’enunciazione di tecniche senza applicazioni pratiche. E invece, trovo difficile che si possa imparare a progettare il software senza un minimo di pratica.  La mia impressione (ma spero di essere smentito da qualche collega) è che in Italia siamo rimasti indietro anche su questo. Nel mio piccolo, spero di colmare almeno parzialmente questo gap. Almeno ci tento.

Impacchettare

Potrebbe esservi capitato qualche volta di dover caricare l’auto di valige, pacchi e pacchettini. E  se avete una moglie come la mia, non vi bastarebbe la monovolume più capiente sul mercato! Però, bisogna anche essere bravi ad impacchettare le cose per bene (cosa che mi toccherà fare tra un paio di giorni). E quasi mai riesce alla prima volta vero? Di solito si comincia a mettere la roba, e dopo un po’ ci si accorge che così non va. E allora bisogna tirare tutto fuori e ricominciare da capo con la santa pazienza.

In effetti, non è (sempre) colpa vostra: i problemi di impacchettamente sono tra i più “difficili” problemi matematico/informatici, fanno infatti parte della classe dei problemi NP-hard.

scatole...

Cominciamo con il più semplice, chiamato Bin-packing. In questo problema avete un certo numero di oggetti di dimensione varia, da mettere dentro delle scatole tutte uguali con una certa capacità. L’obiettivo è di utilizzare il minor numero di scatole. Per semplificare, consideriamo il problema unidimensionale: gli oggetti sono parallelepipedi tutti con la stessa base e con altezza varia, e gli scatoloni hanno la stessa base degli oggetti (che quindi si possono solo impilare uno sul’altro). Ad esempio, consideriamo il problema di avere scatole di altezza pari a 30 cm, e 5 oggetti di altezza pari a 5cm, 10 cm, 12 cm, 13 cm, 15 cm.

Se ci pensate un attimo, troverete che vi bastano 2 scatole: la prima contenente l’oggetto da 15 cm e quello da 13 cm; la seconda contiene tutti gli altri. Poiché gli oggetti non entrano evidentemente in una sola scatola, abbiamo trovato la soluzione minima.

Perché dico che questo problema è difficile? L’abbiamo risolto a mente in pochi secondi!

In informatica, i problemi “difficili” non sono quelli impossibili da risolvere, ma piuttosto quelli che scalano male con la dimensione dell’input. La dimensione dell’input al problema in questo caso è dato dal numero di oggetti da impacchettare. In un problema difficile, il tempo per risolverlo aumenta esponenzialmente con la dimensione dell’input.

Purtroppo il problema del bin-packing è un problema difficile perché per trovare la soluzione ottima dobbiamo per forza analizzare tutte le possibilità. Per essere più precisi: ad oggi non si conosce alcun algoritmo furbo per questo problema, cioè gli unici algoritmi ottimi conosciuti si limitano ad enumerare tutte le combinazioni possibili. E purtroppo, il numero di combinazioni è esponenziale nel numero degli oggetti.

Per capirlo considerate questo semplice ragionamento: supponiamo di avere 20 oggetti e al massimo 10 scatole. Numeriamo le scatole da 0 a 9. A questo punto, ogni possibile combinazione può essere identificata da un numero a 20 cifre: ogni posizione corrisponde a un oggetto, e il suo valore (da 0 a 9) indicherà in quale pacchetto infiliamo l’oggetto in questione. E’ chiaro che il numero di combinazioni corrisponderà a 1.000.000.000.000.000.000.000 (ovvero 10^{21}). Non male, no?

E stiamo parlando del problema unidimensionale. Nella pratica, spesso si ha a che fare con problemi in 3D (quello del bagagliaio dell’automobile ad esempio) o solo in 2D (il piazzamento di circuiti su un chip). Non è che siano più difficili in senso informatico, intendiamoci: anche in quel caso bisogna analizzare tutte le combinazioni di oggetti.

Panico? Ok, panico!

Cioè, aspettate un attimo, spesso non è che ci interessi proprio la soluzione ottimale, anche una abbastanza buona può andare bene, no? Dai, accontentiamoci!

Per questo si usano delle euristiche, ovvero degli algoritmi semplici che magari non ci danno proprio la soluzione ottima, ma per lo meno ci danno una soluzione accettabilmente buona. Per il bin-packing ci sono i seguenti:

  • First fit decreasing: in pratica, ordiniamo gli oggetti in ordine di altezza decrescente, e poi li mettiamo l’uno dopo l’altro nel primo scatolone in cui entrano. E se un oggetto non entra in nessuno di quelli già incignati, ne prendiamo uno nuovo.
  • Best fit decreasing: ordiniamo come prima gli oggetti in ordine di altezza decrescente, e poi mettiamo ogni oggetto nella scatola in cui entra meglio (ovvero quella in cui lascia meno spazio libero). Come prima, se necessario prendiamo uno scatolone nuovo.

Questi algoritmi sono nettamente più semplici di quelli di enumerazione. Innanzitutto, ordinare n elementi in ordine descente si fa in un tempo proporzionale a n log n. Per esempio con 20 oggetti, l’ordinamento si fa più o meno in 24-25 passi. Poi l’inserimento nello scatolone di ogni oggetto si fa in tempo pari a log n, e ci sono n oggetti, quindi anche qui n log n. In informatica teorica, si usa scrivere che la complessità di questi algoritmi è O(n \log{n}). Quindi, con una cinquantina di passi al più abbiamo risolto il problema contro il numero improbabile di cifre di prima.

E infine, quanto sono “buoni” questi algoritmi rispetto all’algoritmo ottimo? Se chiamiamo con OPT il numero minimo di scatole necessarie (calcolate dall’algoritmo ottimo), è stato dimostrato che First-Fit decreasing ne richiede al massimo 11/9 OPT + 6/9. Che non è poi tanto male!!

Perché mi interesso di bin-packing? Perché mi capita tra i piedi piuttosto spesso… infatti, sappiate che la mia specializzazione è nella schedulazione dei processi nei sistemi operativi, e in quest’ambito il bin-packing salta fuori piuttosto spesso.

E adesso a voi: se volete esercitarvi nella programmazione, scrivete una semplice funzioncina che implementi uno dei due algoritmi di cui sopra, per esempio in Python! perché no? o in qualunque altro linguaggio di vostro gradimento, inclusi l’italiano con tutti i suoi dialetti! Qui ad esempio ne trovate uno in Visual Basic (credo). E qui un’intera serie in Haskell dal mio amico Bjorn Brandeburg.

Buona programmazione!

Il problema della fattorizzazione

NP

Hronir ci fa un piacere ricordandoci in un paio di ottimi post che il problema della fattorizzazione dei numeri non è necessariamente un problema NP (non polinomiale). Da leggere attentamente!

Il fatto è che molte persone, anche molti ricercatori in matematica, informatica, etc. danno per scontato che:

  1. La fattorizzazione sia un problema NP-completo, e quindi gli algoritmi di crittografia, basati sul problema della fattorizzazione, siano intrinsicamente sicuri.
  2. I calcolatori quantistici renderanno i problemi NP-hard risolvibili in tempo polinomiale, e quindi renderanno inutili gli attuali algoritmi di crittografia.

In quanto al primo assunto, in realtà non si sa quale sia la complessità del problema di fattorizzazione. Hronir da degli ottimi link, vi consiglio di seguirli. Il sospetto è che in realtà non sia un problema NP-completo, ma un problema un po’ più semplice (magari non proprio polinomiale, ma insomma). In quanto al secondo assunto, Hronir ci dice che non esiste (ad oggi) alcun algoritmo quantistico in grado di risolvere un problema NP-hard.

Non ci avete capito una mazza? E’ il momento di iscriversi a un corso di informatica! :)

Altri link utili:

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

Unisciti agli altri 37 follower