Perché gli array non sono espandibili?

Question

Quando creiamo un array, non possiamo modificarne le dimensioni; è sistemato. OK, sembra bello, possiamo creare un nuovo array più grande e copiare i valori uno ad uno e questo è un po 'lento. Qual è il background tecnico di esso?

Answer 1

Questa domanda non ha menzionato una lingua quindi ho intenzione di scegliere array basati su "C" per la mia risposta.

Gli array vengono allocati come un singolo blocco di memoria. Crescere un array è problematico perché l'unico modo per farlo correttamente è coltivarlo alla fine. Per una crescita della dimensione N devono esserci almeno N byte liberi alla fine dell'array prima del prossimo indirizzo assegnato.

Per supportare questo tipo di allocazione è necessario distribuire le allocazioni nello spazio degli indirizzi virtuali. Ciò elimina entrambi i vantaggi di avere allocazioni di memoria più vicine tra loro e serve ad aumentare la frammentazione. Ciò sfugge alla maggior parte dei gestori di memoria che cercano di mettere insieme la memoria e ridurre la frammentazione.

Assegnare un nuovo array in un posto in memoria con spazio sufficiente e copiare l'array non è semplicemente un'opzione come soluzione generale. Il motivo è che la posizione precedente dell'array è visibile ai consumatori tramite i puntatori.

int* array = malloc(int*someSize); 
int* pointer1 = &(arr[2]); 
growArray(&array, 12); // Can't move because pointer1 knows the address of the array 

Answer 2

Un array alle sue radici è un 'array' di memoria contiguo. Altri dati possono occupare i dati prima e dopo quest'area di memoria, quindi non possono essere ridimensionati dinamicamente senza allocare una nuova area diversa di memoria che si adatti alle nuove dimensioni più grandi.

Answer 3

Dipende dalla lingua.

In C (e lingue simili come Java), quando hai dichiarato un array come int ary[10], il sistema ha messo da parte esattamente la memoria sufficiente per contenere dieci numeri interi back-to-back. L'espansione non è stata facile, perché il sistema non ha messo da parte alcuno spazio aggiuntivo (dal momento che non ha idea se si desidera espandere o quanto) e la memoria che è arrivata subito dopo l'array è stato probabilmente utilizzato da qualcos'altro. Quindi, l'unico modo per ottenere un array più grande era quello di mettere da parte un nuovo blocco di memoria che manterrà l'array espanso, quindi copiare i vecchi contenuti e aggiungere i nuovi elementi.

È corretto che ciò può essere lento. Un modo per aggirare è dichiarare i tuoi array più grandi di quelli che ti servono per darti spazio per crescere. Soprattutto sui computer più vecchi, questo potrebbe portare a un programma che consuma molta memoria che non ha mai usato.

Un altro modo per aggirarlo è utilizzare un linguaggio di livello superiore con array espandibili. Ruby, ad esempio, ti consente di aggiungere più elementi su un array senza dover mai dichiarare memoria o copiare il contenuto dell'array.

Answer 4

Dipende dalla lingua dell'utente, ma in genere gli array sono disposti come una serie di spazi sequenziali nella memoria. In questo modo non è necessario memorizzare posizioni di memoria per ogni punto dell'array, è sufficiente memorizzare una posizione di memoria (l'inizio dell'array), quindi aggiungere un offset (l'offset sarà la dimensione di ciascuna voce moltiplicata per l'indice volevi) per scoprire dove è in memoria una voce specifica.

Questo è anche il motivo per cui gli array in genere contengono solo un tipo, altrimenti non è possibile effettuare un calcolo così semplice. Le lingue che consentono di archiviare più tipi in realtà creano una matrice normale e posizionano puntatori a ciascuna voce dell'array - tutti i puntatori hanno in genere le stesse dimensioni. Questo livello di costi indiretti ed è il motivo per cui le lingue "più semplici" tendono ad essere un po 'più lente.

Ad ogni modo, quando si assegna più memoria si desidera mettere la nuova memoria proprio alla fine dell'array - altrimenti si segmenterebbe la memoria con un buco - perché dovresti farlo?

Quindi non è possibile semplicemente estendere l'array senza spostarlo fisicamente.

I computer lo fanno da anni, quindi la maggior parte delle lingue ha un modo per allocare un nuovo blocco di memoria e quindi dire alla CPU di copiare in blocco tutte le voci nel nuovo blocco e cambiare il puntatore in modo che rifletta, ma spesso (C, Java, ...) lasciano questo ai programmatori con comandi specifici per copiare l'array piuttosto che farlo per te (Forse solo per farti sapere che espandere un array non è "Libero"

Sarebbe possibile aggiungere un puntatore alla fine della matrice per passare a un blocco di nuova memoria che si desidera aggiungere alla fine di una matrice, ma ora la ricerca della matrice è stata rallentata di un importo piuttosto significativo.

Molte lingue racchiudono semplicemente gli array come raccolte che consentono questo tipo di funzionalità. Ad esempio, una Java Vector/ArrayList riassegnerà automaticamente la memoria per te.Un elenco collegato in realtà assegna un singolo elemento ogni volta con un puntatore al successivo. Rende molto veloce l'aggiunta di elementi, ma molto lento per andare all'elemento 5000 (devi leggere ogni singolo elemento, mentre con un elemento di lettura dell'array 1 è veloce come l'elemento 5000)

Answer 5

In generale, il linguaggio di programmazione avere un posto un'astrazione di qualcosa che allocare una parte fissa della memoria. Quindi, fuori da questa astrazione, possono essere create altre astrazioni che nascondono la complessità della gestione della memoria, probabilmente spostando/copiando i dati.

maggior parte del tempo, array sono fisse - una (in qualche modo) a basso livello di astrazione - e lists o collections sono costruiti sulla cima di array e sanno come ridimensionare se stessi in modo dinamico.

È utile avere un'astrazione di basso livello per poter implementare l'algoritmo/ottimizzazione efficiente a volte. Ma nella maggior parte del tuo codice puoi usare elenchi e raccolte senza preoccuparti troppo delle prestazioni.

Answer 6

Se è possibile modificare la dimensione di un array dipende dalla lingua che si sta utilizzando. In quelle lingue in cui non è possibile aumentare la dimensione di un array, la ragione è che gli array sono disposti in posizioni consecutive in memoria e il compilatore non può garantire che le posizioni successive alla fine dell'array siano disponibili per essere aggiunte all'array. Molti linguaggi di programmazione supportano tipi di array espandibili, ma questi semplicemente gestiscono la riallocazione e la copia della memoria sottostante per te.

Ad esempio, nel linguaggio di programmazione Curl, esiste un tipo FastArray che ha una dimensione e una dimensione massima. La dimensione massima specifica la dimensione massima dell'array e determina la quantità di memoria allocata per l'array. Esiste un tipo di array più generale, che utilizza un FastArray come implementazione sottostante e sostituirà l'istanza di FastArray se l'array deve essere espanso oltre la dimensione massima del FastArray sottostante.

Answer 7

Indietro in linguaggio assembly, uno era obbligato a dichiarare lo spazio di memoria richiesto per una variabile. Questa era una memoria riservata nel registro Data Segment (DS).

Così, più o meno cercando in questo modo (Borland Turbo Assembler):

.DATA 
    myStringVariable DB "Hello world!", 13, 10 
    myArrayVariable DW "     " 'Reserving 20 bytes in memory (in a row) 

.CODE 

    MOV AX, @DATA 
    MOV DS, AX 
    ' ... 

Poi, una volta che il.Il segmento DATA era delimitato, non poteva essere modificato poiché il segmento .CODE (CS) iniziava con pochi byte in meno.

Quindi, se una matrice sarebbe stato estensibile, come le collezioni sono in .NET, i dati avrebbero sovrascritto il codice, causando il crash del programma, ecc

C/C++ (3.0), Pascal (7.0), i programmi di debug di QBasic, PowerBasic e COM erano basati su questa architettura e potevano fare meglio di quanto consentito dall'Assemblatore.

Oggi, con la tecnologia più flessibile, siamo ora in grado, immagino, di allocare al volo gli indirizzi di memoria in base alle necessità e di mantenere un riferimento su di essi con una sola variabile, quindi gli array sono diventati estendibili con la raccolta. Ma ci sono alcune situazioni in cui hai una quantità precisa di byte da rispettare, come i pacchetti di rete, ecc. Per esempio, dove gli array sono ancora utili. Un altro esempio è per la memorizzazione di immagini in un database. Sapete esattamente che falciare in byte è un'immagine, quindi potete memorizzarla in un array di byte (Byte []).

Forse mi mancano alcune precisioni qui, ho scritto per quello che ricordo dei miei vecchi linguaggi di programmazione preferiti. Forse un pò di gente può portare qualcosa di più dettagliato.

Spero che questo aiuti! =)