Tipi aggregati - Algoritmi e strutture dati

Bag of integers

Esempio: bag of integer: {1, 1, 3, 5, 5, 5}, in questo caso abbiamo due istanze dell’elemento etichettato 1 e 3 istanze dell’elemento etichettato 5. Gli elementi in sé sono indistinguibili: tutti i 5 sono uguali ma ne ho 3. Una possibile implementazione del bag è con i contatori, ad esempio l’elemento 1 è presente 2 volte. Se un elemento è presente 0 volte vuol dire che non c’è, non fa parte del bag. Il fatto di tenere il conto di quanti elementi ho di un certo valore ci permette anche qui di avere rappresentazioni compatte.

Operazioni sui bag

• Operatori di insiemi: c’è una leggera variante, infatti le operazioni come quelle di unione e di intersezione tra due bag vengono interpretate come operazioni di minimo e massimo, per cui se io faccio l’unione di due bag, prendo gli elementi che ci sono con il conteggio massimo, cioè se un bag contiene un elemento che vale 1 e un altro ne contiene 2, l’unione ne contiene 2, l’intersezione contiene invece il minimo.
• Uguaglianza: la struttura bag ci permette di capire quanti elementi dello stesso valore sono presenti in una certa collezione quando non ci interessa distinguere i singoli elementi, non hanno un’identità individuale ma sono tutti interscambiabili.

L’ordinamento non è rilevante. Le bag hanno un’importante applicazione nell’interpretazione semantica dei testi, cioè capire i testi. Vengono ad esempio utilizzate per le mail o per capire se i luoghi da visitare sono belli o meno.

Sequence

Sequenze of <base_type>: La sequenza è un tipo omogeneo, quindi fatto di oggetti base dello stesso tipo, i cui valori sono sequenze ordinate. Stiamo aggiungendo elementi di aggregazione, infatti il set non ha ordinamento e non conta il numero di volte in cui compaiono gli elementi. Il bag non ha ordinamento ma conta il numero di elementi uguali che ci sono. La sequenza non conta di per sé ma considera l’ordine e gli elementi possono avere lo stesso valore.

Ordine delle sequenze

L’ordinamento è riferito all’ordine degli elementi, non ai valori. L’ordinamento che c’è sui valori è un’altra cosa; l’ordinamento delle sequenze è quello imposto dalla creazione della sequenza. Quindi l’ordinamento delle sequenze lo imponiamo noi nel momento in cui mettiamo i valori.

Esempio: Sequenze of integer: (1, 3, 2, 4, 1, 5) che è diverso da (1, 1, 2, 3, 4, 5). Come nel bag, due elementi possono avere lo stesso valore, ma sono elementi distinti.

Algoritmi di ordinamento

Vedremo che ci sono algoritmi di ordinamento che hanno il compito di riordinare una sequenza partendo dall’ordinamento che ha in input e ottenendo una sequenza di uscita dove l’ordinamento della sequenza e quello dei tipi base coincidono, quindi in questo caso diventerebbe (1, 1, 2, 3, 4, 5), cioè l’ordinamento che io ho imposto alla sequenza e l’ordinamento che la sequenza avrebbe se io considerassi la relazione d’ordine del tipo base vengono a coincidere.

Operazioni sulle sequenze

• isEmpty: è una domanda che ci dice se la sequenza è vuota e non contiene elementi. La sequenza che non contiene elementi è una sequenza.
• Head/Tail: Head è l’elemento che viene per primo nell’ordine che io ho imposto, Tail è l’ultimo elemento che io ho aggiunto alla coda.
• First/Next: First è l’elemento a cui sono arrivato e next è il successivo, è un iteratore, cioè una funzione che ha uno stato, che sa dove è arrivata nella sequenza e permette di andare a individuare l’elemento successivo sapendo l’elemento corrente della sequenza. Questo serve ad accelerare l’esecuzione di molti algoritmi che diversamente dovrebbero visitare nuovamente una sequenza dall’inizio, cioè enumerare tutti gli elementi nell’ordine naturale di quella particolare struttura dati. Nel caso delle liste l’ordinamento è quello in cui vengono scritti gli elementi. La visita di una struttura dati produce una sequenza. Questa operazione di visita e produzione di sequenze, in alcuni linguaggi è detta serializzazione, cioè se io visito una struttura dati in un ordine particolare produco una sequenza che è l’equivalente serializzato di quella struttura dati.
• Equal: uguaglianza.
• Empty.
• Estrazione di prefissi: dall’inizio fino a un certo punto.
• Estrazione di suffissi: da un certo punto fino alla fine.
• Sottosequenze: pezzi di sequenza che si trovano da una posizione a un’altra posizione.

Nella teoria generale dell’elaborazione dei testi si definiscono sottostringhe le sottosequenze che si trovano esattamente uguali nella stringa originale, cioè nell’esempio fatto (3, 2, 4, 1) è una sottostringa di simboli, invece si chiamano sottosequenze le sequenze che compaiono nella sequenza originale ma possibilmente con dei buchi, quindi se io considero la sottosequenza (3, 4, 5) è una sottosequenza e non è una sottostringa, è una sottosequenza perché gli elementi compaiono nella stringa originale nello stesso ordine, però ci sono dei buchi in mezzo, quindi non è una sottostringa.

Nell’elaborazione dei testi è importante distinguere sottostringhe e sottosequenze perché una sottostringa deve esistere uguale a una stringa originale. Se voglio fare una ricerca spesso non sono interessato alle sottostringhe ma alle sottosequenze perché le sottosequenze si trovano nello stesso testo originale ma possibilmente con delle varianti. L’utilizzo della sottostringa va bene se siamo certi che non ci sono errori o varianti nel testo originale, altrimenti si ricorre alla sottosequenza o sottostringa approssimata, quindi qualcosa che va abbastanza vicino.

• Append: aggiunta elementi alla fine.
• Togliere elementi: all’inizio o alla fine della sequenza. Quando tolgo un elemento la sequenza si accorcia, se aggiungo l’elemento si allunga. Ogni elemento che io aggiungo o tolgo da una sequenza ne modifica la lunghezza, cioè il size, cioè il numero di elementi di quella sequenza.

Lo standard considera le sequenze come tipi aggregati omogenei, che vuol dire che tutti gli elementi base hanno lo stesso tipo. I linguaggi di programmazione spesso consentono una generalizzazione delle sequenze in cui i tipi base possono avere elementi diversi. Un esempio è proprio il linguaggio Python: una lista in Python, che è proprio di fatto una sequenza, può essere fatta da oggetti di tipo diverso. Questo ha senso perché così questa struttura è molto più flessibile; quello che rimane della sequenza è: eliminiamo il vincolo che sia una struttura omogenea ma il resto è sempre come prima: esiste un ordinamento che è quello di costruzione e posso andare a individuare elementi all’interno della lista, togliere elementi, aggiungere elementi dove voglio nella sequenza. Esiste una categoria molto importante di sequenze che sono le sequenze di caratteri, le chiameremo stringhe, quindi una stringa di caratteri è una sequenza di caratteri, è così importante che le stringhe esistono come tipo nativo in molte architetture di macchina.

Array

Array <index_type> of <base_type>

Di solito si pensa all’array come array di numeri, come A[i] dove i è un intero. L’array è in realtà un tipo fatto da elementi omogenei, quella del tipo base, quindi array di record, ed è un sottoinsieme del prodotto cartesiano tra un insieme finito detto indice e il tipo base.

Esempio: array [1:4] of integer ((1, 56), (2, 35), (3, 77), (4, 78)). In questo caso il tipo base è [1:4] cioè il sottocampo di interi che va da 1 a 4, è un tipo finito ed è fondamentale che sia così. L’array mette in collegamento gli interi, che sono invece uno spazio molto ampio, e questo tipo base, avrò quindi i seguenti 4 elementi: (1, 56), (2, 35), (3, 77), (4, 78), quindi abbiamo che come primo valore da 1 a 4 e poi tutte le altre possibili combinazioni, ma l’array che consideriamo è un elemento del prodotto cartesiano, cioè un sottoinsieme particolare.

Quindi l’array in sé mappa un insieme finito su un insieme potenzialmente infinito (che non può essere infinito nella macchina ma potenzialmente molto numeroso). Il tipo astratto non ha in sé una nozione di ordinamento dell’indice, cioè 1, 2, 3, 4 sono ordinati perché gli interi sono ordinati, ma potrei fare un array indicizzato sugli insiemi rosso, verde e blu, che è un insieme enumerato e i tipi enumerati non sono ordinati. Quindi l’array non è ordinato su un indice perché l’indice potrebbe non avere un ordinamento naturale. L’importante è che sia un sottotipo finito, cioè che comunque noi possiamo enumerare i valori e mettere in collegamento il valore del tipo indice con un valore che sta invece nel tipo base. Gli array sono omogenei.

Se noi poniamo ulteriori restrizioni a queste cose otteniamo rappresentazioni (con tipi concreti) degli array che possono essere diverse e più o meno efficienti in termini di tempo di accesso. Ad esempio, se limitiamo il tipo indice ad essere un sottotipo intero, abbiamo gli array che sono normalmente implementati nelle macchine, dove addirittura l’architettura di macchina ci mette a disposizione l’indirizzamento base più indice e noi a velocità estremamente elevata riusciamo a individuare l’elemento corrispondente all’indice che consideriamo. Questo è però un caso molto particolare in cui gli indici sono interi e nel caso delle macchine partono da 0. Se lo faccio partire da 100, ho sprecato 100 elementi di memoria. Se poi andiamo ai tipi enumerati, ad esempio considerando i colori, allora non abbiamo questo problema.