0 dní v řadě · 0 bodů

Datové struktury · 22 min

Seznamy

Uložíš libovolně mnoho hodnot pod jedno jméno a naučíš se je přidávat, mazat, procházet a řadit.

Hloubka
Úkoly
Lidsky řečeno

Nákupní lístek. Jeden papír, na něm položky pod sebou v pořadí, jak tě napadly. Můžeš připsat další, škrtnout mléko nebo celý lístek přepsat podle uliček v obchodě. Seznam v Pythonu je ten samý lístek: jedno jméno, uvnitř kolik chceš hodnot a záleží na jejich pořadí.

Proč nestačí proměnné

Každé ráno si na chatě zapisuješ teplotu. S tím, co zatím umíš, by každý den potřeboval vlastní proměnnou: pondeli, utery, streda. Vzorec na průměr by se s každým dnem prodlužoval a po měsíci bys program nejradši smazal.

Seznam (anglicky list) drží hodnoty pohromadě. Píše se do hranatých závorek, hodnoty odděluje čárka a každé z nich se říká prvek.

teploty = [4, 7, 6, 2, 9]

print(teploty)
print(len(teploty))
print(sum(teploty) / len(teploty))
Výstup
[4, 7, 6, 2, 9]
5
5.6

Funkce len vrátí počet prvků a sum je sečte. Přidáš šestý den a řádek s průměrem nemusíš vůbec měnit. Program přestane záviset na tom, kolik dat zrovna máš.

Do seznamu patří cokoli, i texty nebo další seznamy. Prázdný seznam se píše [] a je to běžný začátek, do kterého se postupně přidává.

Sáhni pro konkrétní prvek

Každý prvek má pořadové číslo, index. Počítá se od nuly, takže první prvek má index 0 a poslední o jedna méně, než je délka seznamu.

text
index:     0       1       2       3
prvek:  "Anna"  "Petr"  "Eva"   "Jan"

Index se píše do hranatých závorek za jméno seznamu. Stejným zápisem prvek přečteš i přepíšeš. Záporný index počítá od konce, -1 je poslední prvek.

fronta = ["Anna", "Petr", "Eva", "Jan"]

print(fronta[0])
print(fronta[2])
print(fronta[-1])

fronta[1] = "Marek"
print(fronta)
Výstup
Anna
Eva
Jan
['Anna', 'Marek', 'Eva', 'Jan']

Když sáhneš mimo seznam, Python to nepřejde mlčky a skončí chybou IndexError.

fronta = ["Anna", "Petr", "Eva"]

print(len(fronta))
print(fronta[3])
Výstup
3

Přidávání a mazání

Seznam umí sám pár věcí. Říká se jim metody: funkce přilepené k hodnotě, které se volají přes tečku. Většina metod seznamu mění přímo ten seznam, na kterém je zavoláš.

nakup = ["mléko", "chleba"]

nakup.append("vejce")        # add to the end
print(nakup)

nakup.insert(0, "káva")      # add at index 0
print(nakup)

nakup.remove("chleba")       # remove by value
print(nakup)

posledni = nakup.pop()       # take the last item out
print(posledni, nakup)

prvni = nakup.pop(0)         # take the item at index 0 out
print(prvni, nakup)
Výstup
['mléko', 'chleba', 'vejce']
['káva', 'mléko', 'chleba', 'vejce']
['káva', 'mléko', 'vejce']
vejce ['káva', 'mléko']
káva ['mléko']

Rozdíl mezi remove a pop: remove hledá hodnotu a smaže její první výskyt, pop bere pozici a vyňatý prvek ti vrátí, takže s ním můžeš dál pracovat. Když hodnota v seznamu není, remove skončí chybou ValueError.

Seznamy jde spojit dvěma způsoby. extend přidá prvky druhého seznamu jeden po druhém. Operátor + vyrobí seznam nový a původní nechá být. Nepleť si s nimi append: ten přidá vždy jeden prvek, i kdyby to byl celý seznam.

a = [1, 2]
a.append([3, 4])
print(a)

b = [1, 2]
b.extend([3, 4])
print(b)

c = b + [5]
print(c)
print(b)
Výstup
[1, 2, [3, 4]]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[1, 2, 3, 4]
Kvíz

Co bude v a po řádcích a = [1, 2] a a.append([3])?

Úkol

Čekárna u lékaře

V čekárně sedí tři lidé. Proveď změny v tomto pořadí přímo na seznamu cekarna:

  1. Na konec přišla paní "Černá".
  2. Sestra zavolala prvního v řadě. Vyjmi ho ze seznamu a ulož do proměnné na_rade.
  3. S úrazem přišla paní "Procházková" a jde úplně dopředu.
cekarna = ["Novák", "Svoboda", "Dvořák"]

# doplň
Výstup
Spoj dvojice

Co která metoda dělá

Spoj metodu seznamu s tím, co udělá.

Projdi všechno cyklem

Cyklus for umí procházet i seznam. Proměnná dostane postupně každý prvek. Často přitom něco sčítáš nebo si do nového seznamu vybíráš, co tě zajímá.

utraty = [120, 89, 1450, 35, 640]

celkem = 0
velke = []

for castka in utraty:
    celkem += castka
    if castka > 500:
        velke.append(castka)

print(celkem)
print(velke)
Výstup
2334
[1450, 640]

Když kromě prvku potřebuješ i jeho pořadí, použij enumerate, který znáš z lekce o cyklu for. Operátor in zjistí, jestli v seznamu hodnota je, count spočítá výskyty a index najde první pozici. Když tam hodnota není, index skončí chybou ValueError.

zavodnici = ["Eva", "Tomáš", "Lída", "Eva"]

for poradi, jmeno in enumerate(zavodnici, start=1):
    print(f"{poradi}. {jmeno}")

print("Lída" in zavodnici)
print("Karel" in zavodnici)
print(zavodnici.count("Eva"))
print(zavodnici.index("Lída"))
Výstup
1. Eva
2. Tomáš
3. Lída
4. Eva
True
False
2
2
Úkol

Vadné čidlo

Čidlo při poruše posílá hodnotu -999. Ze seznamu mereni vytvoř:

  • platna: nový seznam bez hodnot -999, ve stejném pořadí,
  • poruchy: kolikrát se porucha objevila,
  • prumer: průměr platných hodnot.

Původní seznam mereni nech beze změny.

mereni = [21, -999, 23, 22, -999, 25]

# doplň
Výstup

Tipni si, co vypíše tenhle kód, a potom ho projdi tlačítkem krokovat.

cisla = [1, 2, 2, 3]

for c in cisla:
    if c == 2:
        cisla.remove(c)

print(cisla)
Výstup
[1, 2, 3]

Jedna dvojka přežila. Cyklus smazal prvek na pozici 1, druhá dvojka se tím na pozici 1 přesunula a cyklus pokračoval pozicí 2. Bezpečná cesta je ta z minulého úkolu: vytvořit nový seznam jen s tím, co chceš nechat.

Řazení

Řadit jde dvěma způsoby. Metoda sort přeskládá přímo seznam. Funkce sorted ho nechá být a vrátí nový, seřazený. reverse=True otočí směr. Když chceš jen nejmenší nebo největší hodnotu, řadit nemusíš, stačí min a max.

body = [72, 15, 98, 40]

print(sorted(body))
print(body)

body.sort(reverse=True)
print(body)
print(min(body), max(body))

jmena = ["eva", "Zuzana", "Adam", "Šárka", "Čeněk"]
print(sorted(jmena))
Výstup
[15, 40, 72, 98]
[72, 15, 98, 40]
[98, 72, 40, 15]
15 98
['Adam', 'Zuzana', 'eva', 'Čeněk', 'Šárka']

U textů si všimni pořadí. Python porovnává čísla znaků v Unicode, ne česká pravidla. Velká písmena bez diakritiky proto stojí před malými a písmena s diakritikou až za z. Řazení podle vlastního pravidla přijde v lekci Funkce jako hodnoty.

Kvíz

Co vypíše tenhle kód? vysledek = [3, 1, 2].sort() a pak print(vysledek)

Najdi chybu

Kam zmizely body?

Program má seřadit body a do nejlepsi uložit nejvyšší z nich. Místo toho spadne. Který řádek je špatně?

Z textu seznam a zpátky

Data často přijdou jako jeden řádek textu. Metoda split ho rozseká na seznam, join naopak slepí seznam textů do jednoho. U join se píše oddělovač dopředu, což vypadá zvláštně, ale rychle si zvykneš.

radek = "jablka;hrušky;švestky"

ovoce = radek.split(";")
print(ovoce)
print(len(ovoce))

print(" + ".join(ovoce))

veta = "každé slovo zvlášť"
print(veta.split())
Výstup
['jablka', 'hrušky', 'švestky']
3
jablka + hrušky + švestky
['každé', 'slovo', 'zvlášť']

Bez argumentu split dělí podle bílých znaků, tedy mezer, tabulátorů a konců řádků. Víc o textech najdeš v lekci Řetězce do hloubky.

Úkol

Abecedně, prosím

V proměnné hoste jsou jména oddělená čárkou. Vytvoř text vysledek, ve kterém budou jména seřazená podle abecedy a oddělená čárkou a mezerou. Tedy Adam, Bořek, Marta, Zdena.

hoste = "Zdena,Adam,Marta,Bořek"

# doplň
Výstup
Pod kapotou · dynamické pole a co doopravdy stojí čas

list v CPythonu není spojový seznam. Je to souvislé pole ukazatelů PyObject * plus délka a kapacita, samotné objekty leží jinde. Proto sys.getsizeof(a) nezapočítá velikost prvků a proto může jeden seznam míchat typy.

Při zaplnění se pole přealokuje s rezervou zhruba o osminu plus malou konstantu. Kopírování se tak rozloží a append je amortizovaně O(1), jednotlivé volání ale občas trvá déle.

operacesložitost
a[i], a[i] = x, len(a)O(1)
a.append(x), a.pop()amortizovaně O(1)
a.insert(0, x), a.pop(0)O(n), posouvá všechny prvky
x in a, a.remove(x), a.count(x)O(n)
a.sort()O(n log n), na téměř seřazených datech blízko O(n)

Fronta přes pop(0) je častý tichý výkonnostní problém, na obou koncích patří collections.deque. Víc v lekci Rychlost a volba struktury.

Řazení je Timsort, od 3.11 se strategií slučování Powersort. Je stabilní, takže stejné prvky drží původní pořadí, a to se dá využít při řazení ve více průchodech. Během sort je seznam dočasně prázdný a jeho změna z funkce key skončí ValueError: list modified during sort. Správné české řazení potřebuje collation, například locale.strxfrm jako klíč nebo PyICU.

Past u porovnání: in a count zkoušejí nejdřív identitu, teprve potom ==. Dokumentace to u in popisuje jako x is e or x == e.

python
nan = float("nan")
print(nan == nan)    # False
print(nan in [nan])  # True, same object
print([nan] == [nan])  # True, same reason

Druhá past: [[]] * 3 nevytvoří tři seznamy, ale tři odkazy na tentýž. Rozebírá to lekce Reference, mutabilita a kopie.