Liste infinite in Python

Avevo detto che mi sarei buttato sullo storico, ma mi sta prenendo più tempo del previsto, e allora ecco un post breve su Python (con la collaborazione di Juhan)

Puntate precedenti:

La domanda di oggi è: si possono fare le liste infinite in Python come in Haskell? La risposta è ni. Il Python non ha alcun meccanismo sintattico per definire una lista infinita, ed inoltre è tutt’altro che “pigro”: non appena definite qualcosa, Python cerca di calcolarla. Quindi, la risposta diretta sarebbe NO. Però. Però esiste un meccanismo in Python che è quello dei generatori, e come vedremo ci permette di calcolcare delle liste “potenzialmente infinite”.

Il meccanismo ha direttamente a che vedere con il ciclo for. Per esempio, se volete fare un ciclo in cui la variabile i assume tutti i valori tra 1 e 10 at ogni iterazione, dovete scrivere qualcosa come:

for i in range(1,10) :
    print i,

In pratica, questo stampa a video tutti i numeri tra 1 e 9.

C’è una cosa che i non pythonisti madrelingua non impareranno tanto facilmente e alcuni mai: il ciclo for i in range (1,10): sarà eseguito per i valori 1, 2, 3, 4, 5, 6, 7, 8, e 9. Cioè fino al limite superiore ESCLUSO.

Questo nella visione di Guido aveva un senso: se il range fosse normale (cioè partisse da zero) il limite superiore rappresenterebbe il numero di componenti. Questa è la spiegazione ufficiale. Quella meno ufficiale è che il BDFL continuasse a sbagliare indici negli arrays in C. Ma è un’accusa falsa e tendenziosa — anche se Python è unico per questo comportamento.

Ma vediamo più in dettaglio come funziona:

  • Prima la funzione range(1,10) genera una lista contenente tutti i numeri da 1 a 9
  • Una lista in Python è un caso particolare di un contenitore, e un contenitore può essere visitato usando un iteratore (per chi non sapesse che cosa è un iteratore, è come un puntatore, un indice, un segnaposto, che inizialmente viene posizionato alla testa della lista, e che si può di volta in volta spostare avanti di un passo)
  • Alla prima iterazione viene inizializzato un iteratore che punta alla testa della lista,
  • il valore puntato dall’iteratore viene messo nella variabile i
  • si esegue il codice nel corpo del for
  • alla fine dell’iterazione, l’iteratore viene incrementato per puntare all’elemento successivo della lista; se non ci sono più elementi, il ciclo termina; altrimenti si assegna a i il valore puntato e si torna al passo precedente.

Uh, quante cose! Complicato? Mica tanto, alla fine sembra complicato perché abbiamo spiegato le cose per filo e per segno, ma il comportamento finale è molto intuitivo, vero?

Comunque, la cosa fondamentale da notare qui è che prima viene creata tutta la lista con range(), e dopo si scorre con l’iteratore. Si potrebbe anche fare in un altro modo, in effetti: si potrebbero generare gli elementi della lista man mano che servono e solo se servono. Ed è in parte quello che fa Haskell con la sua pigrizia: calcola gli elementi man mano che servono e solo se servono. E quindi, in Python hanno pensato che questa cosa qui fosse effettivamente utile, e hanno pensato di fornirla con il concetto di generatore.

Cominciamo a vedere in pratica come si fa: nell’esempietto precedente, invece di chiamare range bisogna chiamare xrange così:

#ciclo normale
for i in range(1,10) :
    print i

#ciclo con generatore
for i in xrange(1,10) :
    print i

Nel secondo caso, xrange non costruisce la lista, ma un semplice generatore, ovvero un oggetto che fornisce un iteratore, e ogni volta che avanzate l’iteratore, esso calcola al momento il nuovo valore da restituire. Dal punto di vista della performance non è cambiato molto in questo semplice caso.

Ma supponiamo adesso di voler costruire la sequenza dei primi 10.000 numeri Fibonacci. La lista risultante prenderà un po’ di spazio in memoria, e magari non ci servirà tutta, oppure ci servivà solo per fare il ciclo e da nessun’altra parte nel programma. In tal caso, usare un generatore invece di una lista permette di risparmiare memoria, e magari anche tempo.

Naturalmente adesso ci serve capire come costruire un generatore per i numeri di Fibonacci. Eccolo:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys

def fibGen() :
    a,b = 1,1
    while True :
        yield a
        a,b = b, a+b

n = int(sys.argv[1])
for k in fibGen() :
    print k,
    n -= 1
    if n == 0 :
        break

La funzione fibGen() è in realtà un generatore: da cosa si capisce? dal fatto che invece di ritornare il risultato con la keyword return, usa yield. Ecco come funziona:

  • Per prima cosa si inizializzano le variabili a e b a 1 e 1, rispettivamente.
  • Poi si effettua un ciclo infinito (che infinito non è in realtà!) con la while(True)
  • Viene chiamata yield, che ritorna il valore della variabile a (cioè 1). Però, a differenza di return, la yield si “segna” il punto in cui ci eravamo fermati, e il valore di tutte le variabili locali, così che, la prossima volta che si invocherà, si riparte dal punto in cui ci eravamo fermati.
  • La prossima volta che si invoca, si riparte dallo stato precedente, e a e b vengono aggiornati
  • quindi si ritorna il valore di a, e così via

Come si invoca fibGen()? esattamente come la range, solo che stavolta, se voglio fermarmi ad un certo punto, devo inserire una condizione di uscita dal ciclo con la break. Carino, no? La funzione fibGen() genera una lista potenzialmente infinita, ma un numero alla volta!

Non sarà tutto automatico come in Haskell, ma alla fine abbiamo messo dentro le liste infinite anche qui. Ecco l’output:

Ultima cosa: ricordatevi che il tipo int è limitato a 2.147.483.647, ma c’è il long che sopperisce e permette interi illimitati: vedi la documentazione Python, o anche:

Alla prossima!

Posta un commento o usa questo indirizzo per il trackback.

Commenti

  • juhan  Il 11 dicembre 2011 alle 15:23

    Ho provato a farlo in newLISP, sembrava facile, anzi immediato, invece è panicante. OK! mi dedico all’influenza 😉
    Update: newLISP è bello perché piccolo e veloce ma non ha certo tutti gli strumenti di Scheme o Common L. Questo dopo uno scambio di mail, un perlustramento nel forum, qualche googlata. Niente di nuovo in fondo: se hai un buon martello tutto ti sembra un chiodo.
    Non so se è etico correggere i propri commenti, dai solo questa volta 8)
    Ah! anche l’influenza forse era solo il nervoso 8)

Trackback

Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo di WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione /  Modifica )

Google photo

Stai commentando usando il tuo account Google. Chiudi sessione /  Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione /  Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione /  Modifica )

Connessione a %s...

Questo sito utilizza Akismet per ridurre lo spam. Scopri come vengono elaborati i dati derivati dai commenti.

%d blogger hanno fatto clic su Mi Piace per questo: