/Cw4

TI:WTBD/Ćwiczenia 4

iteracja i generatory

W wielkim uproszczeniu: generator to obiekt iterowalny, tzn. taki, który można umieścić w pętli for na miejscu sekwencji, po której elementach iterujemy; ale w odróżnieniu od sekwencji (listy, krotki, napisy) nie ,,zawiera" on ,,od razu" swoich elementów, tylko ,,produkuje je w miarę potrzeby".

Przykładem generatora jest plik otwarty do odczytu; tu ,,produkowanie" kolejnych elementów w iteracji polega na ,,podawaniu" kolejnych linijek pliku, wczytanych z dysku. Co istotne: nie ma tu konieczności, by cała treść pliku na raz zmieściła się w pamięci operacyjnej -- oczywiście o ile przetwarzanie będzie miało charakter ,,lokalny", bez potrzeby gromadzenia kolejnych wczytanych linijek.

Generatory można też tworzyć samemu. Najprostsza definicja generatora wygląda całkiem jak definicja funkcji, tyle że zamiast słówka return występuje w niej słówko yield (można je przełożyć na polski jako ustąp). To podobieństwo do definicji funkcji może być mylące! bo generator działa jednak dość odmiennie od funkcji. W momencie wywołania, kod generatora nie jest jeszcze uruchamiany -- zamiast tego, zwracany jest obiekt, w którym zawarty jest ten kod oraz aktualny stan generatora (wartości zmiennych lokalnych). W każdym kroku iteracji -- zrealizowanym wewnętrznie jako wywołanie metody next() generatora, kod definicji generatora jest uruchamiany, gdy jego przebieg napotka instrukcję yield, wykonanie zostaje zatrzymane (z zapamiętaniem stanu i pozycji w kodzie), a argument instrukcji yield jest zwrócony jako wynik wywołania next(). Kolejny krok iteracji wznowi kod generatora od linijki kolejne po yield, z zachowaniem jego stanu.

Najprostszy przykład:

def count():
    k = 0
    while True:
        yield k
        k += 1

Ten generator będzie wypluwał kolejne liczby naturalne (od zera począwszy) bez końca (tzn. dopóki nie zabraknie RAM-u). Tak zachowuje się generator, który nigdy nie powraca -- nigdy nie trafia się na instrukcję return (bo np. w definicji jej nie ma), ale również nie ma możliwości ,,wypadnięcia" za koniec kodu generatora (tu: bo nie ma wyjścia z pętli while). Można lekko zmienić ten przykład:

def counter(n):
    k = 0
    while k < n:
        yield k
        k += 1

i teraz generator zachowuje się w iteracji jak range(n) -- iteracja kończy się na n-tym elemencie (dokładnie: rzucany jest wyjątek StopIteration).

Drugi sposób stworzenia generatora polega na przekształceniu już istniejącego generatora (lub innego obiektu iterowalnego), za pomocą tzw. wyrażenia generatorowego. Przykład:

kwadraty = (k*k for k in counter())

Generator kwadraty będzie produkował po kolei kwadraty kolejnych liczb naturalnych -- bez końca, o ile counter() się nie wyczerpie (zakładamy, że dany jest definicją powyżej, a więc się nie wyczerpie). Nawiasy w wyrażeniu generatorowym są wymagane. Można je napisać równoważnie:

def kwadraty():
    for k in counter():
        yield k*k
kwadraty = kwadraty()

ale wyrażenie generatorowe pozwala na prostszy zapis. Ogólniejsza postać:

kwadraty_nieparzyste = (k*k for k in counter() if k % 2)

(zwracać kwadraty tylko tych k, których dzielenie przez 2 daje niezerową resztę). Elementy podawane w iteracji przez wyrażenie generatorowe można więc opcjonalnie filtrować za pomocą warunku (wyrażenia logicznego) napisanego po słowie if.

zadanie: numerowanie linii

Napisać program częściowo realizujący funkcję systemowego polecenia nl (p. man nl), czyli numerujący linijki pliku/plików wejściowych. Zakładamy dodatkowo, że treść każdego z plików wejściowych będzie na wyjściu poprzedzona 1-linijkowym nagłówkiem z nazwą tego pliku, a wynik zostanie posłany na stdout.

Wersja pierwsza:

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

import fileinput, sys

header = '\n*** FILE: {} ***\n'
separator = ': '
linenumber = 0

for line in fileinput.input():
    if fileinput.isfirstline():
        linenumber = 0
        sys.stdout.write(header.format(fileinput.filename()))
    linenumber += 1
#    sys.stdout.write(separator.join(str(linenumber), line)
#    sys.stdout.write('%d%s%s' % (linenumber, separator,line))
#    sys.stdout.write(str(linenumber) + separator + line)
    sys.stdout.write('{0}{1}{2}'.format(linenumber, separator, line))

Nic tu nie ma odkrywczego, można powiedzieć, że to proste ćwiczenie na zastosowanie modułu fileinput. Linijki zakomentowane na końcu to alternatywne (równie dobre) realizacje ostatniej linijki.

Wersja druga:

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

def numeruj(lines, separator=': '):
    linenumber = 0
    for line in lines:
        linenumber += 1
        yield '{0}{1}{2}'.format(linenumber, separator, line)

#inna implementacja:
#def numeruj(lines, separator=': '):
    #from itertools import count, izip
    #for line in izip(str(count(start=1)), lines):
        #yield separator.join(line)

if __name__ == '__main__':
    from sys import stdout
    from optparse import OptionParser
    from itertools import chain
    
    parser = OptionParser()
    parser.add_option('-H', '--header', dest='header')
    parser.add_option('-S', '--separator', dest='separator')
    opts, args = parser.parse_args()
    header = opts.header or '\n*** {} ***\n'
    separator = opts.separator or ': '

    files = (chain(
                (header.format(filename),)
                , numeruj(open(filename), separator)
                )
                for filename in args
            )
    output = chain.from_iterable(files)
    
    for line in output:
        stdout.write(line)

Ta wersja wygląda na nieco długą, ale to dlatego, że zrezygnowałem tu z fileinput, oraz pozwoliłem by przy wywołaniu można było podać własne definicje nagłówka pliku i separatora numeru linii jako wartości opcji. Za to główne zadanie numerowania linijek zrealizowałem za pomocą generatora (definicja numeruj, w dwóch wersjach). Jest to też dobra okazja, by sobie przeczytać opis wykorzystanych tu funkcji do operowania na generatorach (ogólniej -- obiektach iterowalnych), w dokumentacji modułu itertools.

sortowanie danych

po zawartości określonego pola: częściowa emulacja polecenia systemowego sort; ewentualnie z wykorzystaniem modułu csv (zadanie dla czytelnika).

Naturalnie, sortowanie jest operacją nielokalną -- nie można ustalić, który element będzie pierwszy, zanim się nie zbadało wszystkich, więc trzymanie wszystkich elementów sortowanego zbioru na raz w pamięci jest nieuniknione. Chyba, żeby się uciec do sprytnego wykorzystania plików tymczasowych (systemowe polecenie sort tak potrafi, my tu nie będziemy próbować).

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

from optparse import OptionParser
from fileinput import input

parser = OptionParser()
parser.add_option('-t', '--field-separator', dest='separator', default=None)
parser.add_option('-k', '--key', dest='sortfield', type='int', default=1)
parser.add_option('-r', '--reverse', action='store_true', dest='reverse', default=False)
parser.add_option('-n', '--numeric', action='store_true', dest='numeric', default=False)
opts, args = parser.parse_args()
sep, fnum, reverse, numeric = opts.separator, opts.sortfield, opts.reverse, opts.numeric

def keyfun(l):
    try:
        r = l.split(sep)[fnum - 1] # `sort' numeruje pola od 1, a python listy - od 0 
    except IndexError:
        return None # rekord może nie mieć tylu pól, nie chcę by program wtedy padł
    if numeric:
        r = float(r)
    return r
# w następnej linii odbywa się cała faktyczna robota
# NB. tu generator ulega konwersji do listy (via sorted())
# czyli zostaje `skonsumowany'
lines = sorted((l.rstrip() for l in input(args)), key=keyfun, reverse=reverse)
for line in lines:
    print line

Ilustrujemy tu wykorzystanie własnej funkcji do produkcji klucza sortowania. Wywołanie l.rstrip() służy temu, by każdą linijkę ,,oczyścić" z kodu '\n' ją kończącego (przy okazji giną też ew. spacje na końcach linii -- zakładamy, że są one bez znaczenia), inaczej użycie 'print' dałoby w sumie '\n\n' na końcu każdej linii, czyli podwójny odstęp. Jak osiągnąć to samo inaczej?

sortowanie strumienia danych wg. długości rekordów (linijek)

proszę wykonać samemu.

Warto przejrzeć: http://www.dabeaz.com/generators-uk/