TYPOVÉ ANOTACE, TESTOVÁNÍ, EFEKTIVITA ALGORITMŮIB111 ZÁKLADY PROGRAMOVÁNÍ

Nikola Beneš17. října 2019

is VS. ==

Porovnání hodnot ==

a = [1, 2, 3]b = [1, 2, 3]c = aprint(a == b, b == c, a == c) # True, True, True

Porovnání odkazů is

print(a is b, b is c, a is c) # False, False, True

Doporučení

• nepoužívejte is pro porovnávání hodnot(zdánlivě funguje pro čísla, ale jen pro některá)

• PEP8 vyžaduje is pro porovnání s None(to je zatím jediný případ, kdy byste is měli použít)

1

a = [1, 2, 3]b = [1, 2, 3]c = a

print(a == b, b == c, a == c) # True, True, True

print(a is b, b is c, a is c) # False, False, True

CHYBY V PROGRAMECH

Programy obsahují chyby

• chyby jsou běžné• všichni chybují

Jak odhalit chyby? / Jak ověřit, že program chyby nemá?

• jeden z důležitých problémů informatiky• testování (různé úrovně)• (poloautomatická) verifikace

• stále aktuální výzkumné téma• code review člověkem• důkaz korektnosti• …

2

TESTOVÁNÍ

(rozsáhlé téma, jen lehce nakousneme)

• velmi důležitá část vývoje software (až 80 % nákladů)• různé úrovně

• unit testing (testování malých kusů kódu)• integration testing• system testing• …

• automatické testování• kód, jehož cílem je otestovat jiný kód

• co nejvíce různých (druhů) vstupů• snaha otestovat co nejvíce možností

• testování nikdy není úplné• vstupů je nekonečně mnoho

3

UNIT TESTING

• testování jednotlivých částí kódu (funkcí)• funkce, které testují, zda kód funguje správně

def test_fact1():if fact(17) == 355687428096000:

print("OK")else:

print("Chyba! Funkce fact dává špatný ""výsledek pro vstup 17.")

# ...

• výhody oproti „ručnímu“ testování?• můžeme spouštět opakovaně• např. po každé změně v kódu

4

def test_fact1(): if fact(17) == 355687428096000: print("OK") else: print("Chyba! Funkce fact dává špatný " "výsledek pro vstup 17.") # ...

def test_fact2(): assert fact(17) == 355687428096000, \ "Špatný výsledek pro vstup 17." # ...

def fact(num): result = 0 for i in range(num): result *= i return result

PŘÍKAZ assert

• způsob, jak do kódu psát podmínky, které zaručeně musí platit• interpret nám je zkontroluje1

• když neplatí, ukončí program s chybovou hláškou• použití:

• testování• ověření podmínky, která nutně musí platit• alternativně: vyloučení situací, které nemohou nastat

def test_fact2():assert fact(17) == 355687428096000, \

"Špatný výsledek pro vstup 17."# ...

• nepoužívejte pro kontrolu uživatelského vstupu

1nejsou-li zapnuty optimalizace, což standardně nejsou5

def test_fact1(): if fact(17) == 355687428096000: print("OK") else: print("Chyba! Funkce fact dává špatný " "výsledek pro vstup 17.") # ...

def test_fact2(): assert fact(17) == 355687428096000, \ "Špatný výsledek pro vstup 17." # ...

def fact(num): result = 0 for i in range(num): result *= i return result

PŘÍKLAD POUŽITÍ PŘÍKAZU assert

def square_root(x, precision=0.01):lower = 0upper = xmiddle = (lower + upper) / 2while abs(middle ** 2 - x) > precision:

assert lower ** 2 precision: assert lower ** 2

PŘÍKLAD POUŽITÍ PŘÍKAZU assert

def survey(size, preferences):total = sum(preferences) # only needed for assertparties = len(preferences)count = [0] * parties

for i in range(size):r = random.randint(1, 100)threshold = 0for p in range(parties):

threshold += preferences[0]assert threshold

TYPOVÉ ANOTACE V PYTHONU

TYPOVÉ SYSTÉMY (JEN POVRCHNĚ)

silný vs. slabý typový systém

• jak velká omezení typový systém klade• jak snadno se ta omezení dají obejít?• není zcela jasně definováno, neostrá hranice

dynamické vs. statické typování

• statické: proměnné (funkce apod.) mají svůj typ• typy kontrolovány před spuštěním programu• typicky v době kompilace• typová chyba zabrání spuštění programu

• dynamické: hodnoty mají svůj typ• typy kontrolovány za běhu programu• typová chyba ukončí program• (nebo vyvolá výjimku, apod.)

8

VÝHODY STATICKÝCH A DYNAMICKÝCH TYPOVÝCH SYSTÉMŮ

dynamické

• jednodušší, rychlejší vývoj• stručnější kód• větší flexibilita• snadnější polymorfismus (duck-typing)

statické

• bezpečnější• odhalí chyby dřív, než jsou kritické

• „lépe se vám v noci spí“• často umožňuje rychlejší běh programu• informace o typech může mít dokumentační funkci

• (a kontroluje ji stroj, ne člověk)

9

TYPOVÉ ANOTACE V PYTHONU

• od verze 3.6 (omezeně i v některých starších verzích)• přináší (některé) výhody statického typového systémudo dynamicky typovaného jazyka

• odhalení potenciálních chyb před spuštěním programu• nutnost přemýšlet o typech vede (často) k lepšímu kódu• lepší spolupráce na větších projektech• některá IDE fungují lépe („našeptávání“)

• interpret Pythonu je ignoruje• používají je nástroje pro statickou analýzu kódu

• součástí některých IDE• samostatné• v současnosti nejlepší: mypy• http://mypy-lang.org

10

http://mypy-lang.org

FUNKCE, PROMĚNNÉ

Typová anotace funkcí

def is_triangle(a: float, b: float, c: float) -> bool:

• typy parametrů (tj. co funkce očekává)• typ návratové hodnoty (tj. co funkce slibuje, že vrátí)• pokud funkce nic nevrací, používáme None• neanotované funkce mypy ignoruje (dá se změnit --strict)

Typová anotace proměnných

• většinou není potřeba (mypy si umí typ odvodit z přiřazení)• dvě možnosti:

city: str = "Sparta"soldier_count = 300 # type: int

• první možnost funguje i bez přiřazení 11

def is_triangle(a: float, b: float, c: float) -> bool: return a + b > c and a + c > b and b + c > a

def fact(num): result = 1 for i in range(2, num + 1): result *= i return result

# try changing the return type annotationdef annotated_fact(num: int) -> int: # mypy automatically deduces the type of result result = 1 for i in range(2, num + 1): result *= i return result

# these are not really neededcity: str = "Sparta"soldier_count = 300 # type: int

# this is needed, why?temperature: float = 37

def say_hello(language: str, name: str) -> None: # this is again not really needed hello: str if language == "en": hello = "Hello" elif language == "dk": hello = "Hei" else: hello = "Saluton"

print(hello + ", " + name + "!")

SLOŽITĚJŠÍ TYPY: LIST, TUPLE

• se složitějšími typy se zachází speciálně• potřebujeme knihovnu typing

from typing import List, Tuple

• anotace pro seznamy: List[typ]• anotace pro ntice: Tuple[typ1, typ2, typ3, ...]

def average(numbers: List[float]) -> float:return sum(numbers) / len(numbers)

my_list: List[int] = []

def minmax(num1: int, num2: int) -> Tuple[int, int]:return min(num1, num2), max(num1, num2)

12

from typing import List, Tuple

def average(numbers: List[float]) -> float: return sum(numbers) / len(numbers)

# we need the annotation here, mypy cannot guess the typemy_list: List[int] = []

def minmax(num1: int, num2: int) -> Tuple[int, int]: return min(num1, num2), max(num1, num2)

OPTIONAL, TYPOVÁ SYNONYMA

• funkce, které někdy vrací hodnotu a někdy None

from typing import Optional

def safe_divide(p: float, q: float) -> Optional[float]:return None if q == 0 else p / q

• typová synonyma (pro čitelnější anotace)

Book = Tuple[str, str, float]

def get_book(database: List[Book], title: str) \-> Optional[Book]:

for book in database:if book[0] == title:

return bookreturn None 13

from typing import List, Tuple, Optional

# title, author, priceBook = Tuple[str, str, float]

def get_book(database: List[Book], title: str) \ -> Optional[Book]: for book in database: if book[0] == title: return book return None

my_books = [ ("Dune", "Frank Herbert", 686.90), ("The Absolute Sandman", "Neil Gaiman", 1276.70), ("Doupě latinářů", "Ivan Wernish", 131),]

from typing import Optional

def safe_divide(p: float, q: float) -> Optional[float]: return None if q == 0 else p / q

# this is a mypy-error:# print(safe_divide(3, 7) + 1)

# this is OK:result = safe_divide(3, 7)if result is not None: print(result + 1)

JAK POUŽÍVAT TYPOVÉ ANOTACE?

Chcete-li používat typové anotace (nebo vyžaduje-li to úloha) …

• anotujte funkce (i pomocné)• parametry i návratovou hodnotu

• zkuste spustit mypy, nejlépe s volbou --strict• pokud je všechno v pořádku, jste hotovi• pokud si mypy stěžuje, přečtěte si, co říká …• … a podle toho opravte svůj kód• nejste-li si jistí, co hláška znamená

• zkuste si ji přečíst (a přeložit z angličtiny)• zeptejte se (cvičící(ho), poradce, na diskusním fóru, …)

• proměnné většinou není třeba anotovat• kdyby to bylo nutné, mypy si bude stěžovat

14

EFEKTIVITA ALGORITMŮ

DĚLITELÉ ČÍSLA

def divisors1(num: int) -> List[int]:result = []for divisor in range(1, num + 1):

if num % divisor == 0:result.append(divisor)

return result

• jak tento kód vylepšit?

• počítat jen do poloviny num• využít toho, že divisor i num // divisor jsou děliteli• co když chceme, aby byli seřazení?

15

import mathfrom typing import List

def divisors1(num: int) -> List[int]: result = [] for divisor in range(1, num + 1): if num % divisor == 0: result.append(divisor) return result

def divisors2(num: int) -> List[int]: result = [] for divisor in range(1, num // 2 + 1): if num % divisor == 0: result.append(divisor) result.append(num) return result

def divisors3(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) result = [1, num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: result.append(divisor) result.append(num // divisor) # try running this code without the following if statement; what happens? if result[-1] == result[-2]: result.pop() # try running this code without the following line; what happens? result.sort() return result

def divisors4(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) small, large = [1], [num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: small.append(divisor) large.append(num // divisor) if small[-1] == large[-1]: large.pop() large.reverse() return small + large

DĚLITELÉ ČÍSLA

def divisors2(num: int) -> List[int]:result = []for divisor in range(1, num // 2 + 1):

if num % divisor == 0:result.append(divisor)

result.append(num)return result

• jak tento kód vylepšit?• počítat jen do poloviny num

• využít toho, že divisor i num // divisor jsou děliteli• co když chceme, aby byli seřazení?

15

import mathfrom typing import List

def divisors1(num: int) -> List[int]: result = [] for divisor in range(1, num + 1): if num % divisor == 0: result.append(divisor) return result

def divisors2(num: int) -> List[int]: result = [] for divisor in range(1, num // 2 + 1): if num % divisor == 0: result.append(divisor) result.append(num) return result

def divisors3(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) result = [1, num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: result.append(divisor) result.append(num // divisor) # try running this code without the following if statement; what happens? if result[-1] == result[-2]: result.pop() # try running this code without the following line; what happens? result.sort() return result

def divisors4(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) small, large = [1], [num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: small.append(divisor) large.append(num // divisor) if small[-1] == large[-1]: large.pop() large.reverse() return small + large

DĚLITELÉ ČÍSLA

def divisors3(num: int) -> List[int]:max_divisor = round(math.sqrt(num))result = [1, num]for divisor in range(2, max_divisor + 1):

if num % divisor == 0:result.append(divisor)result.append(num // divisor)

if result[-1] == result[-2]:result.pop()

result.sort()return result

• jak tento kód vylepšit?• počítat jen do poloviny num• využít toho, že divisor i num // divisor jsou děliteli• co když chceme, aby byli seřazení? jde to jinak?

15

import mathfrom typing import List

def divisors1(num: int) -> List[int]: result = [] for divisor in range(1, num + 1): if num % divisor == 0: result.append(divisor) return result

def divisors2(num: int) -> List[int]: result = [] for divisor in range(1, num // 2 + 1): if num % divisor == 0: result.append(divisor) result.append(num) return result

def divisors3(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) result = [1, num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: result.append(divisor) result.append(num // divisor) # try running this code without the following if statement; what happens? if result[-1] == result[-2]: result.pop() # try running this code without the following line; what happens? result.sort() return result

def divisors4(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) small, large = [1], [num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: small.append(divisor) large.append(num // divisor) if small[-1] == large[-1]: large.pop() large.reverse() return small + large

DĚLITELÉ ČÍSLA

def divisors4(num: int) -> List[int]:max_divisor = round(math.sqrt(num))small, large = [1], [num]for divisor in range(2, max_divisor + 1):

if num % divisor == 0:small.append(divisor)large.append(num // divisor)

if small[-1] == large[-1]:large.pop()

large.reverse()return small + large

• jak tento kód vylepšit?• počítat jen do poloviny num• využít toho, že divisor i num // divisor jsou děliteli• co když chceme, aby byli seřazení? je tohle lepší?

15

import mathfrom typing import List

def divisors1(num: int) -> List[int]: result = [] for divisor in range(1, num + 1): if num % divisor == 0: result.append(divisor) return result

def divisors2(num: int) -> List[int]: result = [] for divisor in range(1, num // 2 + 1): if num % divisor == 0: result.append(divisor) result.append(num) return result

def divisors3(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) result = [1, num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: result.append(divisor) result.append(num // divisor) # try running this code without the following if statement; what happens? if result[-1] == result[-2]: result.pop() # try running this code without the following line; what happens? result.sort() return result

def divisors4(num: int) -> List[int]: max_divisor = round(math.sqrt(num)) small, large = [1], [num] for divisor in range(2, max_divisor + 1): if num % divisor == 0: small.append(divisor) large.append(num // divisor) if small[-1] == large[-1]: large.pop() large.reverse() return small + large

PŘÍKLAD: OTRÁVENÁ STUDNA

• máme osm studen, víme, že (právě) jedna z nich je otrávená• laboratorní rozbor

• pozná přítomnost jedu ve vodě• je drahý

• je navíc časově náročný

• kolik rozborů potřebujeme k tomu, abychom s jistotou našliotrávenou studnu?

• všechny rozbory chceme dělat zároveň

Řešení: stačí tři rozbory• každý rozbor nám zmenší „okruh podezřelých“ na polovinu

• můžeme smíchat vodu z více studní

16

PŘÍKLAD: OTRÁVENÁ STUDNA

• máme osm studen, víme, že (právě) jedna z nich je otrávená• laboratorní rozbor

• pozná přítomnost jedu ve vodě• je drahý• je navíc časově náročný

• kolik rozborů potřebujeme k tomu, abychom s jistotou našliotrávenou studnu?

• všechny rozbory chceme dělat zároveň

Řešení: stále stačí tři rozbory• jeden rozbor: voda ze studní č. 1, 2, 3, 4• druhý rozbor: voda ze studní č. 1, 2, 5, 6• třetí rozbor: voda ze studní č. 1, 3, 5, 7• jak poznáme, která studna je otrávená?

16

PŘÍKLAD: HÁDÁNÍ ČÍSLA

• myslím si přirozené číslo mezi 1 a 1000 (včetně)• povoleny pouze otázky typu „Je myšlené číslo menší než N?“• kolik otázek potřebujete na odhalení čísla?

• těžší: kolik předem formulovaných otázek potřebujete?

• kdybyste měli pouze k dispozici pouze K otázek,v jakém rozsahu jste schopni čísla hádat?

17

PŘÍKLAD: HÁDÁNÍ ČÍSLA

Řešení

• půlení intervalu• 𝑁 čísel: potřebujeme cca log2 𝑁 otázek• 𝐾 otázek: umíme vyřešit rozsah velikosti 2𝐾

Řešení těžší varianty (předem formulované otázky)

• dotazy na jednotlivé číslice v binárním zápisu čísla• totéž jsme dělali u druhé varianty otrávené studny• opět stačí cca log2 𝑁 otázek

18

PŘIPOMENUTÍ: LOGARITMUS

𝑥 = 𝑏𝑦 právě tehdy, když 𝑦 = log𝑏(𝑥)

log10(1000) = 3 log3(81) = 4log2(16) = 4 log2(2) = 1log2(1024) = 10 log5(1) = 0log2(

√2) = 0.5 log0.5(4) = − 2

• log𝑏(𝑥 ⋅ 𝑦) = log𝑏(𝑥) + log𝑏(𝑦)• 𝑏𝑙𝑜𝑔𝑏(𝑥) = 𝑥

19

VYHLEDÁVÁNÍ

• častý problém:• web, slovník, informační systémy, databáze• dílčí krok v mnoha algoritmech

zdroj obrázku: http://www.bugemos.com/

20

http://www.bugemos.com/

VYHLEDÁVÁNÍ

Vyhledávání v obecném seznamu

• vstup: seznam čísel2 + dotaz (číslo)• výstup: odpověď True/False, jestli je číslo v seznamu• alt. výstup: index čísla v seznamu (nějaká speciální hodnota,např. None, pokud číslo v seznamu není)

• v nejhorším případě musíme projít celý seznam• časová složitost: cca délka seznamu• jde to lépe? v obecném seznamu ne

2nebo řetězců, nebo čehokoli jiného, co se dá hledat

21

LINEÁRNÍ VYHLEDÁVÁNÍ

def contains(haystack: List[int], needle: int) -> bool:for element in haystack:

if element == needle:return True

return False

def index_of(haystack: List[int], needle: int) \-> Optional[int]:

for index, element in enumerate(haystack):if element == needle:

return indexreturn None

• vyhledávání v Pythonu• operátor in (vrací bool)• seznam.index(prvek) – při nenalezení zahlásí ValueError 22

from typing import List, Optional

def contains(haystack: List[int], needle: int) -> bool: for element in haystack: if element == needle: return True return False

def index_of(haystack: List[int], needle: int) \ -> Optional[int]: for index, element in enumerate(haystack): if element == needle: return index return None

VYHLEDÁVÁNÍ

Vyhledávání v seřazeném seznamu

• vstup: seřazený seznam čísel + dotaz (číslo)• výstup: odpověď True/False, jestli je číslo v seznamu,případně index nalezeného prvku

Řešení

• „naivní“ řešení: procházení celého seznamu• složitost cca délka seznamu (lineární)• použitelné pro krátké seznamy• nepoužitelné pro delší seznamy

• „rozumné“ řešení: půlení intervalu• složitost logaritmická k délce seznamu• jak implementovat?

23

VYHLEDÁVÁNÍ

Binární vyhledávání

• půlení intervalu (podobné hádání čísel, výpočtu odmocniny, …)• podíváme se na prostřední prvek seznamu

• podle jeho hodnoty buď skončíme,nebo pokračujeme doleva nebo doprava

• udržujeme si „dolní“ a „horní“ mez

24

BINÁRNÍ VYHLEDÁVÁNÍ

def binary_search(haystack: List[int], needle: int) \-> bool:

lower_bound = 0upper_bound = len(haystack) - 1while lower_bound bool: lower_bound = 0 upper_bound = len(haystack) - 1 while lower_bound

BINÁRNÍ VYHLEDÁVÁNÍ

Zajímavé varianty k rozmyšlení

• co když se v seznamu prvky mohou opakovat?• index prvního prvku s danou hodnotou• index posledního prvku s danou hodnotou• jak si zachovat efektivitu?

• co když prvek v seznamu není, ale zajímalo by nás, kam by sezařadil?

• poslední prvek menší než hledaný• první prvek větší než hledaný

26

SLOŽITOST ALGORITMŮ (LETMO)

Časová složitost

• funkce, která délce vstupu přiřazuje počet kroků• typicky měříme nejhorší případ

• (existují i jiné možnosti)• je třeba si ujasnit:

• co jsou základní kroky, které počítáme• co je velikost vstupu

• při počítání se seznamy (většinou):• základní kroky jsou operace s jednotlivými prvky• velikost vstupu je délka seznamu

27

SLOŽITOST ALGORITMŮ (LETMO)

Asymptotická časová složitost

• zajímá nás pouze rychlost růstu funkcí• třída 𝒪(𝑓(𝑛)) – funkce, které rostou stejně rychle jako 𝑓(𝑛)nebo pomaleji

• zanedbáváme nedůležité části složitostní funkce• násobení konstantou• přičítání konstanty• nevedoucí členy polynomů, apod.

• příklady:• třída 𝒪(𝑛) zahrnuje všechny lineární funkce(𝑛, 3𝑛 + 7, 1000𝑛 + 9, …)

• třída 𝒪(𝑛2) zahrnuje všechny kvadratické funkce(𝑛2, 6𝑛2 + 11, 20𝑛2 − 17𝑛 + 9, 𝑛2 + 𝑛 + 3, …)

• třída 𝒪(log 𝑛) zahrnuje všechny logaritmické funkce(o základu > 1)

28

SLOŽITOST VYHLEDÁVÁNÍ (BINÁRNÍ VS. LINEÁRNÍ)

Jak moc je logaritmická složitost lepší než lineární?

• řekněme (jen pro účely tohoto slajdu), že• lineární vyhledávání má složitost 5 ⋅ 𝑛 operací• binární vyhledávání má složitost 20 ⋅ log2(𝑛) operací• jedna operace trvá 1 ns

𝑛 binární vyhledávání lineární vyhledávání8 60 ns 40 ns16 80 ns 80 ns256 160 ns 1280 ns65536 320 ns 327,68 µs

4294967296 640 ns 21,48 s18446744073709551616 1,28 µs 2922,78 let

29

VYHLEDÁVÁNÍ A DATOVÉ STRUKTURY

• seřazený seznam• umíme rychle vyhledávat, ale přidávání prvků je pomalé• proč?musíme udržovat seřazenostvkládání dovnitř seznamu je lineární(prvky za místem, kam přidáváme, musíme odsunout o kus dál)

• datové struktury pro rychlé vyhledávání, vkládání i mazání prvků(pro zajímavost)

• vyhledávací stromy• hašovací tabulky• v Pythonu: uvidíme později

30

PŘÍŠTĚ: ŘADICÍ ALGORITMY

• oblíbené algoritmické téma• anglicky „sorting algorithms“, česky někdy „třídicí algoritmy“• cílem je seřadit data v seznamu• existuje mnoho různých algoritmů• většina programovacích jazyků má ve své standardní knihovněfunkci sort() nebo podobnou

• proč se tím tedy zabýváme?• ukázka programů se seznamy• algoritmy s různou myšlenkou• „programátorská tradice“

• k zamyšlení do příště:• jak byste seřadili seznam? (v Pythonu)• jak řadíte „ručně“? (karty, knihy, koření, …)

31

Typové anotace v PythonuEfektivita algoritmů