11    Przetwarzanie list

Programy bardzo często przetwarzają sekwencje danych. Jakkolwiek szczegóły tego przetwarzania bywają rozmaite, istnieje kilka podstawowych typów operacji wykonywanych na sekwencjach danych. Zostaną one przedstawione poniżej, wraz z informacją, jak wygodnie zrealizować je w języku Python.

Zaczniemy od szybkiego generowania list. Wiemy już, jak tworzyć listy zawierające wiele takich samych elementów:

 

>>> l=[0]*20

>>> l

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

 

lub powtarzający się układ:

 

>>> l=[3,5,2]*6

>>> l

[3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2, 3, 5, 2]

 

oraz jak tworzyć listy, których elementy należą do ciągu arytmetycznego:

 

>>> l=range(1,21,2)

>>> l

[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

 

Poznamy teraz wygodne narzędzie do szybkiego tworzenia list o nawet bardzo złożonej zawartości, w oparciu o inną listę. Tym narzędziem są wytworniki list (ang. list comprehensions). Wytworniki dostępne są w pięciu postaciach:

Postać prosta wytwornika ma następującą składnię:
[wyrażenie for zmienna in sekwencja] i daje w wyniku listę, zawierającą wartości wyrażenia obliczone dla elementów sekwencji wejściowej. Przykłady:

·       Podwojenie wartości:

 

>>> [2*x for x in l]

[2, 6, 10, 14, 18, 22, 26, 30, 34, 38]

 

·       Stworzenie par (x, kwadrat x):

 

>>> [(x, x*x) for x in range(1,5)]

[(1, 1), (2, 4), (3, 9), (4, 16)]

 

·       Tabela kodowa ASCII:

 

>>> [(x, ord(x)) for x in "ABCDEF"]

[('A', 65), ('B', 66), ('C', 67), ('D', 68), ('E', 69), ('F', 70)]

 

·       Lista zawierająca 10 pustych list:

 

>>> [ [] for x in range(10) ]

[[], [], [], [], [], [], [], [], [], []]

 

Postać prosta warunkowa pozwala umieszczać na liście tylko takie elementy, które spełniają pewien warunek (operację usuwania z listy elementów niespełniających określonego warunku nazywamy filtrowaniem danych). Ma następującą składnię:
[wyrażenie for zmienna in sekwencja if warunek]

 

Przykłady:

·       Tylko liczby większe od 10:

 

>>> [x for x in l if x>10]

[11, 13, 15, 17, 19]

 

·       Tylko liczby podzielne przez 3 lub 5:

 

>>> [x for x in range(1,20) if not (x%3) or not (x%5)]

[3, 5, 6, 9, 10, 12, 15, 18]

 

·        Tabela kodowa ASCII tylko dla samogłosek:

 

>>> [(x, ord(x)) for x in "ABCDEF" if x in "AEIOUY"]

[('A', 65), ('E', 69)]

 

Postać rozszerzona pozwala tworzyć nową listę w oparciu o więcej niż jedną istniejącą listę; ma następującą składnię:

 [wyrażenie for zmienna1 in sekwencja1

 for zmienna2 in sekwencja2

 ... ]

Przykłady:

·       Pary każdy element z każdym:

 

>>> [(x,y) for x in range(1,5)

 for y in range(4,0,-1)]

[(1, 4), (1, 3), (1, 2), (1, 1), (2, 4), (2, 3), (2, 2), (2, 1), (3, 4), (3, 3), (3, 2), (3, 1), (4, 4), (4, 3), (4, 2), (4, 1)]

 

·       Różnica między wartością z pierwszej i drugiej listy:

 

>>> [x-y for x in range(1,5)

 for y in range(4,0,-1)]

[-3, -2, -1, 0, -2, -1, 0, 1, -1, 0, 1, 2, 0, 1, 2, 3]

 

·       Sklejenie napisu z wartości pochodzących z trzech list:

 

>>> [`x`+y+`z` for x in [1,2]

 for y in ['A','B']

 for z in [0,3] ]

['1A0', '1A3', '1B0', '1B3', '2A0', '2A3', '2B0', '2B3']

 

Postać rozszerzona z jednym warunkiem pozwala na określenie pojedynczego warunku, który muszą spełniać dane kwalifikujące się na listę wynikową. Jej składnia jest następująca:

[wyrażenie for zmienna1 in sekwencja1

 for zmienna2 in sekwencja2

 ...

 if warunek ]

Przykłady:

·       Pary każdy element z każdym, tylko jeżeli pierwszy element jest mniejszy od drugiego:

 

>>> [(x,y) for x in range(1,5)

 for y in range (6,3,-1)

 if x<y]

[(1, 6), (1, 5), (1, 4), (2, 6), (2, 5), (2, 4), (3, 6), (3, 5), (3, 4), (4, 6), (4, 5)]

 

·       Pary każdy element z każdym, tylko jeżeli suma elementów jest mniejsza od 7:

 

>>> [(x,y) for x in range(1,5)

 for y in range (6,3,-1)

 if x+y<7]

[(1, 5), (1, 4), (2, 4)]

 

·       Pary każdy element z każdym, pod warunkiem, że pierwszy element jest parzysty, lub drugi jest nieparzysty:

 

>>> [(x,y) for x in range(1,5)

 for y in range (6,2,-1)

 if not (x%2) or y%2]

[(1, 5), (1, 3), (2, 6), (2, 5), (2, 4), (2, 3), (3, 5), (3, 3), (4, 6), (4, 5), (4, 4), (4, 3)]

 

Postać rozszerzona z wieloma warunkami pozwala na określenie warunków, które muszą spełniać dane pobierane z poszczególnych list źródłowych. Jej składnia jest następująca:

 [wyrażenie

 for zmienna1 in sekwencja1 if warunek1

 for zmienna2 in sekwencja2 if warunek2

 ... ]

Przykład:

·       Pary każdy element z każdym, pod warunkiem, że pierwszy element jest parzysty a drugi jest nieparzysty (z pierwszej listy bierzemy tylko elementy parzyste, a z drugiej – nieparzyste):

 

>>> [(x,y) for x in range(1,5) if not (x%2)

 for y in range (6,2,-1) if y%2]

[(2, 5), (2, 3), (4, 5), (4, 3)]

 

W Pythonie dostępnych jest pięć funkcji, których przeznaczeniem jest ułatwienie przetwarzania sekwencji danych. Pierwszą z nich jest funkcja apply, której działanie polega na wywołaniu funkcji z parametrami uzyskanymi z rozpakowania sekwencji (jest zatem identyczne z poprzedzeniem nazwy sekwencji gwiazdką, jak zostało to omówione w podrozdziale 5.2). Przykład użycia:

 

>>> dziel=lambda x,y,z: (x+y)/z

>>> dziel(3,5,2)

4

>>> xyz=(3,5,2)

>>> apply(dziel,xyz)

4

 

Funkcja map działa inaczej: pozwala wywołać określoną funkcję dla każdego elementu sekwencji z osobna. Zwraca listę rezultatów funkcji, o takiej samej długości jak listy parametrów. Przykłady użycia:

 

>>> map(lambda x: x*x, range(5))

[0, 1, 4, 9, 16]

>>> map(dziel, range(5), range(5), [2]*5)

[0, 1, 2, 3, 4]

 

W pierwszym z powyższych przykładów użyto funkcji jednoparametrowej (kwadratu), pobierając parametry z pojedynczej listy. W drugim użyto funkcji trójparametrowej (zdefiniowana wcześniej dziel), jej pierwszy parametr pobierany jest z pierwszej listy, drugi – z drugiej, a trzeci – z trzeciej.

Funkcja zip służy do konsolidacji danych, tj. operacji łączenia kilku list w jedną, w której wartość pojedynczego elementu listy wynikowej zależy od wartości pojedynczych elementów list źródłowych. Funkcja zip przyjmuje jako swoje parametry jedną lub więcej sekwencji, po czym zwraca listę krotek, których poszczególne elementy pochodzą z poszczególnych sekwencji.

 

>>> zip("abcdef",[1,2,3,4,5,6])

[('a', 1), ('b', 2), ('c', 3), ('d', 4), ('e', 5), ('f', 6)]

>>> zip(range(1,10),range(9,0,-1))

[(1, 9), (2, 8), (3, 7), (4, 6), (5, 5), (6, 4), (7, 3), (8, 2), (9, 1)]

 

W przypadku, gdy długości sekwencji są różne, wynikowa sekwencja jest skracana do najkrótszej spośród nich:

 

>>> zip("zip",range(0,9),zip(range(0,9)))

[('z', 0, (0,)), ('i', 1, (1,)), ('p', 2, (2,))]

 

Funkcja filter służy do filtrowania danych. Przyjmuje jako parametry funkcję oraz sekwencję, po czym zwraca sekwencję zawierającą te elementy sekwencji wejściowej, dla których funkcja zwróciła wartość logiczną True.

Tak na przykład filtruje się samogłoski:

 

>>> samogloska=lambda x: x.lower() in 'aeiou'

>>> samogloska('A')

True

>>> samogloska('z')

False

>>> filter(samogloska,"Ala ma kota, kot ma Ale")

'AaaoaoaAe'

 

Tak wszystkie inne znaki:

 

>>> filter(lambda x: not samogloska(x),"Ala ma kota, kot ma Ale")

'l m kt, kt m l'

 

A tak liczby parzyste:

 

>>> filter(lambda x: x%2-1, range(0,11))

[0, 2, 4, 6, 8, 10]

 

Funkcja reduce służy do agregowania danych, tj. operacji obliczenia pojedynczego wyrażenia, zależnego od wszystkich elementów listy źródłowej. Funkcja reduce przyjmuje jako parametry funkcję oraz sekwencję, zwraca pojedynczą wartość.

Na początek wykonuje funkcję dla dwóch pierwszych elementów sekwencji, następnie wykonuje funkcję dla otrzymanego w pierwszym kroku rezultatu i trzeciego elementu sekwencji, następnie wykonuje funkcję dla otrzymanego w drugim kroku rezultatu i czwartego elementu sekwencji, itd., aż dojdzie do końca sekwencji.

Np.: suma elementów:

 

>>> reduce(lambda x,y: x+y, [1,2,3])

6

 

Np.: iloczyn elementów:

 

>>> reduce(lambda x,y: x*y, [1,2,3,4])

24

 

Np.: suma kwadratów elementów:

 

>>> reduce(lambda x,y: x+y, map(lambda x: x*x, range(1,10)))

285

 

Na poniższym przykładzie zobaczymy, jak łączyć stosowanie poznanych tu konstrukcji.

Przykład. Dane są cztery listy: r1, r2, r3 i r4 liczące po 12 elementów. Zawierają one wartości miesięcznej sprzedaży przez kolejne cztery lata w pewnej firmie. Oblicz:

1.     Sumę sprzedaży dla poszczególnych lat

2.     Sumę sprzedaży w poszczególnych miesiącach przez cztery lata

3.     Średnią sprzedaż miesięczną przez cztery lata

Rozwiązanie. Na początek przygotujemy losowe dane wejściowe.

 

>>> from random import *

>>> seed(2006)

>>> r1=[randint(20,50) for i in range(12)]

>>> r2=[randint(20,50) for i in range(12)]

>>> r3=[randint(20,50) for i in range(12)]

>>> r4=[randint(20,50) for i in range(12)]

>>> r1;r2;r3;r4

[37, 22, 48, 30, 37, 22, 27, 33, 25, 37, 44, 26]

[41, 26, 29, 31, 28, 34, 32, 44, 25, 40, 43, 40]

[38, 26, 23, 23, 34, 36, 32, 38, 36, 48, 40, 34]

[38, 39, 34, 48, 26, 50, 34, 33, 50, 20, 48, 41]

 

Ad. 1. Aby wyliczyć sumę sprzedaży dla poszczególnych lat posłużymy się funkcją reduce:

 

>>> reduce(lambda x,y:x+y,r1)

388

 

W powyższy sposób zagregowaliśmy listę elementów r1 do ich sumy. Aby wyliczyć sumę sprzedaży dla wszystkich lat, posłużymy się dodatkowo funkcją map:

 

>>> map(reduce,[lambda x,y:x+y]*4,[r1,r2,r3,r4])

[388, 413, 408, 461]

 

Wywoła ona funkcję reduce każdorazowo dla funkcji sumującej (zwróćmy uwagę w jaki sposób ją powieliliśmy, by odpowiadała liczbie lat) i danych z kolejnego roku.

Ad. 2. Aby zestawić ze sobą dane o sprzedaży w poszczególnych miesiącach dla wszystkich lat użyjemy funkcji zip:

 

>>> zip(r1,r2,r3,r4)

[(37, 41, 38, 38), (22, 26, 26, 39), (48, 29, 23, 34), (30, 31, 23, 48), (37, 28, 34, 26), (22, 34, 36, 50), (27, 32, 32, 34), (33, 44, 38, 33), (25, 25, 36, 50), (37, 40, 48, 20), (44, 43, 40, 48), (26, 40, 34, 41)]

 

Aby wyliczyć sumę sprzedaży miesięcznej dla wszystkich lat, posłużymy się znaną już nam kombinacją funkcji reduce i map:

 

>>> map(reduce,[lambda x,y:x+y]*12, zip(r1,r2,r3,r4))

[154, 113, 134, 132, 125, 142, 125, 148, 136, 145, 175, 141]

 

Ad. 3. Aby wyliczyć średnią sprzedaż miesięczną przez cztery lata, posłużymy się ponownie funkcją map:

 

>>> map(lambda x: x/4.0, map(reduce,[lambda x,y:x+y]*12, zip(r1,r2,r3,r4)))

[38.5, 28.25, 33.5, 33.0, 31.25, 35.5, 31.25, 37.0, 34.0, 36.25, 43.75, 35.25]

 

Jedną z częściej wykonywanych na listach operacji jest ich porządkowanie (sortowanie i odwracanie kolejności). Przypomnijmy metodę list sort:

 

>>> l=[3,2,5,7]

>>> l.sort()

>>> l

[2, 3, 5, 7]

 

            Jak widać, standardowo porządkuje ona elementy od najmniejszego do największego. Metoda sort posiada jednak parametr reverse, ustawienie którego wartości na True pozwala zmienić porządek sortowania:

 

>>> l=[3,2,5,7]

>>> l.sort(reverse=True)

>>> l

[7, 5, 3, 2]

 

            W pewnych przypadkach, problem, który mamy z sortowaniem jest znacznie bardziej skomplikowany niż zmiana kolejności. Załóżmy, że mamy listę wyrazów, którą chcielibyśmy posortować alfabetycznie:

 

>>> L=["Ala","Ola","pies","dziadek","Tola","smyk"]

>>> L.sort()

>>> L

['Ala', 'Ola', 'Tola', 'dziadek', 'pies', 'smyk']

 

            Jak widać, standardowe sortowanie nie jest poprawne, gdyż umieszcza wszystkie wyrazy pisane z dużej litery przed tymi pisanymi z małej. Może w tym pomóc parametr key, pozwalający określić funkcję, która skonwertuje dane do postaci zapewniającej prawidłowy rezultat porównania. W tym przypadku chodzi o sprowadzenie wszystkich wyrazów do małych liter – użyjemy zatem metody lower klasy str (jak widać, metody możemy wywoływać łącząc ich nazwy nie tylko z nazwami konkretnych obiektów, ale także z nazwą samej klasy – sam obiekt przekazany zaś zostanie jako pierwszy parametr metody):

 

>>> L=["Ala","Ola","pies","dziadek","Tola","smyk"]

>>> L.sort(key=str.lower)

>>>

>>> L

['Ala', 'dziadek', 'Ola', 'pies', 'smyk', 'Tola']

 

            Inny przykład wykorzystania parametru key to sortowanie liczb zapisanych jako napisy. Domyślnie są one sortowane jako ciągi cyfr, co daje porządek leksykograficzny, a nie odpowiadający wartościom liczb:

 

>>> L=["11","2","20","7","55"]

>>> L.sort()

>>> L

['11', '2', '20', '55', '7']

 

            Aby uzyskać sortowanie według wartości, wystarczy skonwertować napisy na liczby używając funkcji int:

 

>>> L=["11","2","20","7","55"]

>>> L.sort(key=int)

>>> L

['2', '7', '11', '20', '55']

 

            Zauważmy, że parametr key jest w istocie funkcją (funkcje są zatem specyficznym typem danych, tzw. typem proceduralnym). Taką sytuację (wywołanie z funkcji innej funkcji, przekazanej do niej jako parametr) nazywamy wywołaniem zwrotnym (ang. callback).

            Parametryzacja metody sort idzie jeszcze dalej, pozwalając podmienić całą funkcję wykonującą porównanie. Domyślnie jest to funkcja cmp; podmieniona funkcja musi tak samo jak cmp zwracać 0 dla dwóch parametrów równych sobie oraz 1 lub -1 w przypadku gdy zachodzi nierówność.

 

>>> cmp(1,2)

-1

>>> cmp(2,2)

0

>>> cmp(3,2)

1

 

            Sortowanie liczb zapisanych jako napisy mogłoby wyglądać więc tak:

 

>>> def porownaj(x,y):

    return cmp(int(x), int(y))

 

>>> L=["11","2","20","7","55"]

>>> L.sort(cmp=porownaj)

>>> L

['2', '7', '11', '20', '55']

 

            Funkcję porownaj zdefiniowaliśmy po to, by wykorzystać ją w jednym tylko miejscu. Python pozwala uniknąć definicji takich funkcji jednorazowego użytku dzięki wyrażeniu lambda. Wyrażenie to ma postać lambda argumenty: wyrażenie, a jego rezultatem jest anonimowa funkcja (którą można od razu wykonać, przekazać jako parametr, lub zapamiętać w zmiennej – tym samym nadając jej nazwę).

Zamiast definiować funkcję porownaj moglibyśmy napisać:

 

>>> L=["11","2","20","7","55"]

>>> L.sort(cmp=lambda x,y: cmp(int(x), int(y)))

>>> L

['2', '7', '11', '20', '55']

 

Wyrażeń lambda można oczywiście używać w każdej sytuacji, w której moglibyśmy użyć na ich miejscu funkcji, np.:

 

>>> print "%.2f" % (lambda x,y: x**y)(2,0.5)

1.41

 

Podstawową wadą wyrażeń lambda to niemożność wykorzystania w nich instrukcji nie będących wyrażeniami, np. print, if, for, while, itp. – choć istnieją sprytne sposoby na obejście tego problemu. Jakkolwiek wyrażenia lambda bywają wygodne, nie należy ich nadużywać, bo prowadzi to do nieprzejrzystego kodu źródłowego.

Jeszcze jeden przykład na porównywanie, tym razem sekwencji:

 

>>> L=[ ("Adam",15), ("Bogdan",19), ("Ala",17), ("Zenobia", 14) ]

>>> L.sort()

>>> L

[('Adam', 15), ('Ala', 17), ('Bogdan', 19), ('Zenobia', 14)]

 

            Jak pamiętamy, porównywanie sekwencji polega na porównaniu między sobą pierwszych ich elementów, tylko gdy są równe – drugich, itd. Załóżmy, że powyższą listę chcielibyśmy posortować według lat, nie imion. Można to zrobić następująco (parametr cmp jest pierwszym parametrem metody sort, jego wartość może więc być podawana bez nazwy):

 

>>> L.sort(lambda x,y: cmp(x[1],y[1]))

>>> L

[('Zenobia', 14), ('Adam', 15), ('Ala', 17), ('Bogdan', 19)]

 

Jak widać, elementy listy są teraz ułożone według rosnącego wieku (drugiego elementu krotki).

 

Ćwiczenie 1. Używając wytwornika zbuduj listę zawierającą wszystkie liczby podzielne przez 3 z zakresu od 1 do 33. Następnie:

·       Używając funkcji filter usuń z niej wszystkie liczby parzyste

·       Używając wyrażenia lambda i funkcji map podnieś wszystkie elementy tak otrzymanej listy do sześcianu

·       Odpowiednio używając funkcji reduce i len oblicz średnią arytmetyczną z elementów tak otrzymanej listy.

Ćwiczenie 2. Stwórz trzy listy zawierające po 5 elementów: nazwiska – z nazwiskami pracowników, godziny – z liczbą przepracowanych godzin, stawka – ze stawką w złotych za godzinę pracy. Wykorzystując funkcje zip, map, reduce i filter (oraz, ewentualnie, wytworniki list) wyświetl nazwiska i wypłaty (iloczyn stawki godzinowej i liczby przepracowanych godzin) tych pracowników, którzy zarobili więcej, niż wyniosła średnia wypłata.