TI/Programowanie dla Fizyków Medycznych:Struktury danych:Listy

Listy przechowują dane w określonej sekwencji i można je modyfikować w miejscu. Listy mogą przechowywać elementy różnych typów jak i struktury danych.

Tworzenie listy polega na podaniu jej elementów oddzielonych przecinkiem w nawiasach kwadratowych:

A = [5, 3.22, 'napis', "AKIA", ['a', 2, 5], {'Ala' : 5, 6 : 'Kot', (1, 2, 3) : 'Smok'}, ('Krowa', 5)]

Można stworzyć pustą listę:

A = []

Listę można również stworzyć z dowolnej sekwencji czy obiektu po którym można się iterować za pomocą funkcji wbudowanej list:

>>> A = list((1, 2, 3))
>>> A
[1, 2, 3]
>>> A = list("Ala ma kota")
>>> A
['A', 'l', 'a', ' ', 'm', 'a', ' ', 'k', 'o', 't', 'a']
>>> A = list({'a' : 2, 'b' : 3})
>>> A
['a', 'b']
>>> A = list({'a' : 2, 'b' : 3}.iteritems())
>>> A
[('a', 2), ('b', 3)]
>>> A = list({'a' : 2, 'b' : 3}.itervalues())
>>> A
[2, 3]

Do elementów listy dostajemy się dzięki indeksom, zatem aby odczytać k-ty element listy należy napisać:

A[k]

a aby coś na nim zapisać:

A[k] = 5

W Pythonie elementy listy indeksuje się od 0.

Należy pamiętać, że próba odczytu lub zapisu elementu poza listą skutkuje zgłoszeniem wyjątku:

>>> A[100]

Traceback (most recent call last):
  File "<pyshell#8>", line 1, in <module>
    A[100]
IndexError: list index out of range
>>> A[100] = 5

Traceback (most recent call last):
  File "<pyshell#9>", line 1, in <module>
    A[100] = 5
IndexError: list assignment index out of range

Przy pomocy wycinków można odczytywać wiele elementów na raz (wycinki zwracają nową listę zawierającą pożądane elementy listy pierwotnej), składnia wycinka:

A[a:b:c]

zwraca listę elementów listy A poczynając od elementu o indeksie a, kończąc na elemencie o indeksie b (ale bez niego) ze skokiem c. Parametr c jest opcjonalny i domyślnie przyjmowana jest wartość 1 (można też pominąć drugi dwukropek). Parametry a i b mogą być ujemne - wtedy pozycja liczona jest od końca listy, zatem -1 oznacza ostatni element, -2 przedostatni itd. (od ujemnych wartości dodawana jest długość listy). Jeśli a odpowiada elementowi późniejszemu na liście niż b, a c jest ujemne to wypisywane są elementy od a do b (bez niego) z krokiem |c|. Parametry a i b też mogą być pominięte, domyślnie przyjmowane jest a = 0 i b = długość listy (dla c > 0) i a = długość listy i b = element przed pierwszym elementem (nie da się tego opisać) (dla c < 0). Jeśli parametry wycinek zwraca listę pustą jeśli parametry a, b i c nie wskazują na żaden element. Sprawdź czy rozumiesz wszystkie przytoczone poniżej przykłady:

>>> A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> A[0:5:2]
[0, 2, 4]
>>> A[0:5]
[0, 1, 2, 3, 4]
>>> A[0:5:]
[0, 1, 2, 3, 4]
>>> A[3:-2]
[3, 4, 5, 6, 7, 8]
>>> A[-7:-3]
[4, 5, 6, 7]
>>> A[-3:-7:-1] #Zauważ, że nie jest odwróceniem poprzedniego
[8, 7, 6, 5]
>>> A[-4:-8:-1]
[7, 6, 5, 4]
>>> A[5:3:-1]
[5, 4]
>>> A[-3:-7:-2]
[8, 6]
>>> A[:7:3]
[0, 3, 6]
>>> A[3::3]
[3, 6, 9]
>>> A[::3]
[0, 3, 6, 9]
>>> A[:3]
[0, 1, 2]
>>> A[::-3]
[10, 7, 4, 1]
>>> A[:-3]
[0, 1, 2, 3, 4, 5, 6, 7]
>>> A[::-1] #Metoda na odwrócenie listy
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
>>> A[:] #Metoda na skopiowanie listy
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> A[3:5:-1]
[]
>>> A[5:3]
[]

Długość listy można uzyskać dzięki wbudowanej funkcji len. Rozmiar listy można zwiększać o jeden przed dopisanie na końcu listy elementu przy pomocy metody append, albo doklejenie sekwencji przy pomocy extend, można także wstawiać element pod dowolny indeks przy pomocy metody insert na zadaną pozycję przesuwając wszystkie dalsze o jedno miejsce w prawo:

>>> A = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
>>> len(A)
11
>>> A.append(11)
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
>>> A.extend((15, 16))
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
>>> A.extend("ala")
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'a', 'l', 'a']
>>> A.append("ala")
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala']
>>> A.append([12, 13])
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala', [12, 13]]
>>> A.append((12, 13))
>>> A
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala', [12, 13], (12, 13)]
>>> A.insert(3, "X") #Pierwszy parametr jest pozycją na którą chcemy wstawić, a drugi elementem do wstawienia
>>> A
[0, 1, 2, 'X', 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala', [12, 13], (12, 13)]

W listach można podmieniać wycinki (jeśli trzeci parametr wycinka nie został podany, lub jest równy 1, to to co chcemy wstawić może mieć inną długość niż wycinek (można to wykorzystać do kasowania elementów listy), w przeciwnym wypadku długości muszą być zgodne):

>>> A
[0, 1, 2, 'X', 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala', [12, 13], (12, 13)]
>>> A[0:5] = ["X", "Y", "Z"]
>>> A
['X', 'Y', 'Z', 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 'ala', [12, 13], (12, 13)]
>>> A[:12:-1] = "abcdef"
>>> A
['X', 'Y', 'Z', 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 'f', 'e', 'd', 'c', 'b', 'a']
>>> A[:12:-1] = "abcdefg"

Traceback (most recent call last):
  File "<pyshell#101>", line 1, in <module>
    A[:12:-1] = "abcdefg"
ValueError: attempt to assign sequence of size 7 to extended slice of size 6
>>> A[0:7] = []
>>> A
[8, 9, 10, 11, 12, 13, 'f', 'e', 'd', 'c', 'b', 'a']

Innymi możliwościami usuwania elementów z listy jest użycie następujących metod pop(), która zwraca i usuwa ostatni element, pop(k) - zwraca i usuwa k-ty element albo remove(elem) - usuwa pierwszy element równy elem, jeśli nie ma takiego to zwraca wyjątek, lub funkcji wbudowanej del usuwającej podane elementy:

>>> A
[8, 9, 10, 11, 12, 13, 'f', 'e', 'd', 'c', 'b', 'a']
>>> A.pop()
'a'
>>> A
[8, 9, 10, 11, 12, 13, 'f', 'e', 'd', 'c', 'b']
>>> A.pop(4)
12
>>> A
[8, 9, 10, 11, 13, 'f', 'e', 'd', 'c', 'b']
>>> A.append(11)
>>> A
[8, 9, 10, 11, 13, 'f', 'e', 'd', 'c', 'b', 11]
>>> A.remove(11)
>>> A
[8, 9, 10, 13, 'f', 'e', 'd', 'c', 'b', 11]
>>> A.remove(12)

Traceback (most recent call last):
  File "<pyshell#130>", line 1, in <module>
    A.remove(12)
ValueError: list.remove(x): x not in list
>>> del A[5]
>>> A
[8, 9, 10, 13, 'f', 'd', 'c', 'b', 11]
>>> del A[0:4]
>>> A
['f', 'd', 'c', 'b', 11]

Możliwe jest sprawdzenie czy element jest na liście przy pomocy operatora in, albo metody index. Operator in zwraca True lub False, natomiast metoda index pozycję pierwszego elementu równego zadanemu lub zgłasza wyjątek jeśli nie element nie znajdował się na liście. Do metody index można podać dwa kolejne opcjonalne parametry definiując zakres indeksów w którym należy szukać. Jeśli podamy jedną wartość to będziemy szukać wśród indeksów od podanego do końca, jeśli dwie to od pierwszego do drugiego - 1. Metoda count zliczająca elementy równe danemu:

>>> 'd' in A
True
>>> 'z' in A
False
>>> A.index('b')
3
>>> A.index('z')

Traceback (most recent call last):
  File "<pyshell#144>", line 1, in <module>
    A.index('z')
ValueError: list.index(x): x not in list
>>> A.count('c')
1
>>> A.index('d', 2) #Po elemencie o indeksie 2 nie ma już 'd'

Traceback (most recent call last):
  File "<pyshell#315>", line 1, in <module>
    A.index('d', 2)
ValueError: list.index(x): x not in list
>>> A.index('b', 2)
3
>>> A.index('b', 2, 4)
3

Często przydatne jest sortowanie list, można tego dokonać za pomocą metody sort lub funkcji wbudowanej sorted. Różnica między nimi jest znacząca, gdyż metoda sort dokonuje sortowania w miejscu (modyfikuje zadaną listę), a funkcja sorted zwraca posortowaną listę. Ponadto do obu funkcji możemy podać dwa trzy parametry opcjonalne: cmp - funkcję, która będzie używana do porównywania elementów listy (powinna zwracać -1 jeśli pierwszy element jest mniejszy 0 gdy są równe i 1 gdy drugi większy), key - funkcję, która zostanie wywołana na każdym elemencie listy i zostaną one posortowane zgodnie z wynikami tej funkcji i reverse - jeśli będzie True to lista zostanie posortowana w porządku malejącym:

>>> A = [-5, 10, -2, -1, 17, 0, 33]
>>> sorted(A)
[-5, -2, -1, 0, 10, 17, 33]
>>> sorted(A, reverse = True)
[33, 17, 10, 0, -1, -2, -5]
>>> sorted(A, cmp = lambda x,y: x % 3 < y % 3)
[-5, 10, -2, -1, 17, 0, 33]
>>> sorted(A, cmp = lambda x,y: cmp(x % 3, y % 3))
[0, 33, -5, 10, -2, -1, 17]
>>> sorted(A, key = lambda x: x % 3)
[0, 33, -5, 10, -2, -1, 17]
>>> A #Zauważ, że wielokrotne wywołanie sorted nie zmieniło wartości listy
[0, 33, -5, -2, 10, -1, 17]
>>> A.sort(reverse = True)
>>> A #Natomiast sort zmienia wartość listy
[33, 17, 10, 0, -1, -2, -5]
>>> A.sort(cmp = lambda x,y: cmp(x % 3, y % 3))
>>> A
[33, 0, 10, -2, -5, 17, -1]

Listę w odwróconym porządku można było uzyskać przy pomocy wycinków, można tez tego dokonać za pomocą funkcji wbudowanej reversed i metody reverse. Funkcja reversed zwraca jednak iterator, aby na jego podstawie stworzyć listę należy użyć funkcji wbudowanej list:

>>> A
[1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> A[::-1]
[9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> reversed(A)
<listreverseiterator object at 0xb6eb528c>
>>> list(reversed(A))
[9, 8, 7, 6, 5, 4, 3, 2, 1]
>>> A.reverse()
>>> A
[9, 8, 7, 6, 5, 4, 3, 2, 1]

Należy zwrócić szczególną uwagę na fakt, że zmienne w Pythonie są referencjami do miejsc w pamięci i nie mają one określonych typów. Informacje o typach są trzymane w pamięci razem z "wartościami" obiektów. Przechowywana jest również liczba referencji do danego obiektu, a gdy obiekt jest już nieosiągalny przez referencje jest on usuwany z pamięci. Dzięki temu nie musimy troszczyć się o wycieki pamięci (np. w C czy C++ można było zaalokować pamięć, a następnie stracić do niej dostęp, co sprawiało, że, aż do zakończenia działania programu nie można było jej zwolnić i ponownie wykorzystać). Należy też rozróżniać równość dwóch zmiennych i ich tożsamość, czyli sprawdzanie czy wskazują na dokładnie ten sam obiekt. Tożsamość jest sprawdzana operatorem is, a równość ==. Fakt, że zmienne są referencjami pociąga za sobą czasami konieczność kopiowania list, rozważmy poniższy przykład:

>>> A = [1, 2, 3]
>>> B =  A #B wskazuje na to samo miejsce w pamięci co A
>>> C = A[:] #C jest kopią, A, zatem jest równe, ale nie jest tym samym co A
>>> B == A
True
>>> C == A
True
>>> B is A
True
>>> C is A
False
>>> A[2] = 'X'
>>> del A[1]
>>> A
[1, 'X']
>>> B
[1, 'X']
>>> C
[1, 2, 3]

Listy można porównywać operatorami <, <=, >, >=, ==, != i is:

>>> A = [1, 2, 3]
>>> B = [1, 2, 5]
>>> B > A
True
>>> C = [1, 2, 3, 4]
>>> C > A
True
>>> B <= C
False

Na przykładzie list można też zaobserwować polimorfizm w Pythonie, otóż operacje dodawania i mnożenia przez liczbę są przedefiniowane dla list i dodawanie dwóch list to ich konkatenacja, a mnożenie przez liczbę to wielokrotna konkatenacja zadanej listy. Dostępne są także operatory skrócone += i *=. Dzięki temu możemy w łatwy sposób przygotować listę odpowiedniej długości do dalszego wykorzystania:

>>> A
[1, 2, 3]
>>> B
[1, 2, 5]
>>> A + B
[1, 2, 3, 1, 2, 5]
>>> A * 3
[1, 2, 3, 1, 2, 3, 1, 2, 3]
>>> 3 * A
[1, 2, 3, 1, 2, 3, 1, 2, 3]
>>> A = [None] * 100
>>> A
[None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None, None]
>>> A += B
>>> A
[1, 2, 3, 1, 2, 5]
>>> A *= 2
>>> A
[1, 2, 3, 1, 2, 5, 1, 2, 3, 1, 2, 5]

Do znajdywania najmniejszego i największego elementu służą funkcje wbudowane min i max, można do nich podać opcjonalny argument key, który działa analogicznie jak w sort, sumę elementów można obliczyć za pomocą funkcji sum, można jej podać argument wskazujący początkową wartość:

>>> A
[-1, 2, -5, 10]
>>> min(A)
-5
>>> max(A)
10
>>> min(A, key = lambda x: 1./abs(x))
10
>>> max(A, key = lambda x: 1./abs(x))
-1
>>> sum(A)
6
>>> sum(A, 100)
106

Do generowania list ciągów arytmetycznych przydatna jest funkcja wbudowana range(a, b, c) - zwraca ona listę od a do b - 1 z krokiem c, c może być ujemne, jeśli podamy tylko jeden parametr to otrzymamy listę od 0 do a - 1:

>>> range(5)
[0, 1, 2, 3, 4]
>>> range(2, 6)
[2, 3, 4, 5]
>>> range(2, 15, 3)
[2, 5, 8, 11, 14]
>>> range(15, 2, -3)
[15, 12, 9, 6, 3]

Do łączenie elementów listy w napis można użyć funkcji join z biblioteki string, a do dzielenia napisu funkcji split. Do obu można podać separator jeśli się go nie poda to przyjmowany jest domyślnie biały znak:

>>> A = ['Ala', 'ma' , 'kota']
>>> napis = "Ala;ma;kota"
>>> import string
>>> string.join(A, ' : ')
'Ala : ma : kota'
>>> string.split(napis, ';')
['Ala', 'ma', 'kota']
>>> string.join(A)
'Ala ma kota'
>>> napis2 = "Ala\tma kota\na nawet dwa"
>>> print napis2
Ala	ma kota
a nawet dwa
>>> string.split(napis2)
['Ala', 'ma', 'kota', 'a', 'nawet', 'dwa']

Z sekwencjami wiążą się też elementy programowania funkcyjnego dostępne w Pythonie. Funkcja wbudowana filter pozwala wybrać z sekwencji elementy dla których zadana funkcja zwraca True. Z kolei funkcja map oblicza wyniki zadanej funkcji dla wszystkich elementów sekwencji i zwraca sekwencję wyników. Funkcja zadana w map może przyjmować wiele argumentów, wtedy należy podać tyle list ile argumentów i z kolejnych list brane są kolejne argumenty funkcji, gdy któraś lista się skończy to podstawiane jest None. Funkcja reduce przyjmuje funkcję dwuargumentową zwracającą pojedynczą wielkość i wywołuje ją kolejno dla dwóch pierwszych elementów sekwencji, a później dla wyniku i następnego elementu sekwencji i tak aż do skończenia sekwencji uzyskując ostatecznie pojedynczą wartość. Do funkcji reduce można zadać początkową wartość, wtedy pierwsze obliczenie jest wykonywane dla tej wartości i pierwszego elementu sekwencji:

>>> A = [-1, 2, -5, 10]
>>> filter(lambda x: x > 0, A)
[2, 10]
>>> map(lambda x: x**2, A)
[1, 4, 25, 100]
>>> B = [1, 2, 3]
>>> map(lambda x, y: str(x) + str(y), A, B)
['-11', '22', '-53', '10None']
>>> reduce(lambda x, y: x + y, A)
6
>>> reduce(lambda x, y: x + y, A, 200)
206

Bardzo ciekawym sposobem tworzenia list są listy składane, podaje się w nich wyrażenie reprezentujące elementy tworzonej listy, może zawierać ono wiele zmiennych, następnie dla każdej zmiennej definiuje się sekwencję z której ona pochodzi i ewentualnie warunki:

>>> A
[-1, 2, -5, 10]
>>> B
[1, 2, 3]
>>> [x**2 for x in A]
[1, 4, 25, 100]
>>> [x + y for x in A for y in B] #Zauważ, że wyniki są obliczane dla każdego elementu iloczynu kartezjańskiego
[0, 1, 2, 3, 4, 5, -4, -3, -2, 11, 12, 13]
>>> [x + y for x in A for y in B if x > y]
[3, 11, 12, 13]

Do przeglądania sekwencji można wykorzystać pętlę for, przydatna bywa też funkcja enumerate(A), zwracająca listę krotek (indeks, A[indeks]), gdzie A to sekwencja, a indeks przebiega od 0 do len(A) - 1 i funkcja zip, której podaje się kilka sekwencji i zwraca ona listę krotek, których kolejne elementy pochodzą z kolejnych sekwencji, długość wynikowej listy jest równa długości najkrótszej listy:

>>> A = [-1, 2, -5, 10]
>>> B = [0, 1]	
>>> for x in A:
	print x
-1
2
-5
10
>>> for i, x in enumerate(A):
	print i, ' ', x
0   -1
1   2
2   -5
3   10
>>> for (x, y) in zip(A, B):
	print x + y
-1
3

Na koniec parę słów o efektywności list. Dostęp do elementu po indeksie, wstawianie jak i usuwanie elementu z końca listy to operacje wykonywane w czasie stałym (niezależnym od długości listy), dzięki temu listy dobrze nadają się do implementowania stosu (kolejki FILO - First In Last Out, struktury danych w której elementy kładziemy na górze stosu i tylko z góry możemy je zdejmować). Z kolei dodawanie i usuwanie elementów z innych pozycji wymaga już przesunięcia wszystkich elementów występującym po danym, co sprawia, że listy nie nadają się do implementacji kolejek FIFO - First In First Out, do takich zadań można wykorzystać strukturę deque z biblioteki collections, w niej dodawanie i usuwanie z obu końców wykonywane jest w czasie stałym.