Array
array.png

Un array è una struttura dati fondamentale nell'informatica. Ogni linguaggio di programmazione mette a disposizione una qualche forma di array. Esso è definito come un insieme contiguo di locazioni di memoria. Le locazioni di memoria hanno una dimensione sufficiente a contenere i tipi di dati che verranno inseriti nell'array.

L'array è un insieme di dati omogeneo, ovvero ogni elemento appartiene allo stesso tipo. Per questo motivo, è possibile conoscere direttamente la locazione di memoria di un elemento dell'array: infatti l'i-esimo elemento di un array si troverà alla locazione
m = m0 + (i-1)*size
dove m0 è la locazione del primo elemento e size è lo spazio di memoria occupato da un elemento.

Gli svantaggi di una tale struttura sono principalmente due: il primo consiste nella staticità della dimensione. Il numero di elementi di un array viene stabilito quando esso viene creato, e non può essere modificato. Per ottenere un maggiore spazio si deve creare un nuovo array più grande e copiare gli elementi nel nuovo array (complessità tempo O(n)). Inoltre, la memoria viene occupata anche se l'array non è completamente riempito. Il secondo consiste nella difficoltà di inserire elementi in mezzo ad un array: essendo una struttura "rigida", per inserire un elemento nella posizione i-esime è necessario spostare tutti gli elementi successivi di una posizione per poter liberare lo spazio. Nel caso peggiore (inserimento in testa all'array) questa operazione richiede tempo O(n). L'eliminazione è più veloce se l'array non deve restare ordinato, poiché può avvenire eliminando un elemento e inserendo nella locazione vuota l'ultimo elemento dell'array. Invece se l'array deve restare ordinato si devono spostare tutti gli elementi successivi. In questo caso la velocità è uguale a quella dell'inserimento di un elemento. Le operazioni di inserimento e cancellazioni sono molto veloci quando si opera in fondo all'array (tempo costante: O(1)).

L'accesso diretto ad ogni elemento permette di implementare, se l'array è ordinato, una modalità di ricerca molto veloce: la ricerca binaria. Essa riesce ad individuare un elemento dell'array in tempo O(log n).

Implementazione

Si può implementare un array che si espanda e si riduca quando è necessario. In altre parole un array che, quando raggiunge l'occupazione massima, effettua una operazione di espansione, creando un nuovo array e copiando gli elementi del vecchio array, e quando scende sotto una certa occupazione si restringa, creando un array più piccolo. L'operazione di restringimento è necessaria per evitare sprechi di memoria.

Il problema fondamentale è capire quando è necessario modificare le dimensioni e di quanto modificarle. Si tratta di stabilire di quanto espandere un array quando gli elementi raggiungono la dimensione massima e quante posizioni vuote devono essere presenti prima di restringerlo. Poiché la modifica delle dimensioni richiedono complessità O(n), è necessario utilizzarle solo quando è effettivamente necessario.

In particolare, una implementazione ingenua potrebbe rendere questo array dinamico molto lento, aggiungendo e togliendo un elemento alla volta. Una implementazione più interessante consiste nel raddoppiare il numero degli elementi quando l'array è pieno, e dimezzare la dimensione quando nell'array sono occupati meno di un quarto. Se si dimezzasse la dimensione quando l'array è riempito per la metà si otterrebbe un nuovo array completamente riempito, che dovrebbe essere nuovamente ridimensionato dopo l'aggiunta di pochi elementi.

Il ridimensionamento dell'array potrebbe avvenire con il metodo Resize seguente:

private void Resize(int newsize)
{
    object[] newarray = new object[newsize];
    for (int i = 0; i < top; i++)
        newarray[i] = data[i];
    data = newarray;
}

Dove data è l'array e top è il puntatore l'ultimo elemento dell'array. Un semplice stack che utilizza un array ridimensionabile può essere implementato così:

class DynamicArray
{
    object[] data;
    int top;
    public DynamicArray(int size)
    {
        data = new object[size];
        top = 0;
    }
 
    public void Push(object obj)
    {
        if (top < data.Length - 1)
            data[top++] = obj;
        else
        {
            Resize(data.Length * 2);
            data[top++] = obj;
        }
    }
 
    public object Pop()
    {
        object temp = null;
        if (top > 0)
        {
            temp = data[top];
            data[top--] = null;
            if (top < data.Length/4)
                Resize(data.Length / 2);
        }
 
        return temp;
    }
 
    private void Resize(int newsize)
    {
        object[] newarray = new object[newsize];
        for (int i = 0; i < top; i++)
            newarray[i] = data[i];
        data = newarray;
    }
}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License