W tym wyzwaniu przejdziemy do dziedziny wiedzy zwanej algorytmy i struktury danych. Skupia się ona na takim sposobie przechowywania danych, a także operowaniu na nich, aby w sposób wydajny osiągać założone cele. Przykładowo jeśli mamy pewien zbiór elementów, i chcemy znaleźć jeden z nich (lub stwierdzić, że go nie ma), to czy aby na pewno musimy przeglądać wszystkie te elementy? Czy gdy chcemy policzyć $2^10$, to na pewno musimy przeprowadzić 10 mnożeń?

My w naszym poradniku nie będziemy sami tworzyć zaawansowanych struktur danych, ani algorytmów na nich działających. Raczej pokażemy, jak skorzystać z gotowych, wydajnie zaimplementowanych struktur, aby rozwiązać nasze problemy.

Funkcje

Zanim przejdziemy dalej, musimy wprowadzić pojęcie funkcji. Funkcja jest kolejnym sposobem, aby napisać kod raz, a następnie móc korzystać z niego wielokrotnie. Funkcja to swego rodzaju czarna skrzynka: wprowadzamy do niej pewne dane, aby na wyjściu otrzymać wynik. Można też porównać ją do rozwiązywania zadania z fizyki: mamy dane (w funkcji są to jej parametry), szukane (jest to wartość zwracana przez funkcję), a także rozwiązanie (jest to ciało funkcji). Spójrzmy na tę analogię w ten sposób: gdy raz rozwiążemy zadanie na wzorach, później już możemy podstawić dowolne dane liczbowe, a same rachunki się nie zmieniają.

Zacznijmy od prostego przykładu. Chcemy obliczyć wartość funkcji liniowej ax+b dla danych x,a,b. Wtedy napiszemy tak:

def liniowa(x, a, b):
    return a*x+b

Jak widać, najpierw piszemy słowo kluczowe def, następnie nazwę funkcji, a potem w okrągłych nawiasach kolejne parametry oddzielone przecinkami. W przeciwności do innych języków programowania nie deklarujemy ani typów danych przechowywanych w parametrach, ani typu danych zwracanego przez funkcję. Sama funkcja zawiera ciało, w którym przeprowadzane są obliczenia, a instrukcja zwracająca wartość to słowo kluczowe return, po którym następuje właśnie ta wartość.

Teraz, gdy mamy już zdefiniowaną funkcję, dokonajmy jej wywołania. Polega ono na napisaniu nazwy funkcji, a także okrągłych nawiasów, w których będą jej argumenty: konkretnie wartości liczbowe, dla których ma zostać obliczona wartość funkcji liniowej:

a = 2
x = 3
wynik = liniowa(x, a, 5)
print(wynik)

## 11

print(liniowa(x, a, 3))

## 9

Zwróćmy uwagę na parę szczegółów: argumenty możemy przekazać zarówno przez zmienną, jak i wpisując bezpośrednio wartość. Wynik działania funkcji możemy przypisać do zmiennej, ale możemy też bezpośrednio przekazać je jako argument do wywołania innej funkcji (w tym wypadku funkcja print()). Wracając do naszej analogii: czarna skrzynka dostaje na wejściu x,a,b, a ze skrzynki “wyskakuje” wartość funkcji liniowej. W drugiej analogii w danych mamy x,a,b, podczas gdy w szukanych y – wartość funkcji liniowej. Rozwiązaniem jest y=ax+b.

Teraz przejdźmy do ciekawszego przykładu. Napiszmy funkcję, która zwraca liczbę podniesioną do potęgi. Aby policzyć potęgę, potrzebujemy dwóch liczb: podstawy i wykładnika. Następnie wykonujemy tyle mnożeń, ile wynosi wykładnik (z dokładnością do 1). Mamy tu połączenie dwóch idei: funkcji i pętli. Spójrzmy:

def potega(podstawa, wykladnik):
    i = 1
    wynik = 1
    while i <= wykladnik:
        wynik *= podstawa
        i += 1
    return wynik

I przykładowe wywołanie:

print(potega(3,4))

## 81

Wartości domyślne parametrów

Czasami niektóre parametry będą często w naszych wywołaniach przyjmować za każdym razem tę samą wartość. Warto wtedy przypisać takiemu parametrowi wartość domyślną. Wtedy nie musimy podawać tego argumentu w wywołaniu. W naszym przykładzie przypiszemy wykładnikowi wartość domyślną równą 1:

def potega(podstawa, wykladnik=1):
    i = 1
    wynik = 1
    while i <= wykladnik:
        wynik *= podstawa
        i += 1
    return wynik

Teraz możemy wywołać funkcję z jednym argumentem. Będzie to podstawa:

print(potega(4))

## 4

Argumenty nazwane

Do tej pory podawaliśmy argumenty w tej samej kolejności, co parametry w definicji funkcji. Pierwszy argument w wywołaniu “szedł” do pierwszego parametru funkcji itd. Jednak nie musi tak być. Możemy podawać argumenty w dowolnej kolejności, gdy podamy ich nazwy:

print(potega(wykladnik = 4, podstawa = 3))

## 81

Rekurencja

Na koniec omawiania funkcji pokażmy technikę zwaną rekurencją. Oznacza to, że do rozwiązania zadania używamy właśnie definiowanej funkcji (innymi słowy, funkcja wywołuje samą siebie, ale ze zmienionym argumentem). Klasycznym przykładem jest obliczanie wartości silni. Możemy zapisać, że n!=n⋅(n−1)!. Jak widzimy, obliczenie wartości silni dla n wymaga obliczenie wartości silni dla n−1. Warto jednak zauważyć, że wzór ten jest niepełny i prowadziłby do nieskończonych obliczeń. Dlatego w rekurencji zawsze musimy zdefiniować przypadek brzegowy, zwany też granicznym. W tym wypadku jest to 0!=1. Uzbrojeni w taką wiedzę możemy napisać:

def silnia(n):
  if n == 0:
    return 1
  return n*silnia(n-1)

I wywołanie:

print(silnia(5))

## 120

Teraz, gdy mamy za sobą omówienie funkcji, możemy przejść do trochę bardziej zaawansowanych typów danych w języku Python.

Krotka

Pewną specyficzną dla języka Python strukturą jest krotka. Polega ona na grupowaniu paru wartości w jeden byt. Warto zaznaczyć, że krotka, która raz została stworzona, nie może być modyfikowana: nie możemy podmienić jednej ze składowych krotki. Stwórzmy najprostszą krotkę (krotka to ogólne określenie na dwójkę, trójkę, czwórkę itd.):

krotka = (2,3)
print(krotka)

## (2, 3)

Gdybyśmy chcieli uzyskać poszczególne składowe krotki, możemy to zrobić przy użyciu operatora kwadratowych nawiasów. W Pythonie, tak jak w wielu językach programowania, numerujemy składowe od 0:

pierwsza = krotka[0]
druga = krotka[1]
print(pierwsza)

## 2

print(druga)

## 3

Oczywiście w krotce możemy mieszać typy danych:

krotka = (2, "Napis")
print(krotka)

## (2, 'Napis')

Kiedy krotka może być przydatna? Np. gdy chcemy zwrócić więcej niż jedną wartość w funkcji.

Lista

Podobną, przynajmniej na pozór, strukturą danych do krotki jest lista. Tutaj także możemy grupować dane oraz nie muszą one być tego samego typu. Jednak główną różnicą jest to, że listę możemy modyfikować. Możemy dodawać nowe elementy czy zastępować dotychczasowe. Listę należy kojarzyć z kwadratowymi nawiasami:

lista = [1, False, "Napis"]
print(lista)

## [1, False, 'Napis']

Aby otrzymać liczbę elementów na liście, czyli jej długość, posługujemy się funkcją len():

print(len(lista))

## 3

Dodajmy kolejny element:

lista.append(2.5+3.7j)
print(lista)

## [1, False, 'Napis', (2.5+3.7j)]

Zaskoczyć może nas kropka pomiędzy zmienną lista a nazwą metody append(). Lepiej zrozumiemy ją, gdy będziemy omawiać programowanie obiektowe. Teraz jednak powiedzmy sobie tylko, że oznacza to, że metoda append() (słowo metoda możemy póki co utożsamiać ze słowem funkcja) jest wywoływana na rzecz zmiennej lista, co oznacza, że będzie modyfikować właśnie ją (dopisze do niej kolejny element).

Istnieje podobna metoda, która przyjmuje jako argument całą listę i dodaje z niej kolejne elementy:

lista.extend([97,98,99])
print(lista)

## [1, False, 'Napis', (2.5+3.7j), 97, 98, 99]

Operatory + i * mają zdefiniowane działanie w kontekście list. +, tak jak w przypadku napisu, to konkatenacja, czyli połączenie dwóch list w jedną:

print(lista + [7,8,9])

## [1, False, 'Napis', (2.5+3.7j), 97, 98, 99, 7, 8, 9]

* zaś pozwala nam powielić daną listę:

print([7,8,9] * 3)

## [7, 8, 9, 7, 8, 9, 7, 8, 9]

Odwołanie się do konkretnego elementu następuje tak jak w krotce:

print(lista[2])

## Napis

Warto tu zwrócić uwagę na specyficzny dla języka Python mechanizm: ujemne indeksy oznaczają pozycje liczone od tyłu, i tak do ostatniej wartości odwołamy się przez:

print(lista[-1])

## 99

a przedostatniej:

print(lista[-2])

## 98

Możemy też podmienić taki element:

lista[2] = "Nowy"
print(lista)

## [1, False, 'Nowy', (2.5+3.7j), 97, 98, 99]

Ciekawsze jest jednak odwoływanie się do pewnego wycinka listy. W tym celu znów używamy kwadratowych nawiasów, ale tym razem wraz z dwukropkiem w środku:

print(lista[2:5])

## ['Nowy', (2.5+3.7j), 97]

Zwróćmy uwagę, że indeksujemy od zera, a także, że pierwszy indeks podajemy włącznie, a drugi wyłącznie. Tak więc wybieramy elementy pod indeksami 2, 3 i 4.

Tutaj także może nastąpić podmiana, niekoniecznie w tej samej liczności:

lista[0:3] = [98,99,101,102]
print(lista)

## [98, 99, 101, 102, (2.5+3.7j), 97, 98, 99]

Wstawienie nowego elementu może nastąpić także w następujący sposób:

lista.insert(1, "Nowy2")
print(lista)

## [98, 'Nowy2', 99, 101, 102, (2.5+3.7j), 97, 98, 99]

A jej usunięcie:

del lista[1]
print(lista)

## [98, 99, 101, 102, (2.5+3.7j), 97, 98, 99]

Na koniec pokażmy sortowanie i odwracanie listy:

liczby = [1,6,3,5,4,7]
liczby.sort()
print(liczby)

## [1, 3, 4, 5, 6, 7]

liczby.reverse()
print(liczby)

## [7, 6, 5, 4, 3, 1]

Napisy

Napisy to tak naprawdę lista, tylko, że liter. Dlatego wszelkie zasady pokazane wyżej dotyczące list mają też zastosowanie dla napisów. I tak możemy choćby odwołać się do pojedynczych liter przez operator indeksowania:

napis = "Ala ma kota"
print(napis[0])

## A

print(napis[0:3])

## Ala

Długość napisu to oczywiście:

print(len(napis))

## 11

W napisach warto zwrócić uwagę na znak backslash: \. Gdy chcemy napisać znak specjalny w napisie, np. przejście do nowego wiersza czy znak tabulacji, używamy kodu, który zaczyna się właśnie od tego znaku. I tak najpopularniejsze jest przejście do nowego wiersza, \n:

print("Pierwszy wiersz\nDrugi wiersz")

## Pierwszy wiersz
## Drugi wiersz

Gdybyśmy nie chcieli, aby znak \ był interpretowany w sposób specjalny, możemy poprzedzić cudzysłów literą r(od raw):

print(r"Pierwszy wiersz\nDrugi wiersz")

## Pierwszy wiersz\nDrugi wiersz

Przy okazji warto pokazać inny sposób wprowadzania wartości zmiennych do napisu, niż dotychczas pokazane dość niewygodne sklejanie napisów. Użyjemy tym razem prefiksu f przed napisem, a nazwy zmiennych będą otoczone nawiasami klamrowymi:

zmienna = 7
napis = f"wartość zmiennej to {zmienna}"
print(napis)

## wartość zmiennej to 7

Wróćmy teraz do komentarza wielowierszowego poznanego w pierwszym wyzwaniu. Tak naprawdę był to napis wielowierszowy:

wieleWierszy = """Tutaj pierwszy
a tu drugi
tutaj trzeci"""
print(wieleWierszy)

## Tutaj pierwszy
## a tu drugi
## tutaj trzeci

Kolejność alfabetyczną, zwaną profesjonalnie leksykograficzną, możemy sprawdzić przez operator porównania:

print("a" < "b")

## True

Zamiana wszystkich liter na wielkie:

napis = "Ala ma kota."
print(napis.upper())

## ALA MA KOTA.

W drugą stronę:

napis = "Ala Ma Kota."
print(napis.lower())

## ala ma kota.

Dość przydatną funkcją jest strip(), która usuwa białe znaki (spacje, entery, tabulatory…) z początku i końca napisu:

napis = "   \n\t Ala \n "
print(napis.strip())

## Ala

Zliczanie i zastępowanie wzorca:

napis = "wyraz, inny wyraz, i jeszcze inny wyraz"
print(napis.count("wyraz"))

## 3

napis=napis.replace("wyraz", "WYRAZ")
print(napis)

## WYRAZ, inny WYRAZ, i jeszcze inny WYRAZ

W przypadku, gdy mamy listę napisów i chcemy ją połączyć w jeden wielki napis, wywołujemy join():

listaNapisow = ["Ala", "ma", "kota"]
print("+".join(listaNapisow))

## Ala+ma+kota

Znów operacja odwrotna będzie polegać na wywołaniu funkcji split():

napis = "Ala ma kota"
print(napis.split(" "))

## ['Ala', 'ma', 'kota']

Zbiór

Teraz przejdziemy do zupełnie innego typu danych: są to zbiory. Zbiór ma dwie ważne cechy: obiekty w zbiorze nie mogą się powtarzać oraz dostęp do konkretnych elementów zbioru (znalezienie elementu w zbiorze lub stwierdzenie, że takowego nie ma) jest bardzo szybki. Zwróćmy uwagę na tę różnicę względem listy: w liście dostęp był szybki, gdy znaliśmy pozycję, indeks, elementu, do którego chcieliśmy się odwołać. Za to dostęp po wartości, jaka się na danym miejscu kryła, było długie (w pesymistycznym przypadku musielibyśmy przejść całą listę).

Kiedy zbiór może się przydać? Np. gdy zbieramy dane z różnych stron internetowych i chcemy się upewnić, że każdy link odwiedzamy tylko raz. Wtedy wstawiamy do zbioru kolejne odwiedzane adresy URL, a następnie, przed odwiedzeniem kolejnego, sprawdzamy, czy nie występuje on już w zbiorze.

Przejdźmy do praktyki. Pokażemy, jak stworzyć pusty zbiór oraz taki, w którym są już jakieś elementy:

zbiorPusty = set()
zbior = {1, 3, 5}
print(zbiorPusty)

## set()

print(zbior)

## {1, 3, 5}

Teraz dokonajmy najbardziej typowego działania na zbiorze, czyli sprawdźmy, czy dany element jest w zbiorze:

print(1 in zbiorPusty)

## False

print(1 in zbior)

## True

Możemy równie dobrze sprawdzić, czy dany element nie występuje w zbiorze:

print(1 not in zbiorPusty)

## True

print(1 not in zbior)

## False

Aby dodać element do zbioru, użyjemy metody add():

zbiorPusty.add(2)
zbior.add(2)
print(zbiorPusty)

## {2}

print(zbior)

## {1, 2, 3, 5}

Aby zaś usunąć element, posłużymy się metodą discard():

zbiorPusty.discard(2)
zbior.discard(2)
print(zbiorPusty)

## set()

print(zbior)

## {1, 3, 5}

Ponadto możemy wykonać typowe operacje teoriomnogościowe, jak suma, różnica czy przecięcie dwóch zbiorów:

print({1,5,8} | {1,5,9}) # suma

## {1, 5, 8, 9}

print({1, 5, 8} - {1, 5, 9}) # różnica

## {8}

print({1, 5, 8} & {1, 5, 9}) # przecięcie

## {1, 5}

A także zapytać, czy jeden zbiór jest podzbiorem drugiego:

print({1, 5}.issubset({1, 5, 9}))

## True

Dla dociekliwych: aby dowiedzieć się, jak są zaimplementowane zbiory w języku Python tak, że dostęp do poszczególnych elementów jest taki szybki, polecamy lekturę: tablica mieszająca.

Słownik

Pewnym rozbudowaniem idei zbioru jest słownik. W naszym mniemaniu częściej w praktyce występuje potrzeba użycia słownika niż zbioru, choć popracie tej tezy wymagałoby przeprowadzenia szerzej zakrojonych badań. Słownik zawiera pary klucz-wartość. Wyszukiwanie po kluczu jest szybkie, tak jak w zbiorze, jednak gdy już odnajdziemy klucz, możemy odzyskać także stowarzyszoną z nim wartość. Gdy usuniemy ze słownika wartości, a zostawimy same klucze, otrzymamy zbiór. Tak jak w zbiorze, w słowniku klucze nie mogą się powtarzać.

Kiedy może się przydać słownik? Otóż każda baza danych jest słownikiem. Wyobraźmy sobie, że posiadamy dane dotyczące 40 milionów Polaków. Jak odnaleźć dane dotyczące jednego z nich, bez przeglądania 40 milionów rekordów? Uporządkujmy te dane w słowniku po numerze PESEL (i to będzie nasz klucz), a resztę danych, takich jak imię, nazwisko i adres zamieszkania umieśmy obok numeru PESEL (to będzie nasza wartość). Wtedy łatwo będzie znaleźć daną osobę po numerze PESEL, choć znalezienie po imieniu i nazwisku będzie już powolne (ale to bolączka wszystkich słowników, stąd tak ważny jest mądry dobór klucza).

Spróbujmy zrealizować nasz przykład w praktyce. Numery PESEL będą przechowywane jako napisy, a dane osobowe w formie listy. Tak jak w przypadku zbiorów, słownik tworzymy przy użyciu nawiasów klamrowych. Klucze od wartości oddzielamy dwukropkiem.

bazaDanychPolakow = {"89082911111" : ["Jan", "Kowalski", 29],
                     "95092200000" : ["Ania", "Nowak", 23],
                     "98122422222" : ["Adam", "Mickiewicz", 220]
}
print(bazaDanychPolakow)

## {'89082911111': ['Jan', 'Kowalski', 29], '95092200000': ['Ania', 'Nowak', 23], '98122422222': ['Adam', 'Mickiewicz', 220]}

Teraz, jak poprzednio, możemy sprawdzić, czy dany numer PESEL jest w słowniku:

print("89082911111" in bazaDanychPolakow)

## True

print("95092200022" not in bazaDanychPolakow)

## True

Gdy chcemy uzyskać wartość stowarzyszoną z kluczem, napiszemy:

print(bazaDanychPolakow["98122422222"])

## ['Adam', 'Mickiewicz', 220]

Gdy chcemy zabezpieczyć się przed odwołaniem do nieistniejącego elementu (i w tym wypadku zwrócić wartość domyślną), użyjemy metody get():

print(bazaDanychPolakow.get("89082911111", "wartość domyślna"))

## ['Jan', 'Kowalski', 29]

print(bazaDanychPolakow.get("95092200022", "wartość domyślna"))

## wartość domyślna

Dodanie nowej pary klucz-wartość odbywa się w następujący sposób:

bazaDanychPolakow["88081244444"] = ["Magda", "K", 30]
print(bazaDanychPolakow)

## {'89082911111': ['Jan', 'Kowalski', 29], '95092200000': ['Ania', 'Nowak', 23], '98122422222': ['Adam', 'Mickiewicz', 220], '88081244444': ['Magda', 'K', 30]}

Usunięcie zaś:

del bazaDanychPolakow["88081244444"]
print(bazaDanychPolakow)

## {'89082911111': ['Jan', 'Kowalski', 29], '95092200000': ['Ania', 'Nowak', 23], '98122422222': ['Adam', 'Mickiewicz', 220]}

Pomimo, że słowniki raczej służą do wybiórczego wybierania pojedynczych par klucz-wartość, istnieje możliwość przejścia pętlą (poprawniej: przeiterowania się) po wszystkich elementów. Mamy tu do wyboru przejście po samych kluczach, samych wartościach lub po parach klucz-wartość:

for klucz in bazaDanychPolakow.keys():
    print(klucz)

## 89082911111
## 95092200000
## 98122422222

for wartosc in bazaDanychPolakow.values():
    print(wartosc)

## ['Jan', 'Kowalski', 29]
## ['Ania', 'Nowak', 23]
## ['Adam', 'Mickiewicz', 220]

for klucz, wartosc in bazaDanychPolakow.items():
    print(klucz)
    print(wartosc)
    print("-----")

## 89082911111
## ['Jan', 'Kowalski', 29]
## -----
## 95092200000
## ['Ania', 'Nowak', 23]
## -----
## 98122422222
## ['Adam', 'Mickiewicz', 220]
## -----

Zwróćmy uwagę zwłaszcza na ostatnią pętlę: tam, gdzie podajemy zmienną iterującą, podaliśmy dwie zmienne oddzielone przecinkiem. Oznacza to, że metoda items() zwraca krotkę, która ma dwa elementy. A my rozpakowujemy tę krotkę, co oznacza, że przypisujemy jej pierwszy element do zmiennej klucz, a drugi jej element do zmiennej wartosc.

Zadanie 3

Sprytne obliczanie potęgi

Okazuje się, że można obliczyć potęgę przy użyciu mniejszej liczby mnożeń, korzystając z rekurencji. W tym celu przeanalizujmy przykład: $2^7$ = $2^3$ * $2^3$ * 2. Jak widzimy, wystarczy raz obliczyć $2^3$. Następnie można ten wynik przemnożyć przez samego siebie, a potem, jeśli oryginalny wykładnik był nieparzysty (a był, bo było to 7), domnożyć jeszcze raz przez podstawę. Napisz funkcję sprytne_potegowanie(podstawa, wykladnik), która oblicza zadaną potęgę w podany sposób: wywołuje rekurencyjnie samą siebie dla wykładnika podzielonego na dwa (z zaokrągleniem) jak w przykładzie, a następnie operując na tym częściowym wyniku oblicza pełną potęgę.

Palindrom

Napisz funkcję czyPalindrom(), która zwraca prawdę, gdy podany jako argument napis jest palindromem, to znaczy czytany wspak da ten sam napis, np. “kajak”. Funkcja zwraca fałsz w przeciwnym wypadku.

Anagram

Napisz funkcję czyAnagram(), która zwraca prawdę, gdy dwa napisy podane jako dwa argumenty funkcji mają tę własność, że da się z liter pierwszego napisu ułożyć drugi napis. To zadanie da się rozwiązać na naprawdę wiele sposobów, a najwydajniejszy z nich zakłada użycie słowników.

Moda

Napisz funkcję moda(), która jako parametr przyjmuje listę liczb całkowitych. Funkcja zwraca tę liczbę, która pojawia się w tej liście najczęściej. Jeśli mamy remis, zwróć którąkolwiek z tych liczb.

Gotowe rozwiązanie zadania 3 znajdziecie tutaj.