Map-reduce

Procedimento di calcolo strutturato in due fasi:

1. map: la stessa funzione/trasformazione viene applicata a tutti gli elementi di una lista
2. reduce: una funzione viene applicata a tutti gli oggetti pasati da map.

def sum_squares(L):
	squares = [e*e for e in L]
	return sum(squares)
 
print(sum_squares(list(range(1, 10))))

A differenza di una soluzione che implementa for/while, in stile C, che uilizza uno spazio costante, questa utilizza uno spazio $O(n)$. Il plus, però, è che la parte di mapping è perfetta per essere parallelizzata.

map builtin

La funzione builtin di map accetta come parametri una funzione e n liste. La funzione passata deve accettare come parametri le n liste. Le liste sono scorse in parallelo, e si tiene la lunghezza della lista più corta. Il risultato di map è un iterabile.

for i in map(lambda x,y,z: x+y+z, [1, 2, 3], [4, 5, 6, 7], [8, 9]):
	print(i)

reduce builtin

inclusa in functools

Riceve come parametri una funzione (che a sua volta deve prendere due parametri), un iterabile e un valore iniziale opzionale. La funzione reduce ritorna un valore dato dalla ripetizione della funzione passata come parametro su tutti gli elementi della lista. La prima esecuzione è fatta con il primo elemento dell’iterabile e, se c’è, il valore iniziale, il secondo elemento altrimenti.

from functools import reduce
 
reduce(lambda x,y: x+y,[1,2,3],10)

groupby è una speciale reduce

words = ["ciao", "hello", "nihao", "hallo", "ciao", "ciao"]
mappedseq = map((lambda w : (w, 1)), words)
# [('ciao', 1), ('hello', 1), ('nihao', 1), ('hallo', 1), ('ciao', 1), ('ciao', 1)]
 
# passaggio fondamnetale. Vanno sortati, se no non si raggruppano
p = sorted(mappedseq)
 
grp = groupby(p, key=lambda x: x[0])
 
f = [(e[0], sum(1 for _ in e[1])) for e in grp]
# [('ciao', 3), ('hallo', 1), ('hello', 1), ('nihao', 1)]
 
# si può sortare di nuovo tutto per avere la parola che compare di più
sorted(f,key=lambda g: g[1],reverse=True)[:1]
 
 

python_book5