# ---
# jupyter:
# jupytext:
# formats: ipynb,py:percent
# text_representation:
# extension: .py
# format_name: percent
# format_version: '1.3'
# jupytext_version: 1.15.2
# kernelspec:
# display_name: Python 3 (ipykernel)
# language: python
# name: python3
# ---
# %% [markdown] slideshow={"slide_type": "slide"}
#
# # Fondamenti di Programmazione
#
#
# **Andrea Sterbini**
#
# lezione 8 - 19 ottobre 2023
# %% [markdown] slideshow={"slide_type": "subslide"}
# # RECAP: estrarre i k massimi da N valori generati a caso
# **$O(n)$** volte (per tutti i valori letti)
# aggiorno la lista di **k** migliori elementi
# - tempo $O(k)$ se **non** tengo i k migliori ordinati
# - oppure $O(k*log(k))$ se li tengo ordinati
#
# Sembra inutile tenerli ordinati!
# %% [markdown] slideshow={"slide_type": "subslide"}
# Avevo dato un suggerimento per migliorare
# - trovare in tempo $O(log(k))$ dove inserire X
# - inserire X (purtroppo in tempo $O(k)$)
#
# E questo ci riporta di nuovo a $O(k)$ per aggiornare i $k$ elementi
#
# Ci vorrebbe una struttura dati con inserimento, cancellazione e minimo in $O(log(k))$
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### SOLUZIONE: from sortedcontainers import [SortedList](https://grantjenks.com/docs/sortedcontainers/sortedlist.html)
# - $O(log(k))$ inserimento di un nuovo valore
# - $O(log(k))$ lettura minimo (elemento a indice 0)
# - $O(log(k))$ cancellazione del minimo
#
# Risultato finale: tempo **$O(n*log(k))$**
# %%
from sortedcontainers import SortedList
help(SortedList.add)
help(SortedList.__delitem__) # usato da 'del massimi[0]' per eliminare il minimo
help(SortedList.__getitem__) # usato da 'massimi[0]' per leggere il minimo
# %% slideshow={"slide_type": "subslide"}
from sortedcontainers import SortedList
def aggiorna_k_massimi_SC(massimi, X, k):
if len(massimi) < k:
massimi.add(X) # O(log(k))
elif massimi[0] < X: # O(log(k))
del massimi[0] # O(log(k))
massimi.add(X) # O(log(k))
# quindi il tempo nel caso peggiore è O(log(k))
# %% slideshow={"slide_type": "subslide"}
def k_massimi_SC_crescente(N, k):
massimi = SortedList()
for X in range(N): # il caso peggiore è la sequenza crescente, ripetuto N volte
aggiorna_k_massimi_SC(massimi, X, k) # O(log(k))
return massimi
# quindi il tempo peggiore è O(log(k)*N)
# %% run_control={"marked": true} slideshow={"slide_type": "subslide"}
# %timeit k_massimi_SC_crescente(1_000_000, 30)
# %timeit k_massimi_SC_crescente(1_000_000, 300)
# %timeit k_massimi_SC_crescente(1_000_000, 3000)
# %timeit k_massimi_SC_crescente(1_000_000, 30000)
# %%
from math import log2
[ log2(X) for X in [30, 300, 3000, 30000]]
# %% [markdown]
# # PAUSA
# %% [markdown] slideshow={"slide_type": "slide"}
# # Tipi in Python
#
# Python NON dichiara nè controlla a runtime se i tipi dei dati forniti alle funzioni (e ritornati) sono "giusti"
#
# Questo perchè i tipi sono dinamici e gli oggetti riferiti dalle variabili "sanno" quali metodi possono essere applicati.
#
# Questo vi fornisce ampia libertà con tutta una serie di controlli eseguiti a run-time.
#
# Nei linguaggi compilati dobbiamo indicare i tipi e questo permette di spostare nella fase di compilazione molti controlli e rendere il codice compilato più veloce.
# %% [markdown] slideshow={"slide_type": "slide"}
# Esistono tool per controllare i tipi usati nel programma, i due più comuni sono:
# - **[mypy](https://mypy-lang.org/)** che fa una analisi statica del codice (ovvero SENZA eseguirlo) e deduce e controlla i tipi
# - **[typeguard](https://typeguard.readthedocs.io/en/latest/)** a run-time (eseguendo il codice)
#
# **Aggiungere i tipi** alle definizioni delle funzioni, variabili ed argomenti ci fa catturare molti più errori
#
# Esistono inoltre dei compilatori di Python (ad es. il progetto **[Codon](https://docs.exaloop.io/codon)** oppure **[Cython](https://cython.org/)**) che lo rendono più efficiente e veloce (al livelo del C/C++) se i tipi vengono indicati (per un sottoinsieme del linguaggio).
# %% [markdown] slideshow={"slide_type": "fragment"}
# ## Come si aggiungono i tipi al codice
# ```python
# # definizione del tipo di una variabile nell'assegnamento
# variabile : tipo = valore
# # oppure come commento
# variabile = valore # type : tipo
# ```
# %% [markdown] slideshow={"slide_type": "fragment"}
# ```python
# # definizione del tipo degli argomenti e del risultato di una funzione
# def funzione( argomento1 : tipo1, ...) -> return_type :
# codice della funzione
# # oppure come commento
# def funzione( argomento1, ...):
# # type:(tipo1, ...) -> return_type
# codice della funzione
# ```
#
# Queste "annotazioni" finiscono in un attributo dell'oggetto funzione e possono essere esaminate e controllate con **`mypy`** oppure con **`typeguard`**
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Come si descrivono i tipi
# - potete usare direttamente i nomi delle classi corrispondenti
# - **bool, int, float, dict, set, tuple, list, ...**
#
# ```python
# pi : float = 3.14
# dati : list[int] = [ 3, 6, 12, 45 ]
# ```
# %% [markdown] slideshow={"slide_type": "subslide"}
# Per i contenitori possiamo indicare
# **tra parentesi quadre** il tipo degli elementi contenuti nel contenitore
#
# esempio | descrizione
# ---:|:---
# **list** | lista eterogenea
# **list[int]** | lista omogenea di **int** (di lunghezza indefinita)
# **dict[str, int]** |dizionario con chiavi tutte **str** e valori tutti **int**
# **set[float]** |insieme omogeneo di **float**
# **tuple[int, float]** |coppia di valori (**int**, **float**) nell'ordine
# **tuple[int, ...]** | tupla di lunghezza variabile contenente solo **int**
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Potete usare sinonimi (alias) al posto di tipi complessi
# Questo aiuta a rendere più leggibili le annotazioni
# ```python
# # una scheda è un dizionario di coppie 'info':'valore'
# Scheda = dict[str, str]
# # una agendina è una lista di schede
# Agenda = list[Scheda]
# ```
# Si tendono ad usare nomi maiuscoli
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Ci sono tipi speciali nel modulo `typing`
# **`from typing import ...`**
# - **None** per indicare il valore **None**
# - **Any** per indicare che va bene qualsiasi tipo
# - **NoReturn** per funzioni non tornano valori (lanciano sempre errore)
# - **Union[ T1, T2 ]** oppure **T1 | T2** per indicare che sono validi sia **T1** che **T2**
# %% [markdown] slideshow={"slide_type": "subslide"}
# - **Optional[T]** equivale a **T | None**
# - **Callable[[...], ReturnType]** per indicare una funzione che riceve gli argomenti **[...]** e torna un **ReturnType**
# - **TypeVar** per definire tipi parametrici
# - ...
# %% slideshow={"slide_type": "subslide"}
## Esempio di annotazioni di tipo
from typing import Sized # i Sized hanno il metodo __len__ e se ne può calcolare la dimensione
# qui ho un criterio di ordinamento che
# - accetta cose che hanno una lunghezza (Sized)
# - e produce coppie (int,Sized)
def criterio(elemento : Sized) -> tuple[int,Sized]:
return len(elemento), elemento
# i tipi sono inseriti nell'attributo __annotations__ dell'oggetto funzione
criterio.__annotations__
# %% slideshow={"slide_type": "subslide"}
# provo a eseguire un test su sorted
def test_sorted():
L : list[Sized] = [ '932', '1', '23', '045', 2 ] # <== ATTENZIONE intero!!!
expected : list[Sized] = ['1', '2', '23', '045', '932']
result = sorted(L,key=criterio)
assert result == expected
if __name__ == '__main__':
test_sorted()
# scopriamo l'errore SOLO A RUNTIME!!!
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## come verificare i tipi staticamente? (senza eseguire il codice)
#
# **`mypy --pretty sorted.py`**
#
# **mypy** scopre l'errore di tipo già dall'assegnamento!!!
# %%
# !mypy --pretty sorted.py
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## MA è anche utile verificare i tipi a runtime
# - possono dipendere da dati esterni
# - **mypy** non è detto che abbia tutte le info necessarie
# - moduli non tipati o tipati male
# - alcune deduzioni ancora non sono implementate
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Run-time type-checking
# Non si fa così: **`python sorted.py`**
#
# (lo scopriamo all'ultimo momento, eseguendo **len**)
# %%
# !python sorted.py
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Run-time type-checking
# NON si fa così: **`pytest sorted.py`**
# ```
# E TypeError: object of type 'int' has no len()
# ```
#
# Si è scoperto solo perchè **len(int)** non funziona
# %%
# !pytest sorted.py
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Molto meglio: col modulo `typeguard`
# Che si installa nell'Anaconda prompt col comendo
#
# **`conda install typeguard -c conda-forge`**
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Si usa eseguendo in Anaconda prompt il comando
#
# **`pytest sorted.py --typeguard-packages=sorted`**
#
# **`E typeguard.TypeCheckError : argument "elemento" (int) is not an instance of collections.abc.Sized`**
#
# BENE: adesso **typeguard** si è accorto che **2** non è di tipo **Sized** quando ha controllato l'assegnamento
# %%
# !pytest sorted.py --typeguard-packages=sorted
# %% slideshow={"slide_type": "subslide"}
### Oppure (sconsigliato): MODIFICANDO IL CODICE
from typeguard import typechecked
from typing import Sized
@typechecked # decoratore che controlla i tipi in ingresso e uscita
def criterio(el : Sized) -> tuple[int,Sized]:
return len(el), el
LL : list[Sized] = [ 'uno', 2 ]
sorted(LL, key=criterio) # <== viene scovato qui
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Cosa vi consiglio di fare
# Definite i tipi degli argomenti e i risultati delle vostre funzioni (e le vostre variabili)
#
# Chiamate
#
# **```mypy --pretty programma.py```**
#
# **```pytest programma.py --typeguard-packages=programma```**
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Come usiamo i tipi negli HW obbligatori
#
# - tutte le funzioni fornite sono annotate coi tipi
# - uno dei test dello HW verifica i tipi a runtime (e che non li togliate)
# %% [markdown]
# # INTERVALLO
# %%
# %%HTML
# %% [markdown] slideshow={"slide_type": "subslide"}
# # Homework 2 (obbligatorio - AA 22-23)
# ## dal blog XKCD di Randall Munroe
# | [](http://m.xkcd.com/2637) | | I+I=II II+II=IV IV+V=IX
| | 1+1=2 2+2=4 4+5=9
|
# | -- | -- | -- | -- | -- |
# %% [markdown] slideshow={"slide_type": "slide"}
# Dato un numero romano (ad es. 'MCMLXI' = 1961) composto dei simboli
#
# | lettera | peso | lettera | peso | lettera | peso | lettera | peso | lettera | peso | lettera | peso | lettera | peso
# |:-------:|:----:|:-------:|:----:|:-------:|:----:|:-------:|:----:|:-------:|:----:|:-------:|:----:|:-------:|:----:
# | **M** | 1000 | **D** | 500 | **C** | 100 | **L** | 50 | **X** | 10 | **V** | 5 | **I** | 1
#
# Supponiamo di scriverlo concatenando direttamente i valori di ciascuna lettera
# ```
# 'MCMLXI' => 1000 100 1000 50 10 1
# => '1000100100050101'
# ```
#
# Chiamiamo questo formato ["formato XKCD"](http://m.xkcd.com/2637) degli interi
# %% [markdown] slideshow={"slide_type": "subslide"}
# ## Obiettivo dello HW
# Bisognava implementare le 4 funzioni:
# ```python
# def decode_XKCD_tuple( xkcd_values : tuple[str, ...], k : int) -> list[int]:
# 'decodifica una tupla di interi in formato XKCD e ne estrae i K massimi'
# def decode_value( xkcd : str ) -> int:
# 'decodifica un valore dal formato XKCD all\'intero corrispondente'
# def xkcd_to_list_of_weights( xkcd : str) -> list[int]:
# 'trasforma un valore in formato XKCD nella lista di pesi interi'
# def list_of_weights_to_number( weigths : list[int] ) -> int:
# 'data una lista di pesi ottiene il numero intero corrispondente'
# ```
# E poi estrarre da una lista di stringhe in "formato XKCD" i **k** valori massimi.
# - convertendo ciascuna stringa nella lista di pesi
# - convertendo ciascuna lista di pesi nel valore intero
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Perchè questo HW era così semplice?
# - vi fornisce già l'analisi (per chi è alle prime armi)
# - controlla che usiate i dati giusti a runtime con **typeguard** (e che non li togliate)
# - controlla che non scriviate codice troppo intricato con **radon**
#
# Gli HW seguenti NON vengono specificati a questo livello di dettaglio
# (l'analisi del problema è a carico vostro)
# %% [markdown]
# ### Realizziamolo
#
# - **decode_XKCD_tuple**: per decodificare la tupla e ottenere i k massimi
# - trasformiamo ciascuna stringa nell'intero e gestiamo i k massimi come si è visto
# %% [markdown]
# - **decode_value**: per trasformare una stringa in un intero
# - trasformiamo la stringa in una lista di pesi
# - otteniamo l'intero dalla lista di pesi
# %% [markdown]
# - **xkcd_to_list_of_weights**: per trasformare la stringa in una lista di pesi
# - scandiamo la stringa cercando i pesi in ordine di lunghezza decrescente (da '1000' a '1')
# - oppure osserviamo che ciascun peso inizia con 5 o con 1
#
# Esempio: 1961: '1000100100050101' -> [1000, 100, 1000, 50, 1]
# %% [markdown]
# - **list_of_weights_to_number**: per trasformare la lista di pesi in un intero
# - applichiamo le regole dei numeri romani:
# - ovvero se un peso è seguito da un peso maggiore (es. 9 = IX)
# - va sottratto
# - altrimenti va sommato
#
# Esempio: [1000, 100, 1000, 50, 1] -> (1000 - 100 + 1000 + 50 + 1) = 1961
# %%
# carico un modulo che applica mypy alle celle di questo notebook
# %load_ext nb_mypy
# attivo la verifica ad ogni salvataggio
# %nb_mypy On
# %%
def decode_XKCD_tuple( xkcd_values : tuple[str, ...], k : int) -> list[int]:
'decodifica una tupla di interi in formato XKCD e ne estrae i K massimi'
interi = [ decode_value(X) for X in xkcd_values ]
return sorted(interi, reverse=True)[:k] # semplice ma non la più veloce
# Esempio
decode_XKCD_tuple(('1000100100050101','1101000','150'), 6)
# %%
def decode_value( xkcd : str ) -> int:
'decodifica un valore dal formato XKCD all\'intero corrispondente'
pesi = xkcd_to_list_of_weights(xkcd)
return list_of_weights_to_number(pesi)
# %%
def xkcd_to_list_of_weights( xkcd : str) -> list[int]:
'''trasforma un valore in formato XKCD nella lista di pesi interi'''
pesi : list[str] = ['1000','500','100','50','10','5','1']
risultato : list[int] = []
while xkcd:
for peso in pesi:
if xkcd.startswith(peso): # se i primi caratteri corrispondono
risultato.append(int(peso)) # aggiungo il peso al risultato come intero
xkcd = xkcd[len(peso):] # accorcio la stringa togliendo la parte trovata
break # smetto il for e continuo il while
return risultato
# Esempio
xkcd_to_list_of_weights('1000100100050101')
# %%
# altrimenti se notiamo che tutti i pesi iniziano per 1 oppure per 5
# inserisco spazio prima di 1 e di 5 e uso split
def xkcd_to_list_of_weights( xkcd : str) -> list[int]:
'''trasforma un valore in formato XKCD nella lista di pesi interi'''
spaziato : str = xkcd.replace('1', ' 1').replace('5', ' 5') # inserisco spazio prima di 1 e 5
return [ int(X) for X in spaziato.split() ] # e spezzo la stringa sugli spazi
# Esempio
xkcd_to_list_of_weights('1000100100050101')
# %%
def list_of_weights_to_number( weigths : list[int] ) -> int:
'data una lista di pesi ottiene il numero intero corrispondente'
somma = 0
for i in range(len(weigths)-1): # per ciascun valore fino al penultimo
if weigths[i] int:
'implementazione usando una list comprehension e zip'
return sum( -X if X
# e produrre una stampa in cui visualizziamo le frequenze
# su righe successive, come **barre di asterischi**
#
# Esempio: da [ 1, 4, 2, 4, 1, 4, 4, 2, 4, 4, 1, 1, 4 ] otteniamo
# ```
# 1 ****
# 2 **
# 3
# 4 *******
# ```
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Problema: stampare l'istogramma di una serie di dati
#
# **Input:**
# - la lista di dati numerici (interi/float?)
# - la definizione degli intervalli (implicita/esplicita?)
#
# **Output:**
# - stringa formata da più righe, una per ogni valore:
# - ciascuna riga contiene il **valore, spazio** e
# tanti **asterischi** quante volte quel valore appare nei dati
#
# **Da decidere**: i valori con conteggio 0 devono apparire?
# '''
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Istogramma con estremi e dati interi
# %% slideshow={"slide_type": "fragment"}
'''
# per ottenere l'istogramma conoscendo gli estremi A,B e i dati
# calcolo le frequenze dei dati
# opzione uno: usiamo una lista se:
# i valori sono interi
# conosciamo l'intervallo di valori possibili [A, B]
# ciascun 'bin' è largo 1
# dalle frequenze produco la stringa
'''
def istogramma_con_estremi_e_dati_interi(A : int,
B : int,
dati : list[int]) -> str:
frequenze : list[int] = calcola_frequenze(A, B, dati)
return produci_istogramma(A, frequenze)
# %% slideshow={"slide_type": "fragment"}
# per calcolare le frequenze come lista di conteggi
def calcola_frequenze(A : int, B : int, dati : list[int]) -> list[int] :
'attenzione agli indici della lista per dati positivi e negativi!'
# usiamo un offset
conteggi : list[int] = [0] *(B-A+1) # devo contenere tutti i valori da A a B COMPRESI
for valore in dati:
if A <= valore <= B: # controllo che il valore sia in [A,B]
conteggi[valore-A] += 1 # sottraggo A per allinearlo all'indice 0
return conteggi
# %% slideshow={"slide_type": "fragment"}
def produci_istogramma(A : int, frequenze : list[int]) -> str :
testo = ''
for indice, frequenza in enumerate(frequenze):
valore = indice + A # devo riaggiungere A all'indice
asterischi = "*"*frequenza
testo += f"{valore:>4}\t{asterischi}\n"
return testo
L : list[int] = [ 2, 17, 1, 4, 2, 8, 11, 2, 4, 8, 11, 3 ]
print(istogramma_con_estremi_e_dati_interi(-5, 20, L))
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Istogramma con estremi e dati float
# - in questo caso posso troncare i valori
# - oppure li potrei arrotondare all'intero più vicino con **round**
# %% slideshow={"slide_type": "subslide"}
## WHAT IF i dati sono float?
def istogramma_con_estremi_e_dati_float(A : int, B : int,
dati : list[float]) -> str:
frequenze = calcola_frequenze_float(A,B, dati)
return produci_istogramma(A, frequenze)
def calcola_frequenze_float(A : int, B : int,
dati : list[float]) -> list[int]:
dati_interi = [ int(X) for X in dati ] # tronco i valori
return calcola_frequenze(A,B, dati_interi)
LF = [ 1.3, 5.7, 2.1, 5.8, 2.4, 4.2, 1 ]
print(istogramma_con_estremi_e_dati_float(-2,9, LF))
# %% [markdown] slideshow={"slide_type": "subslide"}
# ### Istogramma usando dizionari
# Se i dati sono sparsi e ci sono molte frequenze nulle posso usare meno memoria
# %% slideshow={"slide_type": "fragment"}
# se vogliamo usare meno memoria possiamo usare un dizionario
# O(n)
def calcola_frequenze_con_diz_int(dati : list[int]) -> dict[int, int] :
frequenze = {}
for valore in dati: # N volte
if valore in frequenze:
frequenze[valore] += 1
else:
frequenze[valore] = 1
return frequenze
# Esempio
from random import choices
L = choices(range(-10,10), k=30)
istogramma = calcola_frequenze_con_diz_int(L)
print(L)
print(istogramma)
# %% slideshow={"slide_type": "fragment"}
# O(n^2)
def calcola_frequenze_con_diz_int2(dati : list[int]) -> dict[int, int] :
frequenze = {}
for valore in dati: # N volte
frequenze[valore] = dati.count(valore) # O(N)
return frequenze
# oppure con una list-comprehension
'''return { dati.count(valore) for valore in dati }'''
# %% slideshow={"slide_type": "fragment"}
# ricordiamoci di ordinare le chiavi
def produci_istogramma_diz_con_buchi(istogramma : dict[int,int]) -> str :
# ignoro i valori con conteggio 0
testo = ''
for valore, frequenza in sorted(istogramma.items()):
testo += f"{valore}\t" + ('*'*frequenza) + '\n'
return testo
# Esempio
print(produci_istogramma_diz_con_buchi(calcola_frequenze_con_diz_int2(L)))
# %% slideshow={"slide_type": "fragment"}
# per visualizzare anche i valori con frequenza 0 li posso aggiungere al dizionario
def produci_istogramma_diz_senza_buchi(istogramma : dict[int,int]) -> str :
# generare anche i dati con conteggio 0
# aggiungiamo al dizionario i valori con conteggio 0
m = min(istogramma) # minima chiave
M = max(istogramma) # massima chiave
for X in range(m,M+1):
if not X in istogramma:
istogramma[X] = 0
return produci_istogramma_diz_con_buchi(istogramma)
# Esempio
print(produci_istogramma_diz_senza_buchi(calcola_frequenze_con_diz_int2(L)))
# %% slideshow={"slide_type": "fragment"}
# oppure ne posso tenere conto nella generazione del testo
# come frequenza = 0 se la chiave non è presente
def produci_istogramma_diz_senza_buchi2(istogramma : dict[int,int]) -> str :
m = min(istogramma) # minima chiave
M = max(istogramma) # massima chiave
testo = ''
for X in range(m,M+1):
frequenza = istogramma.get(X, 0) # se X non è nel dizionario torna 0
asterischi = '*'*frequenza
testo += f"{X:>4}\t{asterischi}\n"
return testo
print(produci_istogramma_diz_senza_buchi2(istogramma))