Title: Przetwarzanie równoległe i strumieniowe

PRS

Przetwarzanie równoległe i strumieniowe

Wykład 2

Struktury danych, programowanie funkcyjne, strumienie w Python

Zaliczenie

Struktury danych

https://dev.to/davidgitonga/an-introduction-to-python-data-structures-l8l

Struktury danych - listy

Listy w Pythonie mogą mieć różne typy danych:

group = ["Bob", 23, "George", 72, "Myriam", 29]

Listy mogą mieć podlisty jako elementy. Te listy podrzędne mogą również zawierać listy podrzędne, tj. Listy mogą być konstruowane rekurencyjnie za pomocą struktur list podrzędnych.

>>> complex_list = [["a",["b",["c","x"]]]]
>>> complex_list = [["a",["b",["c","x"]]],42]
>>> complex_list[0][1]
['b', ['c', 'x']]
>>> complex_list[0][1][1][0]

Output :

Q: [...]
A: c

Struktury danych - in operator

Operator in sprawdza czy element znajduje się w kolekcji

t = [1, 2, 4, 5]
3 in t
4 in t
4 not in t

Output:

False
True
False

Struktury danych - tuple

Tuple to immutable kolekcje w Pythonie i są definiowane przez nawiasy

our_tuple = (5, 6, 7, 8)

# We can index them, just like strings
our_tuple[2]
>>> 7

# And iterate through them:
for item in our_tuple:
    print item
>>> 5
>>> 6
>>> 7
>>> 8

Struktury danych - tuple

Tuple możemy rozpakowywać

new_tuple = (5, 6, 7, 8)
(a, b, c, d) = new_tuple
print ("a is:", a)
a is: 5
print ("b is:", b)
b is: 6
print ("c is:", c)
c is: 7
print ("d is:", d)
d is: 8

Upewnij się, że zawsze masz taką samą liczbę zmiennych podczas rozpakowywania tuple!

Tuple są niemutowalne. Aby zmienić tuple, musielibyśmy najpierw ją rozpakować, zmienić wartości, a następnie spakować.

Struktury danych - list comprehensions

List comprehension to mechanizm podobny do notacji matematycznej

S = {x^2 : x in {0 ... 9}}

Nowa lista jest generowana przez aplikację funkcji do wszystkich elementów listy

[ expression for name in list ]

li = [3, 6, 2, 7]
[ elem *2 for elem in li]

Output:

[6, 12, 4, 14]

Struktury danych - list comprehensions

Jeśli elementami listy są inne kolekcje, to nazwa może zostać zastąpiona zbiorem nazw pasujących do „kształtu” elementów listy.

li = [(‘a’, 1), (‘b’, 2), (‘c’, 7)]
[ n * 3 for (x, n) in li ]

Output:

Q: [...]
A: [3, 6, 21]

Struktury danych - dictionary

Słowniki są jak listy, ale zawierają jako elementy pary klucz-wartość.

Składnia dla tworzenia słowników {key1 : value1}

params = {"parameter1" : 1.0,
        "parameter2" : 2.0,
        "parameter3" : 3.0}

print(type(params))
print(params)
params["parameter1"] = "A"
params["parameter2"] = "B"

Struktury danych - dictionary

Do iteracji po słowniku nie potrzebujemy żadnych specjalnych metod starczy operator in:

for key in d:
    print(key)

Mamy także specjalne metody do pobierania kluczy keys():

for key in d.keys():
    print(key)

Metoda values() służy do pobierania listy wartości słownika:

for val in d.values():
    print(val)

Struktury danych - zip

Do łączenia dwóch list w jedną posłużyć nam może funkcja zip().

Zipowany obiekt można łatwo przekształcić w prawdziwy słownik za pomocą funkcji dict().

>>> keys = ['a', 'b', 'c']
>>> values = [1, 2, 3]
>>> dictionary = dict(zip(keys, values))
>>> print(dictionary)
{'a': 1, 'b': 2, 'c': 3}

Struktury danych - set

Zbiory to immutowalne kolekcje unikalnych, nieuporzadkowanych elementów.

>>> x = set("A Python Tutorial")
>>> x
set(['A', ' ', 'i', 'h', 'l', 'o', 'n', 'P', 'r', 'u', 't', 'a', 'y', 'T'])

x = {"A","b","C"}
print(x)
y = {"Abc"}
print(y)
z = set(["asd","ads"])
print(z)
******************
{'A', 'b', 'C'}
{'Abc'}
{'asd', 'ads'}

Struktury danych definiowane

http://www.quickmeme.com/meme/3t5jki

Struktury danych definiowane - linked list

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insertAtBegin(self, data):
    new_node = Node(data)
    if self.head is None:
        self.head = new_node
        return
    else:
        new_node.next = self.head
        self.head = new_node

Funkcje

https://blog.kotlin-academy.com/programmer-dictionary-higher-order-function-9cadb07df94e

Funkcje

W związku z tym, że funkcje w Python są obiektami, możemy przekazywać funkcje - lub lepiej "referencje do funkcji" - jako parametry funkcji.

def g():
    print("Hi, it's me 'g'")

def f(func):
    print("Hi, it's me 'f'")
    func()

f(g)

Output:

Hi, it's me 'f'
Hi, it's me 'g'

Programowanie funkcyjne

[Image: emc]

Programowanie funkcyjne, jak sama nazwa wskazuje, polega na definiowaniu wykonania programu jako wywołań funkcji.

Pozwalają one pisać prostszy, niezależny, krótszy kod, ktory łatwiej jest przetestować oraz zrównoleglić. Programowanie funkcyjne opiera się na tzw "pure functions".

Wątki

Pure functions

Funkcja jest nazywana funkcją czystą (pure function), jeśli zawsze zwraca ten sam wynik dla tych samych wartości argumentów i nie ma skutków ubocznych, takich jak modyfikacja argumentu (lub zmiennej globalnej) lub zmiana stanu systemu.

Jedynym wynikiem wywołania funkcji czystej jest wartość zwracana.

Przykłady pure functions

Przykłady pure functions to len("abc"), pow(x,y), math.sqrt(x) etc.

Przykłady impure functions to print() (zmienia stan), random.randint(x,y), time.time() (zależą od globalnego stanu) etc.

Przykłady pure functions

Kompilatory (np dla C++) potrafią optymalizować czyste funkcje, wiedząc, że dana wartośc dla tego samego argumentu będzie zawsze stała.

for (len = 0; len < strlen(str); ++len)

    printf("%c", toupper(str[len]));

zamieni na

int len = strlen(str);

for (i = 0; i < len; ++i)

    printf("%c", toupper((str[i]));

Przykłady

Q: global m = '';
def add(a, b):
    global m
    m = 'added'
    return a + b
A: false
If wrong: Zmienia globalny stan

Q: Czy jest czystą funkcją:

l = [1, 2, 3]

def last(l):
    return l[-1]
A: true

Przykłady

Q: min()
A: true

Q: l = [1, 2, 3]

def last():
    return l.pop()
A: false
If wrong: Zmienia wejściową listę

Przykłady

Q: K = 10
def add10(a):
    return a + K
A: false
If wrong: Korzysta z globalnego stanu

Python a programowanie funkcyjne

Programy w Pythonie mają funkcjonalnie wyglądający interfejs, ale wewnętrznie używają niefunkcjonalnych operacji.

Przykład:

Implementacja funkcji może również wykorzystywać przypisania zmiennych lokalnych, ale nie zmieniać zmiennych globalnych, ani nie mieć żadnych innych skutków ubocznych dla stanu systemu (programu).

Podsumowanie

1: Funkcja Pure powinna zwracać to samo wyjście przy tych samych danych wejściowych.

2: Czysta funkcja nie powoduje skutków ubocznych (pozostawia nienaruszone środowisko). Częstymi efektami ubocznymi są zmiana właściwości obiektu globalnego, zapisywanie w konsoli, zmiana kodu HTML strony, na której wykonywany jest skrypt.

3: Czysta funkcja nie powinna polegać na stanie zewnętrznym.

Podsumowanie - zalety i wady

Zalety programowania funkcyjnego:

- łatwe debuggowanie i testowanie
- modularność
- lazy evaluation
- wykonanie równoległe
- czytelność

Wady programowania funkcyjnego:

- trudne do opanowania
- czasem trudno uniknąć kontekstu

Iteratory

Iterator jest formą obiektu, który reprezentuje strumień danych i zwraca każdą jednostkę jeden po drugim.

Musi mieć metodę o nazwie __next__(), która nie przyjmuje żadnych argumentów i zawsze zwraca następny element strumienia.

Jeśli strumień nie zawiera żadnych obiektów, __next__() powinien natychmiast zgłosić wyjątek StopIteration.

Iterator nie musi być skończony; w rzeczywistości napisanie iteratora, który generuje nieskończony strumień danych, jest całkowicie racjonalne.

Iteratory - nieskończony iterator

Iterator

Funkcjonalny operator iter() pobiera obiekt i próbuje zwrócić iterator, który będzie zawierał zawartość lub elementy obiektu, zgłaszając TypeError, jeśli obiekt nie pozwala na iterację.

Iteracja jest obsługiwana przez kilka funkcjonalnych typów danych, z których najpowszechniejszymi są listy i słowniki.

Jeśli możesz uzyskać iterator dla obiektu, mówi się, że jest on iterowalny.

Każdy proces ma własny licznik instrukcji, który wskazuje następną instrukcję do wykonania, oraz własny obszar przydzielonej mu pamięci operacyjnej.

Iterator

Iterator

Uwaga: Należy pamiętać, że w iteratorze można iść tylko do przodu, nie możesz uzyskać poprzedniej części, skopiować jej ani zresetować iteratora.

Interfejs iteratora definiuje tylko metodę __next__().

Funkcje mogą zatem procesować całe wyjście iteratora, a jeśli chcesz zrobić coś innego z tym samym strumieniem, musisz utworzyć nowy iterator.

Generatory

Generatory to specjalna klasa funkcji, które upraszczają zadanie pisania iteratorów. Funkcje regularne obliczają wartość i zwracają ją, a generatory zwracają iterator, który zwraca strumień wartości.

def generate_ints(N):
    for i in range(N):
        yield i

yield to słowo kluczowe, które jest używane jak return, z wyjątkiem tego, że funkcja zwróci iterator.

Generatory nie przechowują wszystkich wartości w pamięci, generują je w locie.

Generatory

>>> gen = generate_ints(3)
>>> gen
<generator object generate_ints at ...>
>>> next(gen)
0
>>> next(gen)
1
>>> next(gen)
2
>>> next(gen)
Traceback (most recent call last):
File "stdin", line 1, in <module>
File "stdin", line 2, in generate_ints
StopIteration

Lambdy

W Pythonie możemy również tworzyć funkcje nienazwane, używając słowa kluczowego lambda:

f1 = lambda x: x**2

# is equivalent to

def f1(x):
    return x**2

 Ta technika jest przydatna na przykład, gdy chcemy przekazać prostą funkcję jako argument do innej funkcji, na przykład:

map(lambda x: x**2, range(-3,4))

Output:

[9, 4, 1, 0, 1, 4, 9]

Lambdy

Operator lambda lub funkcja lambda służy do tworzenia małych, jednorazowych i anonimowych obiektów funkcyjnych w Pythonie.

Operator lambda może mieć dowolną liczbę argumentów, ale może mieć tylko jedno wyrażenie. Nie może zawierać żadnych instrukcji i zwraca obiekt funkcji, który można przypisać do dowolnej zmiennej.

add = lambda x, y : x + y

print add(2, 3) # Output: 5

W lambda x, y: x + y; 'x' i 'y' to argumenty funkcji, a 'x + y' to wyrażenie, które jest wykonywane, a jego wartości są zwracane jako dane wyjściowe.

Leniwa ewaluacja

Leniwa ewaluacja lub call-by-need to strategia generowania obiektów, która opóźnia wykonanie wyrażenia do momentu, gdy jego wartość jest potrzebna, a także pozwala uniknąć powtarzania wywołań. Iteratory zwracają tylko jeden element na raz.

Leniwa ocena, pozwala na tworzenie nieskończonej sekwencji liczb w generatorach.

def fibonacci():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

Metody programowania funkcyjnego

Funkcja map oczekuje funkcji i dowolnej liczby obiektów iterowalnych, takich jak lista, słownik itp. Przy wywołaniu wykonuje funkcję dla każdego elementu w sekwencji i zwraca listę elementów zmodyfikowanych przez obiekt funkcji.

def multiply2(x):
    return x * 2

map(multiply2, [1, 2, 3, 4]) # Output [2, 4, 6, 8]

map(lambda x : x*2, [1, 2, 3, 4]) #Output [2, 4, 6, 8]

W Pythonie3 funkcja map zwraca iterator lub obiekt mapy, który jest leniwie ewaluowany.

Metody programowania funkcyjnego

Funkcja filter oczekuje dwóch argumentów, funkcji i elementu iterowalnego. funkcja zwraca wartość logiczną. funkcja jest wywoływana dla każdego elementu iterowalnego, a filtr zwraca tylko te elementy, dla których funkcja zwraca wartość true.

a = [1, 2, 3, 4, 5, 6]
filter(lambda x : x % 2 == 0, a) # Output: [2, 4, 6]

Podobnie jak funkcja map, funkcja filter również zwraca listę elementów. W przeciwieństwie do funkcji mapowania funkcja filtrowania może mieć tylko jedno iterowalne wejście.

Podobnie jak map, funkcja filter w Pythonie3 zwraca obiekt filter lub iterator, który jest leniwie ewaluowany.

Metody programowania funkcyjnego

Funkcja reduce wykonuje przekazaną funkcję na każdej kolejnej pozycji i wewnętrzny akumulator wyniku końcowego; na przykład:

reduce(lambda n,m:n*m, range(1,10))
362880


oznacza „silnię 10” (innymi słowy, pomnóż każdy element przez iloczyn poprzednich mnożeń).

W Pythonie 3 funkcja reduce() nie jest już podstawową wbudowaną funkcją i została przeniesiona do functools (nadal część standardowej biblioteki), tj. aby z niej skorzystać, należy ją zaimportować w następujący sposób:

from functools import reduce

Metody programowania funkcyjnego

for e in lst:  func(e)      # statement-based loop
map(func,lst)           # map()-based loop

Zamiana pętli na wywołanie funkcji :

# let's create an execution utility function
do_it = lambda f: f()

# let f1, f2, f3 (etc) be functions that perform actions

map(do_it, [f1,f2,f3])   # map()-based action sequence

Metody programowania funkcyjnego

Znajdź część wspólną dwóch list:

a = [1,2,3,5,7,9]
b = [2,3,5,6,7,8]
filter(                           )

2,3,5,7

Znajdź maksimum w liście

f = (                                )
reduce(f, [47,11,42,102,13])

102

(odpowiedź używa ; zamiast :)

Q: [...]
A: lambda x ; x in a, b

(odpowiedź używa ; zamiast :)

Q: [...]
A: lambda a,b ; a if (a > b) else b