# definizione vuota del decoratore @profile per non avere errori # quando NON si usa il line-profiler import builtins if 'profile' not in dir(builtins): def profile(X) : return X import random ''' RECAP - ANALISI - IN/OUT/ERRORI/SIDE EFFECTS - vincoli su IN e OUT - algoritmo "rozzo" - definiamo una funzione per ciascun sottoproblema - dictionary (con chiavi immutabili) e set (con elementi immutabili) - list set e dictionary comprehension - sorted e sort con argomento key e funzione/lambda OGGI: - k-massimi di una lista (ma con poca memoria!) - istogramma - di dati interi di cui si conosce il range - di dati float raccolti in colonne di cui si conosce il range - di dati interi qualsiasi (con dizionario) - stampati saltando i valori mancanti - stampati CON i valori mancanti ''' #k-massimi distruttivo @profile def k_massimi_distruttivo(K, L): # controllo che K sia sensato assert 0 <= K <= len(L) , "K non è un valore tra 0 e len(L)" # all'inizio il risultato è [] risultato = [] # per k volte for _ in range(K): # k volte # trovo il massimo e lo elimino dalla lista massimo = estrai_massimo(L) # prop a len(L) # lo metto nel risultato risultato.append(massimo) # # torno il risultato return risultato # estrai_massimo e lo elinìmino dalla lista @profile def estrai_massimo(L): # trovo il massimo massimo = max(L) # proporzionale a len(L) # lo tolgo da L L.remove(massimo) # proporzionale a len(L) # trno il valore trovato return massimo # per una versione non distruttiva @profile def k_massimi_ND(K, L): # copio la lista lista1 = L.copy() # uso k_massimi_distruttivo sulla copia return k_massimi_distruttivo(K, lista1) ''' Se la lista iniziale fosse stata ordinata le cose sarebbero state molto più semplici IDEA: ordiniamo la lista e prendiamo i primi K valori ''' # per ottenere i k massimi @profile def k_massimi_ordinati(K,L): # controllo su K # ordiniamo L ordinati = sorted(L, reverse=True) # N log(N) # estraggo i k primi valori # li ritorno return ordinati[:K] ''' WHAT IF: vogliamo usare pochissima memoria? - il minimo è K (elementi massimi da ritornare) - IDEA: 1) ricordiamo solo i K elementi migliori trovati 2) per ogni nuovo valore aggiorniamo i K valori ''' ############################################################ # trovare i K massimi usando poca memoria ''' # per trovare i kmassimi con poca memoria # - iniziamo con una lista di k valori vuota # - per ciascuno dei valori di L # - aggiorno la lista dei K massimi # - ritorno la lista di k massimi # per aggiornare la lista con un nuovo valore e sappiamo che ce ne servono k # - se la lunghezza della lista < k # - aggiungo il valore # - se il valore è <= minimo # - lo ignoro # - altrimenti è > minimo # - tolgo il minimo # - aggiungo il valore ''' # per trovare i kmassimi con poca memoria def k_massimi_lowmem(L, K): # O(K * N) # - iniziamo con una lista di k valori vuota massimi = [] # O( 1 ) # - per ciascuno dei valori di L for valore in L: # per N volte # - aggiorno la lista dei K massimi aggiorna_massimi(valore, massimi, K) # O(K) # - ritorno la lista di k massimi return massimi # O(1) # per aggiornare la lista con un nuovo valore e sappiamo che ce ne servono k def aggiorna_massimi(X, MAX, K): # O(K) # - se la lunghezza della lista < k if len(MAX) < K: # O(1) # - aggiungo il valore MAX.append(X) # O(1) return minimo = min(MAX) # O(K) # - se il valore è <= minimo if minimo >= X: # O(1) # - lo ignoro return # - altrimenti è > minimo else: # - tolgo il minimo MAX.remove(minimo) # O(K) # - aggiungo il valore MAX.append(X) # O(1) # per aggiornare la lista ordinata con un nuovo valore # (e sappiamo che ce ne servono k) # - se la lunghezza della lista < k # O(1) # - aggiungo il valore mantenendo la lista ordinata # O(K) # - trovo il minimo # O(1) # - se il valore è <= minimo # O(1) # - lo ignoro # - altrimenti è > minimo # - tolgo il minimo # O(1) # - aggiungo il valore mantenendo la lista ordinata # O(K) # per aggiungere il valore mantenendo la lista ordinata # cerco dove va inserito O(log K) # inserisco il valore O(K) # è possibile aggiornare i K massimi più rapidamente? # WHAT IF i K valori vengono tenuti ordinati? # trovare i K massimi tenendo i k valori ordinati # tenere aggiornata la lista di massimi riordinandola # tenere aggiornata la lista di massimi inserendo il valore al posto giusto # per inserire un valore in una lista ordinata ############################################################ # istogramma di valori interi in intervallo noto (o ignorando gli out) # - IN: una lista di valori (interi o float) di cui sappiamo in che intervallo sono [A,B] # - OUT: una stringa che ha per ogni valore lo schema # numero tab tanti asterischi quanti dati hanno quel valore accapo def istogramma_con_intervallo(valori, A, B): # costruire una lista che ha come posizione il valore e come contenuto il # di # la lista deve contenere tutti 0 conteggi = [0] * (B-A+1) # per ciascun valore X in input for X in valori: # calcolare la posizione in cui va inserito (X-A) posizione = int(X - A) # incremento l'elemento della lista che sta in quella posizione conteggi[posizione] += 1 # costruisco la stringa per i conteggi ottenuti return costruisci_istogramma(conteggi, A) # per costruire la stringa per i conteggi ottenuti (sapendo A) def costruisci_istogramma(conteggi, MIN): # il testo iniziale è "" testo = '' # per ciascuno dei conteggi for posizione, frequenza in enumerate(conteggi): # ricostruisco il valore originale che corrisponde all'indice (indice + A) valore = posizione + MIN # aggiungo una riga " valore tab tanti asterischi accapo" testo += str(valore) + '\t' + ('*'*frequenza) + '\n' # torno la stringa totale return testo # istogramma di valori float -> interi # istogramma di valori interi qualsiasi (dizionario) def istogramma_con_dizionario(valori): # O(N) # all'inizio il dizionario è vuoto conteggi = {} # O(1) # per ciascun valore nei dati for valore in valori: # per N volte # se necessario lo converto in intero valore = int(valore) # O(1) # se è presente nel dizionario if valore in conteggi: # O(1) # ne incremento il conteggio conteggi[valore] += 1 # O(1) # altrimenti else: # lo aggiungo con valore 1 conteggi[valore] = 1 # O(1) # costruisco la stringa testo = costruisci_istogramma_con_dizionario(conteggi) # X # la ritorno return testo # per costruire la stringa dal dizionario def costruisci_istogramma_con_dizionario_con_salti(frequenze): # all'inizio la stringa è '' testo = '' # per ciascun valore e conteggio for chiave, valore in sorted(frequenze.items()): # aggiungo la riga "valore tab * x conteggio accapo" testo += str(chiave) + '\t' + '*' * valore + '\n' # torno la stringa return testo # per costruire il testo da un dizionario compresi i valori nulli def costruisci_istogramma_con_dizionario(frequenze): testo = '' # trovo massimo e minimo delle chiavi MAX = max(frequenze) MIN = min(frequenze) # per tutti i valori tra minimo e massimo compreso for valore in range(MIN, MAX+1): # se il valore appare nelle chiavi dizionario if valore in frequenze: # la frequenza da mostrare è il valore nel dizionario freq = frequenze[valore] else: # altrimenti la frequenza da mostrare è 0 freq = 0 # aggiungo una riga come quella di prima testo += str(valore) + '\t' + '*'*freq + '\n' # torno il testo return testo # tempi di calcolo usando count e la nostra funzione def calcola_istogramma_con_count(valori): # X + O(N^2) conteggi = {} # O(1) # per ogni diverso valore nella lista valori_possibili = set(valori) # O(N) for X in valori_possibili: # per N volte (nel caso peggiore) # contarlo usando count ed aggiungerlo al dizionario conteggi[X] = valori.count(X) # O(1) + O(N) return costruisci_istogramma_con_dizionario(conteggi) # X # ordinamento? # stampa con salti # stampa senza salti # calcolo le frequenze di valori interi qualsiasi (dizionario) def frequenze(valori): # O(N) # all'inizio il dizionario è vuoto conteggi = {} # O(1) # per ciascun valore nei dati for valore in valori: # per N volte # se è presente nel dizionario if valore in conteggi: # O(1) # ne incremento il conteggio conteggi[valore] += 1 # O(1) # altrimenti else: # lo aggiungo con valore 1 conteggi[valore] = 1 # O(1) return conteggi # riconoscere anagrammi def anagrammi(A, B): # calcolo la frequenza delle lettere nelle due stringhe freqA = frequenze(A) freqB = frequenze(B) # se i due dizionari sono uguali allora le due stringhe sono anagrammi return freqA == freqB # generare anagrammi if __name__ == '__main__': # questo codice non viene eseguito dall'import ma solo eseguendo il file N = 200 A = -170 B = +200 L = random.choices(range(A, B+1), k=N) #isto = istogramma_con_intervallo(L, A, B) #isto = istogramma_con_dizionario(L) #isto2 = calcola_istogramma_con_count(L) #print(isto2) #assert isto == isto2